FET: Medium: Quantum Algorithms, Complexity, Testing and Benchmarking

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

This is an exciting time in quantum computation, with computational ideas poised to play an even larger role in guiding the enormous investment in experimental realization of quantum computers, as well as in foundational questions in cryptography, complexity theory, condensed matter physics and quantum gravity. This project includes robust plans for exploring these issues, including the testing and benchmarking of near-term quantum computers, foundational questions at the intersection of cryptography and quantum, the complexity of ground states of local Hamiltonians and quantum probabilistically checkable proof (PCP), and the interplay between quantum gravity and ideas from quantum complexity and cryptography. The presented research will deepen an already active interaction between the theory of quantum computing and experimental and theoretical physics, as well as with classical complexity theory and cryptography. It will bring the computational lens to bear on some of the most fundamental questions in condensed matter physics and quantum gravity. This project presents two different threads. The first explores computational questions about verification and benchmarking of near-term quantum computers. This includes studying the complexity of (and algorithms for) Random Circuit Sampling, which was the basis of Google’s “quantum supremacy” experiment, and formulating a theoretically sound but achievable goal for the next generation of quantum processors. And it includes developing some of the basic primitives for benchmarking quantum computers. The second thread is more foundational and explores a number of themes including: i) Fundamental questions in Quantum Hamiltonian Complexity, including the quantum PCP conjecture and whether ground states of certain 2D Hamiltonians have succinct classical representations as projected entangled-pair states (PEPS). ii) Re-examining the basic primitives of cryptography in the context of quantum computation. iii) The deep relationship between quantum gravity and complexity theory and cryptography, including questions about whether the quantum extended Church-Turing thesis is false in quantum gravity, how to formalize the general notion of efficient computation in quantum gravity, and connections between cryptography and the nature of Bekenstein-Hawking radiation. The Principal Investigator will update and continue teaching Massive Open Online Course (MOOC) class named "Quantum mechanics and quantum computation" that has already reached tens of thousands of students worldwide. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.