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 was to bring together leading computer scientists, condensed matter physicists, and mathematicians working on these questions and build upon the existing bridges and collaborations among them. One of the important priorities was to help establish a common language among the three groups so that key insights from all three areas could be pooled in tackling the outstanding issues at the heart of quantum Hamiltonian complexity.

View the monograph produced by S. Gharibian, Y. Huang, Z. Landau, and S. W. Shin in connection with this program.


Umesh Vazirani (UC Berkeley; chair), Dorit Aharonov (Hebrew University of Jerusalem), 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 (Microsoft Research), 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), Jutho Haegeman (Ghent University), 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 at Urbana-Champaign), Carl Miller (University of Michigan), Daniel Nagaj (University of Vienna, Austria), Or Sattath (Hebrew University of Jerusalem), Thomas Vidick (Massachusetts Institute of Technology; Microsoft Research Fellow), Xiaodi Wu (Massachusetts Institute of Technology)

Visiting Graduate Students and Postdocs:

Ning Bao (Stanford University), Paul Christiano (UC Berkeley), Matthew Coudron (Massachusetts Institute of Technology), Ayal Green (Hebrew University of Jerusalem), 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 (MIT)


Wednesday, Jan. 15Saturday, Jan. 18, 2014


Umesh Vazirani (UC Berkeley)
Monday, Feb. 24Friday, Feb. 28, 2014


Dorit Aharonov (Hebrew University of Jerusalem), Thomas Vidick (Massachusetts Institute of Technology; Microsoft Research Fellow), John Watrous (University of Waterloo)
Monday, Mar. 24Thursday, Mar. 27, 2014


Matt Hastings (Microsoft Research), Umesh Vazirani (UC Berkeley)
Monday, Apr. 21Thursday, Apr. 24, 2014


Ignacio Cirac (Max Planck Institute, Garching), Frank Verstraete (University of Vienna)
Monday, May 4Friday, May 8, 2015


Dorit Aharonov (Hebrew University of Jerusalem), Ignacio Cirac (Max Planck Institute, Garching), Umesh Vazirani (UC Berkeley), Frank Verstraete (University of Vienna)

Program image: "Taming the Quantum Tiger" by June Shin ( [at] 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?

Past Internal Program Activities

Wednesday, May 14th, 2:30 pm5:00 pm
Wednesday, April 30th, 2:30 pm5:00 pm
Or Sattath (Simons Institute)
Friday, April 11th, 3:30 pm5:00 pm
Ashwin Nayak (University of Waterloo)
Friday, April 4th, 3:30 pm5:00 pm
Wednesday, April 2nd, 2:30 pm5:00 pm
Friday, March 21st, 3:30 pm5:00 pm
Wednesday, March 19th, 2:30 pm5:30 pm
Tuesday, March 11th, 1:45 pm3:45 pm
Tuesday, March 4th, 2:30 pm5:00 pm
Tuesday, February 18th, 3:15 pm5:00 pm
Tuesday, February 11th, 2:30 pm5:00 pm
Friday, January 31st, 3:30 pm5:00 pm
Tuesday, January 28th, 2:30 pm5:00 pm