Can a classical experimentalist command an untrusted quantum system to realize arbitrary quantum dynamics, aborting if it misbehaves? We prove a rigidity theorem for the famous Clauser-Horne-Shimony-Holt (CHSH) game, first formulated to provide a means of experimentally testing the violation of the Bell inequalities. The theorem shows that the only way for the two non-communicating quantum players to win many games played in sequence is if their shared quantum state is close to the tensor product of EPR states and their measurements are the optimal CHSH measurements on successive qubits. This theorem may be viewed as analogous to classical multi-linearity testing, in the sense that the outcome of local checks gives a characterization of a global object. Control over the state and operators can also be leveraged to create more elaborate protocols for realizing general quantum circuits. In particular, it allows us to establish that a quantum interactive proof system with a classical verifier is as powerful as one with a quantum verifier.

### Tuesday, February 19th, 2013

It has been known since the work of Bell that entanglement allows for the generation of super-strong correlation between spatially isolated parties. The study of entanglement in many-body systems, however, has revealed important constraints on these correlations as the number of systems increases. The exploitation of the key such constraint, entanglement monogamy, is behind a number of recent results in the study of entanglement in ground states of gapped Hamiltonians as well as the quantum PCP conjecture.

All known results seeking to exploit monogamy to its fullest extent, such as de Finetti-type theorems, only provide strong bounds as the number of systems under study increases. Indeed it seems natural that monogamy dictates an asymptotic weakening of the strength of entanglement as it is shared between more and more parties.

In this talk we will ask the question whether there is an analogue of monogamy that already manifests itself strongly when only a constant number of systems are available. We will give a positive answer to this question by introducing tools from complexity theory, including the celebrated BLR linearity test. We will show that the constraints imposed by this test lead to a new formulation of asymptotic monogamy-like constraints on entanglement in tripartite systems. As an application, we will use this result towards the resolution of a long-standing open question in quantum complexity theory.

No abstract provided.

The local Hamiltonian problem consists in estimating the groundstate energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum generalisation of constraint satisfaction problems (CSPs) and has a key role in quantum complexity theory, being the first and most natural QMA-complete problem known. An interesting regime for the local Hamiltonian problem is that of extensive error, where one is interested in estimating the mean groundstate energy to constant accuracy. The problem is NP-hard by the PCP theorem, but whether it is QMA-hard is an important open question in quantum complexity theory. A positive solution would represent a quantum analogue of the PCP theorem. In this talk I will present new approximation guarantees for solving the local Hamiltonian problem within constant extensive error.

First I'll show how to obtain in NP a proof of small mean groundstate energy that depends on two parameters:

- The degree of the constraint graph: Here I'll show that the problem is in NP for Hamiltonians on high degree graphs, with a product state giving an approximation to the groundstate energy of error inverse polynomial in the degree of the graph. In contrast, the PCP theorem holds true with error independent of the degree of the constraint graph of the CSP. This result also gives a rigorous justification to the folklore in condensed matter physics that mean field becomes exact once the dimension of the lattice grows.
- The average entanglement in the ground state of the Hamiltonian: Here we find that the problem is also in NP for Hamiltonians that satisfy a subvolume law for the entanglement entropy. This gives a new connection between the amount of entanglement in the groundstate of a local Hamiltonian and its computational complexity.

The approximation guarantees obtained give new limitations on which type of Hamiltonians one could expect to base a possible quantum analogue of the PCP theorem.

Second I'll briefly present new polynomial-time algorithms for approximating the mean groundstate energy of three classes of Hamiltonians: (i) 2-local Hamiltonians on any planar graph, solving an open problem of Bansal, Bravyi, and Terhal; (ii) dense k-local Hamiltonians for any constant k, solving an open problem of Gharibian and Kempe; and (iii) Hamiltonians on low-threshold graphs, building on work of Barak, Raghavendra, and Steurer.

The main idea behind the results is an information-theoretic argument inspired by recent work on the convergence of the Lasserre hierarchy for CSPs. Based on joint work with Aram Harrow.

### Wednesday, February 20th, 2013

The density matrix renormalization group is the most successful numerical approach for finding ground states of one dimensional systems in condensed matter physics. We now understand that DMRG is based on a natural low-entanglement approximation, exploiting the low entanglement of ground states embodied in the area law for entanglement entropy. DMRG has gradually become a leading technique for studying two dimensional systems, particularly frustrated magnetic systems, where much effort has gone into the search for realistic models which can be shown to have quantum spin liquid ground states. In this talk, I will give a broad overview of DMRG and quantum spin liquids, our recent success in showing that the Kagome lattice Heisenberg model is a spin liquid, and our attempts to find additional spin liquid models.

Originating from the works of Bekenstein and Hawking on the entropy of black holes, area laws constitute a central tool for understanding entanglement and locality properties in many-body quantum systems. Essentially, in a system that obeys an area law, the entanglement entropy of a bounded region scales like its boundary area, rather than its volume.

In 2007 Hastings proved that all 1D quantum spin systems with a constant spectral gap obey an area law in their ground state. A major open problem is whether an area law holds also in two or more dimensions.

