About
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, and the development of quantum algorithms — will be critical to these practical efforts. These themes all figure prominently in this program.
Many of this program's topics 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 also focuses 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 reexamination 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.
