Coogee’15

Sydney Quantum Information Theory Workshop

Dan Browne

(UCL, UK)

QMA-hard local Hamiltonians from non-unitary circuits

In 1999, Kitaev proposed the complexity class QMA as a quantum analogue of NP and showed that a local Hamiltonian problem is QMA-complete [1]. Kitaev's construction and proof are now the foundation stone of a growing and active field of research known as Hamiltonian Complexity.

At the heart of Kitaev's construction adopts a method proposed by Feynman in 1984 to map unitary quantum circuits into the terms of a Hamiltonian. In the theory of quantum computing, unitary circuits play a central role but quantum computation does not need to be unitary. Measurement-based, and teleportation-based computation show that projective measurement can have an equally powerful role as unitary gates in quantum computation. Furthermore, post-selection, or renormalised projection, can be a powerful computational tool radically changing the computational complexity of a model [2].

In this work [3], we generalise Feynmann's circuit-to-Hamiltonian mapping to include certain non-unitary gates.   This allows us to construct new alternative constructions for QMA-hard Hamiltonian families based on non-unitary, e.g. teleportation-based or cluster-state computing. We prove such constructions are QMA-hard and discuss the prospects and challenges for generalising further. Applications of this new construction are work-in-progress, but may offer opportunities for novel clock constructions [3] or the incorporation of certain noisy, but error corrected evolutions into QMA-hard constructions.

Joint work with Nairi Usher, UCL

Further reading and references:

* indicates recommended pre-reading 

[1] QMA and the local Hamiltonian problem

* Kitaev, Shen and Vyalyi - Classical and Quantum Computation - Chapter 14. 

A very clear introduction to QMA and Kitaev's proof for the local Hamiltonian problem. Unfortunately, Kitaev's book is not available online. Kitaev's proof has been summarised in a variety of papers, e.g. Dorit Aharonov, Tomer Naveh, quant-ph/0210077, and Daniel Nagaj's talk http://simons.berkeley.edu/talks/daniel-nagaj-2014-02-24 gives a good intuition for the proof.  

[2] The computational power of post-selection

Scott Aaronson, Quantum Computing, Postselection, and Probabilistic Polynomial-Time, quant-ph/0412187

* Bremner, Shepherd and Jozsa, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy, arXiv:1005.1407

[3] Teleportation-based and Measurement-Based Quantum Computing

See e.g. Briegel et al, arXiv:0910.1116, Nielsen, arXiv:quant-ph/0504097 or Jozsa, arXiv:quant-ph/0508124 

* For this talk, however,  figure 1 of Bremner, Shepherd and Jozsa (above) covers the necessary key ideas of MBQC and Teleportation-based QC.

[4] Nairi Usher and Dan E. Browne, QMA-hard local Hamiltonians from non-unitary circuits, in preparation

[5] Novel clock constructions

See eg: Daniel Nagaj's talk (above) or Breuckmann and Terhal, arXiv:1311.6101

Fernando Brandao

(UCL, UK)

The Fawzi-Renner Inequality by State Redistribution

In a recent breakthrough Fawzi and Renner proved a lower bound to the conditional mutual information of a tripartite state in terms of its distance to the closest reconstructed state. In this talk I'll discuss their inequality and outline a few applications, for instance in the study of topological order.  Then I will present a simplified proof of the result (in fact of a strengthening of it) based on the state redistribution protocol of Devetak and Yard.

Relevant papers:

[1] http://arxiv.org/abs/1410.0664

[2] http://arxiv.org/abs/1411.4921

[3] http://arxiv.org/abs/1410.4184

[4] http://arxiv.org/abs/quant-ph/0612050

Toby Cubitt

(Cambridge, UK)

Turing’s wheelbarrow: towards realistic QMA-hard Hamiltonians

Abstract: (Warning: all condensed matter physicists appearing in this abstract are fictitious. Any resemblance to real condensed matter physicists, living or dead, is purely coincidental.)

