Spring 2014

Quantum Hamiltonian Complexity

Jan. 13May 16, 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 an interactive proof system with a polynomial time quantum prover interacting with a polynomial time classical 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.

Click here to subscribe to our announcements email list for this program.

Umesh Vazirani (UC Berkeley; chair), Dorit Aharonov (Hebrew University of Jerusalem), Matt Hastings (Microsoft Research), Frank Verstraete (University of Vienna).
Long-Term Participants (including Organizers): 
Scott Aaronson (Massachusetts Institute of Technology), Dorit Aharonov (Hebrew University of Jerusalem), Bela Bauer (Microsoft Research, Station Q), Michael Ben-Or (Hebrew University of Jerusalem), Fernando Brandao (University College London), Anne Broadbent (University of Ottawa), Xie Chen (UC Berkeley), Giulio Chiribella (Tsinghua University), Ignacio Cirac (Max Planck Institute, Garching), Jens Eisert (FU Berlin), Joe Fitzsimons (Singapore University of Technology and Design and the Centre for Quantum Technologies), Raúl García-Patrón Sánchez (Université Libre de Bruxelles), Daniel Gottesman (Perimeter Institute), Jeongwan Haah (Massachusetts Institute of Technology), Patrick Hayden (Stanford University), Sandy Irani (UC Irvine), Rahul Jain (National University of Singapore), Iordanis Kerenidis (LIAFA), Guy Kindler (Hebrew University of Jerusalem), Zeph Landau (UC Berkeley), Anthony Leverrier (INRIA Rocquenfort), Dana Moshkovitz (Massachusetts Institute of Technology), Ashwin Nayak (University of Waterloo), Sandu Popescu (University of Bristol), Ben Reichardt (University of Southern California), Norbert Schuch (RWTH Aachen), Leonard Schulman (California Institute of Technology), Yaoyun Shi (University of Michigan), Jamie Sikora (LIAFA), Brian Swingle (Harvard University), Mario Szegedy (Rutgers University), Umesh Vazirani (UC Berkeley; chair), Frank Verstraete (University of Vienna), Ashvin Vishwanath (UC Berkeley), Andrew Yao (Tsinghua University), Jon Yard (Microsoft Research, Station Q).
Research Fellows: 
Sevag Gharibian (UC Berkeley), Alexandra Kolla (University of Illinois, Urbana-Champaign), Carl Miller (University of Michigan), Daniel Nagaj (University of Vienna, Austria), Or Sattath (Hebrew University of Jerusalem), Thomas Vidick (California Institute of Technology; Microsoft Research Fellow), Xiaodi Wu (Massachusetts Institute of Technology).
Visiting Graduate Students: 
Ning Bao (Stanford University), Paul Christiano (UC Berkeley), Matthew Coudron (Massachusetts Institute of Technology), Ayal Green (Hebrew University of Jerusalem), Jutho Haegeman (Ghent University), Urmila Mahadev (UC Berkeley), Attila Pereszlényi (Centre for Quantum Technologies, Singapore), Anupam Prakash (UC Berkeley), Seung Woo Shin (UC Berkeley), Guoming Wang (UC Berkeley), Yixin Xu (Rutgers University), Henry Yuen (Massachusetts Institute of Technology).


Jan. 15Jan. 18, 2014
Organizers: Umesh Vazirani (UC Berkeley)
Feb. 24Feb. 28, 2014
Organizers: Dorit Aharonov (Hebrew University of Jerusalem), Thomas Vidick (California Institute of Technology; Microsoft Research Fellow), John Watrous (University of Waterloo)
Mar. 24Mar. 27, 2014
Organizers: Matt Hastings (Microsoft Research), Umesh Vazirani (UC Berkeley)
Apr. 21Apr. 24, 2014
Organizers: Ignacio Cirac (Max Planck Institute, Garching), Frank Verstraete (University of Vienna)

Those interested in participating in this program should send email to the organizers qhc [at] lists [dot] simons [dot] berkeley [dot] edu (at this address.)

Program image: "Taming the Quantum Tiger" by June Shin (juneshin [dot] design [at] gmail [dot] com). Quantum computation teaches us that a quantum system is better visualized as a wild tiger than as a docile Schrödinger's cat. Can we tame the exponential power of quantum systems by classically controlling, analyzing and simulating them?