Scaling up quantum computers to thousands of high fidelity qubits and implementing fault tolerant qubits is the next major challenge for experimental quantum computing. Theoretical challenges such as the efficiency of protocols for fault-tolerant quantum computation, scalable proofs of quantumness, demonstrations of quantum advantage, as well as the development of quantum algorithms, will be critical to these practical efforts. These themes will all figure prominently in our program. 

Many of the topics of this program lie at the intersection of quantum computation and the theory of error correcting codes. For example, recent constructions of quantum low-density parity-check (qLDPC) codes with optimal parameters show exciting potential for a new theory of quantum fault-tolerance. However, many questions remain open, such as the efficiency of decoding algorithms for qLDPC codes, whether qLDPC codes can be locally testable, and how a fault-tolerant protocol can be implemented in a practical setting.

The program will also focus on quantum complexity theory and specifically on quantum Hamiltonian complexity. A central question here is the quantum PCP conjecture, which asks whether properties of many-body systems are hard to approximate. Recent progress on the quantum PCP conjecture has been a direct consequence of breakthroughs in qLDPC codes. Another central question is the Area Law conjecture, which states that ground (and low energy) states of physically relevant quantum systems have low entanglement and can be represented classically. 

Quantum error correction, quantum complexity theory and quantum cryptography are also playing an unexpected role in fundamental physics, namely how to reconcile general relativity with quantum mechanics. The theories of entanglement and quantum error correction have led to progress on these questions, and there are strong indications that quantum computational complexity has a role to play in understanding the breakdown of effective field theory and reconciling the viewpoints of different observers in quantum gravity.

Another focus of this program is to further advance the ongoing revolution at the intersection of quantum computing and the theory of cryptography. One major theme is a re-examination of the foundations of cryptographic protocols in the presence of quantum adversaries. Another is to use a cryptographic leash to allow a classical verifier to carry out protocols with an untrusted quantum computer for tasks such as proofs of quantumness, certifiable randomness, verification of quantum memory, fully homomorphic quantum computation and verification of quantum computation.

Click here to subscribe to our news and events to learn more about this and other events.

Anurag Anshu (Harvard University), Nikolas Breuckmann (University of Bristol), Patrick Hayden (Stanford University), Sandy Irani (UC Berkeley), Urmila Mahadev (California Institute of Technology), Umesh Vazirani (UC Berkeley)

Full Semester Visitors:
Srinivasan Arunachalam (IBM), Adam Bouland (Stanford University), Bill Fefferman (University of Chicago), Prahladh Harsha (TIFR), Robert Huang (California Institute of Technology), Isaac Kim (UC Davis), Aleksander Kubica (AWS Center for Quantum Computing), Chinmay Nirkhe (IBM), James Whitfield (Dartmouth), Henry Yuen (Columbia University), Andrea Coladangelo (University of Washington), Jason Pollack (Syracuse University)

Long-Term Visitors (at least 1 month):
Dorit Aharonov (Hebrew University), Stephen Bartlett (University of Sydney), Ken Brown (Duke University), Earl Campbell (Riverlane and University of Sheffield), Matthew Coudron (University of Maryland), Irit Dinur (Weizmann Institute of Science), Jens Eisert (Free University of Berlin), Joe Emerson (Institute for Quantum Computing), Steve Flammia (AWS Center for Quantum Computing), Alex Grilo (CNRS), Jonas Haferkamp (Harvard University), Nick Hunter-Jones (University of Texas Austin), Rahul Jain (National University of Singapore), Tali Kaufman-Halman (Bar-Ilan University), Iordanis Kerenidis (QC Ware), Tamara Kohler (Universidad Complutense de Madrid), Anthony Leverrier (INRIA), Ashley Montanaro (University of Bristol), Ramis Movassagh (Google), Markus Muller (RWTH Aachen), Anand Natarajan (MIT), Brian O'Gorman (IBM), Pavel Panteleev (Lomonosov Moscow State University), Supartha Podder (Stony Brooks University), Anupam Prakash (QC Ware), Shruti Puri (Yale University), Yihui Quek (Harvard University), Miklos Santha (CNRS Paris and CQT Singapore), Madhu Sudan (Harvard University), Brian Swingle (Brandeis University), Eugene Tang (MIT), Vinod Vaikuntanathan (MIT), Michael Walter (Ruhr University Bochum), Penghui Yao (Nanjing University), Mark Zhandry (NTT Research)

To participate as a long-term visitor, please apply here

About the Quantum Algorithms, Complexity, and Fault Tolerance Boot Camp

The boot camp for this program will be distributed throughout the semester. The boot camp for the Error-Correcting Codes program will include some introductory material on quantum error correcting codes. Also, the first day of each of the three workshops for this program will have introductory material on the topic of the workshop.