When Kitaev [1] proved QMA-hardness of 5-local Hamiltonians, condensed matter physicists said it wasn't relevant to physics because 5-body interactions are unrealistic. When Kitaev, Kempe and Regev [2] extended the result to 2-local Hamiltonians, they still said it wasn't physically relevant because of the geometrically non-local interactions. When Oliveira and Terhal [3] extended it nearest-neighbour interactions on a 2D square lattice of qubits, they still said it wasn't physically relevant because the interactions were non-uniform. And anyway everyone knew that 2D systems were complicated. When Aharonov, Gottesman, Irani and Kempe [4] extended it to a 1D chain, they still said it wasn't physically relevant because the interactions weren't translationally invariant. When Gottesman and Irani [5] proved QMA_EXP-hardness of a translationally-invariant 1D chain, condensed matter physicists still said it wasn't physically relevant because the local dimension was ridiculously large.

I'll explain how we've extended Gottesman and Itani's result to a translationally-invariant 1D chain with local dimension 30 (and falling!), and sketch some of the interesting new technical tools we developed to get the local dimension down by five orders of magnitude. I invite you to guess what the condensed matter physicists will say...

Joint work with Johannes Bausch and Maris Ozols.

Background reading:

[1] A. Kitaev, A. Shen and M. Vyalyi. "Classical and Quantum Computation".

American Mathematical Society.

[2] J. Kempe and A. Kitaev and O. Regev. "The complexity of the Local

Hamiltonian problem". SIAM Journal of Computing, 35, p1070, 2006.

[3] R. Oliveira and B. Terhal. "The complexity of quantum spin systems on

a two-dimensional square lattice". QIC 8, p0900, 2008.

[4] D. Aharonov, D. Gottesman, S. Irani and J. Kempe. "The power of

quantum systems on a line". Comm. Math. Phys. 287, p41, 2009.

[5] D. Gottesman and S. Irani. "The quantum and classical complexity of

translationally invariant tiling and Hamiltonian problems".

arXiv:0905.2419[quant-ph].

Gemma de las Cuevas

(MPQ, Germany)

Which discrete states have a continuum limit?

Renormalization to low energies is widely used in condensed matter theory to reveal the low energy degrees of freedom of a system, or in high energy physics to cure divergence problems. This defines a 'coarse-graining' procedure which is generally irreversible. Here we ask which states can be seen as the result of a coarse-graining procedure, that is, which states can be fine-grained. Intuitively, the limit of the fine-graining procedure is the continuum limit of the state. We consider three definitions of continuum limit and characterise which states satisfy either one in the context of Matrix Product States. 

Ongoing work with N. Schuch, D. Perez-Garcia, and J. I. Cirac

Jens Eisert

(Freie University Berlin, Germany)

Digging in the mud: New perspectives on many-body localization

The phenomenon of many-body localisation has received a lot of attention recently, both for its implications in condensed-matter physics of allowing systems to be an insulator even at non-zero temperature as well as in the context of the foundations of quantum statistical mechanics, providing examples of systems showing the absence of thermalisation following out-of-equilibrium dynamics. Still, many aspects of it are still unsatisfactorily understood, specifically when taking a rigorously-oriented mindset. In this talk, I will undertake the modest attempt to review some of the recent quantum information-inspired approaches to attain new insights into mathematical connections between seemingly unrelated features of many-body localisation. Ideas of entanglement area laws, Lieb-Robinson bounds, approximately local constants of motion and tensor networks will feature strongly.

Further reading and references: A superset of the works considered is

[1] Many-body localisation implies that eigenvectors are

matrix-product states, M. Friesdorf, A. H. Werner, W. Brown, V. B.

Scholz, J. Eisert, arXiv:1409.1252.

[2] Local constants of motion imply transport, M. Friesdorf, A. H.

Werner, M. Goihl, J. Eisert, W. Brown, arXiv:1412.5605.

[3] Quantum many-body systems out of equilibrium, J. Eisert, M.

