Spring 2024

Quantum Algorithms, Complexity, and Fault Tolerance

Jan. 9May 10, 2024

Scaling up quantum computers to thousands of high fidelity qubits, demonstrating quantum advantage and implementing fault tolerant qubits are the next major challenges for experimental quantum computing. Theoretical challenges such as the efficiency of protocols for fault-tolerant quantum computation, scalable proofs of quantumness, and 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)

Long-Term Participants (tentative):
Adam Bouland (Stanford University), Bill Fefferman (University of Chicago), Daniel Gottesman (University of Maryland), Jeongwan Haah (Microsoft), Prahladh Harsha (Tata Institute of Fundamental Research), Dakshita Khurana (University of Illinois Urbana-Champaign), Isaac Kim (University of California, Davis), Anand Natarajan (Massachusetts Institute of Technology), Pavel Panteleev (Moscow State University), Anupam Prakash (QC Ware), Yihui Quek (Harvard University and Massachusetts Institute of Technology), Miklos Santha (National University of Singapore), Vinod Vaikuntanathan (Massachusetts Institute of Technology), James Whitfield (Dartmouth College)



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)


Nikolas Breuckmann (University of Bristol), Anthony Leverrier (INRIA)