In this talk I will present a new proof for the 1D area law, which gives an exponentially smaller bound on the entanglement entropy, and is within a polynomial factor from the best known lower bounds. The proof also implies that the ground state can be well-approximated by an MPS with sublinear bond dimension. I will talk about the main mathematical ideas behind the proof, as well as the challanges that one faces when trying to prove the 2D case.

Joint work with A. Kitaev, Z. Landau and U. Vazirani

We will show that not only the ground states of gapped local quantum Hamiltonians obey an area law, but also the low lying excited states. This yields fundamental new insights into the nature of elementary particles in strongly correlated quantum systems.

The structure of ground states of local Hamiltonians is one of the fundamental questions in condensed matter physics and quantum complexity theory, and is the quantum analog of constraint satisfaction problems (CSPs). Here we will present a surprising result: a classical polynomial time algorithm for approximating ground states of 1D gapped Hamiltonians. The algorithm builds on concepts introduced in recent proofs of 1D area laws (specifically approximate ground state projectors (AGSPs)) and convex programming. Based on joint work with Umesh Vazirani and Thomas Vidick.

### Thursday, February 21st, 2013

Certain many-body quantum systems can be efficiently described in terms of Projected Entangled-Pair States (PEPS). In this talk I will review some of the properties of such states, paying special attention to the bulk-boundary correspondence they define. In particular, I will show how topological properties are reflected in the theory of the boundary. This work was done in collaboration with D. Pérez García, D. Poilblanc, N. Schuch and F. Verstraete.

A recent theoretical breakthrough has been the identification of new gapped topological phases which only appear in interacting systems, but which, unlike fractional Quantum Hall states or spin liquids, only have short ranged quantum entanglement. Although one dimensional examples – such as the Haldane phase of the spin-1 chain - have been long known, only recently have higher dimensional realizations been proposed based on a mathematical classification scheme, which however leaves open the physical nature of these phases. We will discuss a physical approach in 2D and 3D, that captures the defining properties and an intuitive picture of these states, as well as provides a route to their realization in experimental systems.

[1] Theory and classification of interacting integer topological phases in two dimensions: A Chern-Simons approach, Yuan-Ming Lu and Ashvin Vishwanath, Phys. Rev. B 86, 125119 (2012)

[2] Physics of three dimensional bosonic topological insulators: Ashvin Vishwanath and T. Senthil, arXiv:1209.3058

Quantum codes with low density parity checks (LDPC) enable reliable storage of encoded quantum states by monitoring syndromes of simple low-weight check operators. Such codes have recently found applications in fault-tolerant quantum computing and as toy models of quantum memory Hamitonians. In this talk I will review some of the recent developments and open problems concerning quantum LDPC codes that are of relevance for quantum Hamiltonian complexity and the theory of topological quantum order.

In the second part of the talk I will present a new construction of quantum LDPC codes based on a tensor product of chain complexes and the Künneth theorem. Given a pair of stabilizer codes [[n,k,d]] and [[n',k',d']] with check operators of weight w and w', their homological product is a stabilizer code [[O(nn'),kk',dd']] with check operators of weight w+w'. Our proof requires one of the two input codes to obey a technical condition that we call composability, whereas the second input code can be arbitrary. We show that the Steane [[7,1,3]] code and its concatenated versions are composable. Using this result we construct the first example of quantum LDPC codes with check operators of logarithmic weight and the minimum distance scaling faster than the square root of the code size.

Under a certain set of conditions collectively known as "local topological order", the low energy spectrum of a system is robust to local perturbations. This has the consequence that quantum information encoded in the degenerate ground state of such a system is stable at zero temperature. On the other hand, the existence of a macroscopic energy barrier between ground states imply that information encoded in the ground state is robust against thermal fluctuations. Here, we demonstrate that for local commuting projector codes, local topological order prohibits the existence of an energy barrier, which shows a tradeoff between robustness to quantum and thermal fluctuations. I will also discuss relations to area law and quantum Markov networks.

### Friday, February 22nd, 2013

The theme of this talk is the interplay between entanglement and renormalization in quantum matter. I will begin by describing recent progress in computing entanglement properties of interesting ground states by focusing on the low energy physics. Then I will discuss how the results of such studies lead us naturally to consider certain classes of tensor network states that incorporate the interplay between entanglement and renormalization. Finally I will talk about the connections between such tensor network states and holographic duality, which is a correspondence between quantum field theory and quantum gravity. I will not assume any prior knowledge of holography and only basic familiarity with the ideas of entanglement and renormalization.

Relativistic quantum field theory describes all of the fundamental interactions in Nature, with the possible exception of gravity, I will describe and analyze a quantum algorithm for simulating real-time evolution in an interacting massive scalar quantum field theory in four or fewer spacetime dimensions. The run time of the algorithm scales polynomially in the particle number, the energy, and the desired precision. Hence the algorithm achieves an exponential speedup relative to the best existing classical algorithms. This result supports the conjecture that all physical processes in Nature can be simulated efficiently using a universal quantum computer. Based on joint work with Stephen Jordan and Keith Lee.