Friesdorf, C. Gogolin, Nature Physics, February (2015).

[4] Absence of thermalisation in non-integrable systems, C. Gogolin,

M. P. Mueller, J. Eisert, Phys. Rev. Lett. 106, 040401 (2011).

[5] Local integrals of motion and the logarithmic lightcone in

many-body localised systems, I. H. Kim, A. Chandran, D. A. Abanin,

arXiv:1412.3073.

[6] Spectral tensor networks for many-body localisation, A. Chandran,

J. Carrasquilla, I. H. Kim, D. A. Abanin, G. Vidal, arXiv:1410.0687.

[7] Constructing local integrals of motion in the many-body localised

phase, A. Chandran, I. H. Kim, G. Vidal, D. A. Abanin,

arXiv:1407.8480.

[8] Phenomenology of fully many-body-localised systems, D. A. Huse, R.

Nandkishore, V. Oganesyan, Phys. Rev. B 90, 174202 (2014).

[9] Many-body localisation edge in the random-field Heisenberg chain,

D. J. Luitz, N. Laflorencie, F. Alet, arXiv:1411.0660.

[10] Bounds on information propagation in disordered quantum spin

chains, C. K. Burrell, T. J. Osborne, Phys. Rev. Lett. 99, 167201

(2007).

David Gross

(University of Freiberg, Germany)

Non-Negative Phase Space Distributions, with the Benefit of Hindsight

The speaker's first ever result [quant-ph/0602001] characterized the set of pure quantum states that give rise to non-negative discrete Wigner distributions. Nobody (including the author) seemed to care too much - until a series of brilliant and high-profile papers by Veitch, Emerson and others recently rekindled the interest in non-negative representations of QM. In this talk, I'll present a new, more general and highly simplified proof of the original results.

Jeongwan Haah

(MIT, USA)

An invariant of topologically ordered states under local unitary transformations

The notion of phases of matter is often understood only intuitively through examples, despite of their fundamental importance. For gapped quantum phases, topological phases of matter can be viewed as being at the coarsest level, but they are still ill-defined beginning from general local Hamiltonians.

I will take a viewpoint that quantum phases of matter are equivalence classes among many-body wave functions where the relation is defined by local unitary transformations, and discuss a particular class of ground states of gapped local Hamiltonians for which we can talk about classification. I will show how the notions of quasi-particles and braiding are engraved in the ground state wave function. The mechanism allows us to find rigorous invariants of the states, which are closely related to so-called topological S-matrix. A corollary is that for two states with different invariants any quantum circuit connecting them must have depth proportional to the system’s diameter.

Suggested reading material:

* Kitaev, Preskill, “Topological entanglement entropy” PRL 96, 110404 (2006)

* Bravyi, Hastings, Verstraete, "Lieb-Robinson Bounds and the Generation of Correlations and Topological Quantum Order” PRL 97, 050401 (2006)

* Zhang et al, "Quasiparticle statistics and braiding from ground-state entanglement” PRB 85, 235151 (2012)

* Haah, “An invariant of topologically ordered states under local unitary transformations” arXiv:1407.2926

Aram Harrow

(MIT, USA)

Mystery talk!

Michael Kastoryano

(Freie University Berlin, Germany)

Non-equilibrium phase transitions, old and new insights

A number of different models exhibiting non-equilibrium phase transitions will be introduced and analyzed. Some are quantum others are purely classical. I hope to convince you by the end of the presentation that this is a rich and interesting topic that researchers in our community should spend more time thinking about. 

The first model I will consider is a single particle system on a one dimensional line that combines coherent and dissipative hopping. The model exhibits a phase transition, which is characterized by a complete suppression of the current in one phase. We will argue that the origin of this transition is topological, and show that it is robust to several types of disorder. 

I will subsequently review a different class of (many particle) classical models which is often called Directed Percolation (DP), and a particularly interesting extension of this called Self-Organized Criticality (SOC). Finally, I will show that these models provide some insight on the area law conjecture. 

