This reunion workshop is for long-term participants in the program "Quantum Algorithms, Complexity, and Fault Tolerance," held in the spring 2024 semester. It will provide an opportunity to meet old and new friends. Moreover, we hope that it will give everyone a chance to reflect on the progress made during the semester and since, and sketch which directions the field should go in the future. In an effort to keep things informal and to encourage open discussion, none of the activities will be recorded. Participation in the workshop is by invitation only. 

Sample Schedule (see schedule tab for more detail)

9:00-9:30 AM Check-in refreshments

9:30-10:00 AM Talk 1

10:30-11:00 AM AM Break

11:00-12:00 AM Talk 2

12:00-2:00 PM Lunch

2:00-3:00 PM Talk 3

3:00-3:30 PM PM Break

3:30-4:30 PM Talk 4

4:30-5:30 PM Reception (Day 1 only)

If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials. 

Recent developments in quantum algorithms, particularly the 2021 discovery of an apparent exponential quantum speedup for the SIS-infinity problem by filtering, and the 2024 discovery of an apparent exponential quantum speedup for the optimal polynomial intersection problem by decoded quantum interferometry, provide new motivation for the quantum decoding problem. Here, one is given a codeword from a classical error correcting code, which has been subjected to a coherent superposition of symbol-flip errors, and one wishes to recover the original codeword using an efficient quantum circuit. In this workshop we will survey the current state of the art in quantum decoding, present open problems in quantum decoding motivated by algorithmic applications, and then work on these problems together.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials. 

The complexity of ground states of local Hamiltonians is the quantum analog of the theory of NP-Completeness. It features the two most important open questions in quantum complexity theory: the quantum PCP conjecture and the Area Law for 2D gapped Hamiltonians. Recent progress on the first question has been a direct consequence of the discovery of good quantum LDPC codes, while progress on the second question has relied on fault-tolerant polynomials. In a very exciting development, ideas from quantum error correction and quantum complexity theory play an unexpected and deep role in current attempts to understand quantum gravity. These connections even suggest the possibility that quantum gravity could violate the quantum extended Church-Turing thesis. This workshop will bring together researchers from TCS, information and coding theory, mathematics, physics to share recent progress, exchange ideas and make progress on these questions.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials. 

This workshop will bring together researchers from academia and industry to study the capabilities of existing and upcoming quantum computers. Topics will include protocols for characterizing quantum noise, as well as tailoring fault-tolerance protocols to more concrete noise models. The other theme will be proofs of quantumness and other near-term algorithms suitable for such computers, as well as algorithms for scalable fault-tolerant quantum computers.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials. 

Jens Eisert (Free University of Berlin)

Quantifying quantum states' complexity is a key problem in various subfields of science, ranging from quantum computing - where it is closely related to notions of computational complexity - to black-hole physics. In this talk, we discuss notions of circuit complexity from different perspectives. We start from classifying quantum states according to the preparation complexity. The main result presented in the talk is a proof of a prominent conjecture by Brown and Susskind about how random quantum circuits' complexity increases with the depth of the circuit [1].

This workshop will bring together researchers from academia and industry to study the capabilities of existing and upcoming quantum computers. Topics will include protocols for characterizing quantum noise, as well as tailoring fault-tolerance protocols to more concrete noise models. The other theme will be proofs of quantumness and other near-term algorithms suitable for such computers, as well as algorithms for scalable fault-tolerant quantum computers.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials. 

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials. 

The Boot Camp is intended to acquaint program participants with the key themes of the program. It will consist of five mini crash courses, plus a sequence of overview talks as follows:

Mini Crash Courses

Thomas Vidick (Massachusetts Institute of Technology): "Quantum Games and Semi-Definite Programming"
Ashwin Nayak (University of Waterloo): "Quantum Information Theory"
Luca Trevisan (Stanford University): "The Classical PCP Theorem"
Ben Reichardt (University of Southern California): "Quantum Error Correction"
Zeph Landau (UC Berkeley): "Tensor Networks"

Overview Talks

Umesh Vazirani (UC Berkeley): "Introduction to Quantum Hamiltonian Complexity"
Anne Broadbent (University of Waterloo): "Delegated Quantum Computation"
Yaoyun Shi (University of Michigan): "Untrusted Quantum Devices"
Daniel Nagaj (University of Vienna): "Quantum Complexity and Condensed Matter Physics"
Zeph Landau (UC Berkeley): "The Complexity of Ground States"
Aram Harrow (Massachusetts Institute of Technology): "Application of Quantum Information Theory in QHC"
Patrick Hayden (Stanford University): "Quantum Information Measures and Black Holes"
Thomas Vidick (Massachusetts Institute of Technology): "The Quantum PCP Theorem"
Aram Harrow (Massachusetts Institute of Technology): "SDP Hierarchies and Quantum States"
Daniel Nagaj (University of Vienna): "Many-body Physics and Complexity"
John Preskill (California Institute of Technology): "Simulating Quantum Field Theory with a Quantum Computer"

Click here for a set of introductory notes on the field of Quantum Hamiltonian Complexity intended to complement the Boot Camp.