Computational Complexity of Quantum Hamiltonian Systems

The computational complexity of quantum simulations is an active area of research which is of interest to workers in quantum information theory, theoretical computer science, mathematical physics and many-body physics. The intent of the workshop is bring together these different communities, to exchange ideas and discuss the latest results in this area.

Quantum computers hold the promise of being able to simulate quantum systems more efficiently than classical machines.  But exactly what problems can be solved  efficiently on a quantum computer? Recent work has exhibited a class of problems, the estimation of the smallest eigenvalue of a Hamiltonian, which are even hard for  quantum computers.

On the other hand physicists have developed methods such as DMRG, matrix product state techniques, and quantum Monte Carlo methods, to simulate properties of quantum systems on a classical computer. However, it is not always known when these methods give rise to provably efficient algorithms (BPP or P algorithms).

During the workshop we expect to discuss topics such as

1. Complexity-theoretic classification of quantum Hamiltonian problems. The containment of these problems in complexity classes such as QMA, (Q)AM, BQP, NP, BPP etc.

2. Classical simulation methods for quantum systems. The dependence on spectral gaps, correlation lengths, bounded-entanglement properties of ground-states. The applications of Lieb-Robinson bounds. The use of matrix product states and other  efficient classical representations of quantum states. The use and efficiency of DMRG (density-matrix renormalization group) methods.

3. Relations between classical Markov chains, Hamiltonian problems and quantum adiabatic computation.

4. Entanglement scaling theory in critical and non-critical quantum systems and area laws.

This workshop cosponsored by EUs 6th Framework; the Marie Curie Action SCF (Conferences and Training Courses).