The first part of this talk is based on joint work with Mark Rudner.

Isaac Kim

(Perimeter Institute, Canada)

Conservation laws from entanglement

Abstract: In physics, conservation laws are often derived from Noether’s theorem by invoking certain symmetries. In this talk, I will argue that conservation laws can follow from another mechanism as well, without invoking any symmetries. The key player behind this mechanism is entanglement. I will explain how this mechanism works for the case of a two-dimensional topologically ordered system, and speculate on its generalization. If time permits, some technical open problems shall be discussed as well.

Background reading list:

cond-mat/0506438(Appendix E), 1111.2342, 1405.0137.

Tobias Osborne

(Hannover, Germany)

What is quantum field theory? A quantum information theorist’s journey

Abstract:

In this talk I will try to make good on my long-standing promise to explain quantum field theory in a quantum information friendly way. In particular, I will describe the modern Wilsonian approach to defining QFT, and explain how to (as rigourously as possible) implement this approach using quantum information theoretic tools. In this way I'll explain how the definition of a QFT can be broken into two key components: (i) firstly, one must introduce the space of regulated quantum field theories; (ii) then the regulated theory space needs to be subjected to a completion process to yield continuum theories without cutoff. It turns out that the completion process is naturally carried out with respect to a family of quantum information distance metrics which define for us what is meant by a "convergent sequence of regulated QFTs". Such a convergent sequence is then seen to induce a "flow" on the space of QFTs known as the renormalisation group. This flow is generated by a vector field called the beta function. While this may all sound rather baroque I will argue that, conceptually, it is no more difficult than the process whereby one constructs the real numbers from the rational numbers. There are some key bonuses of taking a QI approach: (i) we are able to define QFTs without (necessarily) requiring lagrangians; (ii) we obtain manifestly finite quantum information measures appropriate for interacting QFTs; and (iii) we are able to express all the main known examples of QFTs in this language, and hopefully so much more.

Background reading:

There isn't much written up yet, but you could take a look at the "continuous limits of lattice systems" github repository:

https://github.com/tobiasosborne/Continuous-Limits-of-Quantum-Lattice-Systems

Fernando Pastawski

(Caltech, USA)

A toy model for holographic bulk-boundary correspondence

