Programs | Spring 2014Quantum Hamiltonian Complexity

13 January to 16 May, 2014

Quantum Hamiltonian complexity is an exciting area combining deep questions and techniques from both quantum complexity theory and condensed matter physics. The connection between these fields arises from the close relationship between their defining questions: the complexity of constraint satisfaction problems in complexity theory and the properties of ground states of local Hamiltonians in condensed matter theory. At one end of the spectrum, quantum Hamiltonian complexity expands the scope of computational complexity theory in new directions by asking three fundamental questions:

  • Can ground states of “natural” quantum systems be described succinctly?
  • Does the exponential complexity of general quantum systems persist at high temperature?
  • Is the scientific method sufficiently powerful to understand general quantum systems?

Each of these questions can be formulated as a precise computational question. The first question translates to a beautiful conjecture in condensed matter theory called the area law, which states that the ground state of any local Hamiltonian satisfies the property that the entanglement entropy across any cut is bounded by the edge expansion of the cut. The second question can be formalized as asking whether the quantum analog of the PCP theorem is true. And the third question can be formulated in terms of the power of the interactive proof system with a polynomial time quantum prover interacting with a classical polynomial time verifier.

At the other end of the spectrum, quantum Hamiltonian complexity provides new approaches and techniques for tackling fundamental questions in condensed matter physics, in particular the classical simulation of quantum many body systems. The area law plays a central role in recent progress on using tensor network based techniques for simulating such systems. The goal of this semester long program is to bring together leading computer scientists, condensed matter physicists and mathematicians working on these questions, and to build upon the existing bridges and collaborations between them. One of the important priorities will be to help establish a common language between the three groups, so that key insights from all three areas can be pooled in tackling the outstanding issues at the heart of quantum Hamiltonian complexity.

Organizers:

Umesh Vazirani (UC Berkeley; chair), Dorit Aharonov (Hebrew University, Jerusalem), Matt Hastings (Duke University and Station Q), Frank Verstraete (University of Vienna).

Long-Term Participants (in addition to Organizers):

Itai Arad (CQT, Singapore), Michael Ben-Or (Hebrew University, Jerusalem), Fernando Brandao (UFMG, Brazil), Anne Broadbent (Waterloo), Ignacio Cirac (Max Planck Institute, Garching), Jens Eisert (FU Berlin), Joe Fitzsimmons (CQT, Singapore), Daniel Gottesman (Perimeter Institute), Jeongwan Haah (MIT), Sandy Irani (UC Irvine), Elham Kashefi (University of Edinburgh), Zeph Landau (UC Berkeley), Roderich Moessner (ENS Paris), Ashwin Nayak (Waterloo), Ben Reichardt (University of Southern California), Norbert Schuch (RWTH Aachen), Leonard Schulman (Caltech), Yaoyun Shi (University of Michigan), Brian Swingle (Harvard), Mario Szegedy (Rutgers), Andy Yao (Tsinghua University).

Research Fellows:

Sevag Gharibian (UC Berkeley), Alexandra Kolla (UIUC), Carl Miller (University of Michigan), Daniel Nagaj (University of Vienna), Or Sattath (Hebrew University, Jerusalem), Thomas Vidick (MIT), Xiaodi Wu (University of Michigan).

Workshops:

During the semester there will be three workshops spanning the topics of the program, as well as a Boot Camp designed to acquaint participants with key material early in the semester. These are planned as follows:

  • Boot Camp : January 13-17, 2014.
    Organizers: Umesh Vazirani (UC Berkeley).
  • Workshop 1 : "Quantum Games and Protocols." February 24-28, 2014.
    Organizers: Dorit Aharonov (Hebrew University, Jerusalem), Thomas Vidick (MIT).
  • Workshop 2: "Complexity Meets Condensed Matter." March 24-28, 2014.
    Organizers: Matt Hastings (Duke University and Station Q), Umesh Vazirani (UC Berkeley).
  • Workshop 3 : "Tensor Networks and Simulations." April 21-25, 2014.
    Organizers: Ignacio Cirac (MPI, Garching), Frank Verstraete (University of Vienna).

Participation:

Those interested in participating in this program should send email to the organizers at this address.