Abstract: Physical interactions in quantum many-body systems are typically local: Individual constituents interact mainly with their few nearest neighbors. This locality of interactions is inherited by a decay of correlation functions, but also reflected by scaling laws of the en-tanglement entropy of ground states. This entropy of the reduced state of a subregion often merely grows like the boundary area of the subregion, and not like its volume, in sharp contrast to an ex tensive behavior. Such "area laws'' for the entanglement entropy and related quantities have received considerable attention in recent years. They emerge in several seemingly unrelated fields, in the context of black hole physics, quantum information science, and quantum many-body physics.

In this talk we review the current status of area laws in these fields. Center stage is taken by rigorous results on lattice models in one and higher spatial dimensions. A significant proportion of the talk is devoted to the connection between the entanglement content of states and the possibility of their efficient numerical simulation.

The talk is based on the recent review "Area laws for the entanglement entropy - a review", J. Eisert, M. Cramer, M.B. Plenio,
arXiv:0808.3773, to be published in Reviews of Modern Physics.

Daniel Gottesman (Perimeter Institute, Canada)
Computationally hard problems in spin systems

Abstract: Consider the problem of finding the ground state energy of a Hamiltonian describing a spin system with local interactions. It turns out that this is an extremely difficult problem, so hard that we believe it cannot be efficiently solved on a quantum computer (i.e., it is not in BQP), nor can a potential answer be checked efficiently on a classical computer (it is not in NP). This problem is in fact complete for a complexity class known as QMA, which is the most natural quantum analogue of NP. I will define QMA and describe the major results and techniques relating to QMA-completeness of local Hamiltonians.

Miguel Angel Martin-Delgado (Departamento de Fisica TeoricaI, Universidad Complutense, Madrid)
Topology Induced Anomalous Defect Production by Crossing a Quantum Critical Point

Abstract: We study the influence of topology on the quench dynamics of a system driven across a quantum critical point. We show how the appearance of certain edge states, which fully characterise the topology of the system, dramatically modifies the process of defect production during the crossing of the critical point. Interestingly enough, the density of defects is no longer described by the Kibble-Zurek scaling, but determined instead by the non-universal topological features of the system.
Edge states are shown to be robust against defect production, which highlights their topological nature.
arXiv:0811.3843 (Phys. Rev. Lett. to be published)

Tobias Osborne (Royal Holloway, London)
The computational complexity of simulating quantum spin systems

Abstract: In this talk I’ll review the foundational results concerning the computational complexity of simulating quantum spin systems. In particular, I’ll describe what is known about simulating the ground-state properties of 1D spin systems and the dynamical properties of low-dimensional quantum spin spin systems, as well as partial results concerning disordered quantum spin systems. I’ll also describe how the efficiency of popular numerical methods such as the density matrix renormalization group is intertwined with how information propagates through quantum spin systems.

Pawel Wocjan (University of Central Florida)
The Power and Limitations of Quantum Computing - a Characterization in terms of PromiseBQP-complete Problems

Abstract: In this talk, I will give an extensive introduction to the known characterizations of BQP in terms of PromiseBQP-complete problems such as evaluating quadratically signed weight enumerators and the Jones polynomial. PromiseBQP-complete problems are in a precise complexity-theoretic sense the hardest problems that can be solved efficiently on a quantum computer. I will especially focus on the “non-quantum” characterization of the power and limitations of quantum computing in terms of the following simple matrix problem.

Let A be a real symmetric matrix of size N such that the number of non-zero entries in each row is polylogarithmic in N and the positions and the values of these entries are specified by an efficiently computable function. The problem is to estimate an arbitrary diagonal entry (A^m)_{jj} of the matrix A^m up to an error of epsilon b^m, where b is an a priori given upper bound on the norm of A and m and epsilon are polylogarithmic and inverse polylogarithmic in N, respectively.