Toy models are incredibly important in developing our physical intuition by capturing the essential features of more complicated physical phenomena in a tractable way. I will describe a toy model for bulk-boundary correspondence. The model is based on a novel construction for  quantum error correcting code which relies on a MERA-like tensor network. It allows us to provide an explicit prescription for mapping bulk operators onto the boundary operators. We construct a tensor network from elementary tensors associated to data hiding states arranged in a hyperbolic geometry (a geometry with negative curvature. The key observation is that these tensors are unitary along any balanced bipartition of their legs. The hyperbolic curvature is essential to guarantee injectivity and interpret the resulting tensor network as a quantum error correcting code (QECC). When the base tensor is a stabilizer state, the resulting code is also a stabilizer code. We provide explicit examples based on the encoding tensor for the [[5,1,3]] perfect QECC (equivalently [[6,0,4]] data hiding state). For such models we prove an exact Ryu-Takayanagi type formula for the entanglement entropy of any convex region in the boundary. We also discuss how the unitarity along different cuts is a natural feature for describing Lorenz invariant systems, where time and space appear at a similar footing.

This is joint work with Beni Yoshida, Daniel Harlow and John Preskill.

References:

Exact holographic mapping and emergent space-time geometry. Qi, X.-L. (2013). 

Bulk Locality and Quantum Error Correction in AdS/CFT A. Almheiri, X. Dong, D. Harlow (2014)

Entanglement renormalization and holography B. Swingle (2012)

Class of Quantum Many-Body States That Can Be Efficiently Simulated G. Vidal (2008)

David Poulin

(Sherbrooke, Canada)

Single-shot fault-tolerance: I don’t know much about it but I don’t think it can work

Abstract: I will discuss the possibility of realizing a fault-tolerant memory without having to repeat the syndrome measurements a large number of times. I will first show that this is indeed possible for general stabilizer codes, and in fact I will derive an encoding rate at which it can be achieved. But I will present a general argument which shows that this is not possible for LDPC codes (including topological codes). Time permitting (I mean, if I have time to think about it before the workshop), I will extend the argument to subsystem codes.

Recommended reading: http://arxiv.org/abs/1404.5504

Cyril Stark

(MIT, USA)

Compressibility of positive semidefinite factorizations and quantum models

Abstract: We investigate compressibility of the dimension of positive semidefinite matrices while approximately preserving their pairwise inner products. This can either be regarded as compression of positive semidefinite factorizations of nonnegative matrices or (if the matrices are subject to additional normalization constraints) as compression of quantum models. We derive both lower and upper bounds on compressibility. Applications are broad and range from the statistical analysis of experimental data to bounding the one-way quantum communication complexity of Boolean functions. This is joint work with Aram Harrow.

Recommended reading: arXiv:1412.7437.

Krysta Svore

(Microsoft Research, USA)

Quantum Deep Learning

In recent years, deep learning has had a profound impact on machine learning and artificial intelligence. I’ll present a quantum algorithm for deep learning that has several advantages over existing classical deep learning algorithms. Specifically, the proposed quantum machine learning algorithms not only reduce the time required to train a deep network but also allow richer classes of models, including restricted and full Boltzmann machines and multi-layer, fully connected networks, to be efficiently trained. By using quantum state preparation methods, we avoid the use of contrastive divergence approximation and obtain improved maximization of the underlying objective function.

Guifre Vidal

(Perimeter Institute, Canada)

Tensor network renormalization

We introduce a coarse-graining transformation for tensor networks that can be applied to the study of both classical statistical and quantum many-body systems, via contraction of the corresponding partition function or Euclidean path integral, respectively. The scheme is based upon the insertion of optimized unitary and isometric tensors into the tensor network and has, as its key feature, the ability to completely remove short-range correlations at each coarse-graining step. As a result, it produces a renormalization group flow (in the space of tensors) that (i) has the correct structure of fixed points, and (ii) is computationally sustainable, even for systems at a critical point. We demonstrate the proposed approach in the context of the 2D classical Ising model both near and at the critical point.

Joint work with Glen Evenbly

background material: http://xxx.lanl.gov/abs/arXiv:1412.0732 and references therein

Stephanie Wehner

(Delft, The Netherlands)

Understanding nature from experimental observations: a theory independent test for gravitational decoherence

Quantum mechanics and the theory of gravity are presently not compatible. A particular question is whether gravity causes decoherence - an unavoidable source of noise. Several models for gravitational decoherence have been proposed, not all of which can be described quantum mechanically. In parallel, several experiments have been proposed to test some of these models, where the data obtained by such experiments is analyzed assuming quantum mechanics. Since we may need to modify quantum mechanics to account for gravity, however, one may question the validity of using quantum mechanics as a calculational tool to draw conclusions from experiments concerning gravity.

Here we propose an experiment to estimate gravitational decoherence whose conclusions hold even if quantum mechanics would need to be modified. We first establish a general information-theoretic notion of decoherence which reduces to the standard measure within quantum mechanics. Second, drawing on ideas from quantum information, we propose a very general protocol that allows us to estimate decoherence of any physical process for any physical theory satisfying only very mild conditions. Finally, we propose a concrete experiment using optomechanics to estimate gravitational decoherence in any such theory, including quantum mechanics as a special case.

Our work raises the interesting question whether other properties of nature could similarly be established from experimental observations alone - that is, without already having a rather well formed theory of nature like quantum mechanics to make sense of experimental data. We conclude by discussing this possibility.

Joint work with C. Pfister, J. Kaniewski, M. Tomamichel, A. Mantri, R. Schmucker and G. Milburn.