CAREER: Frontiers of Low-Depth Quantum Advantage

Quantum computing is a promising new paradigm for computation that could radically change our understanding of scientific phenomena in fields from medicine to chemistry. An implicit assumption in this claim is that quantum computers are more powerful than the (classical) computers that we have today. Somewhat surprisingly, however, mathematically proving the superiority of quantum computers is a longstanding and challenging question. The quest to prove this "quantum advantage" is not only important from a scientific perspective, but also from an economic one, since building and maintaining quantum computers is both difficult and expensive. This project lays out an ambitious program to methodically strengthen the theoretical foundations of quantum advantage. Namely, the project will develop new techniques to give irrefutable mathematical evidence that there are certain tasks that admit highly parallel quantum algorithms that cannot be parallelized with classical computers. In addition, the project describes a variety of educational initiatives that expand access to quantum computing both at the university level and for researchers outside of academia seeking to understand the theoretical underpinnings of this research program. The project addresses the following theoretical challenges: First, barriers in complexity theory have traditionally prevented claims of unconditional quantum advantage against arbitrary polynomial-time classical computation. Those barriers have not yet been reached in the low-depth setting, but to make progress, new lower bound techniques for models of low-depth classical circuits are required. Second, noise has always been a preeminent concern when scaling quantum experiments, preventing asymptotic quantum advantage in popular experiments such as random circuit sampling. In contrast, random constant-depth quantum circuits may still enjoy an asymptotic quantum advantage against constant-depth classical circuits in the presence of noise. This necessitates a more thorough understanding of the robustness of entanglement at these low depths. Finally, proofs of quantum advantage are often predicated on the structure of the underlying circuit topology. This project will develop concrete characterizations of the topologies that are amenable to these techniques. 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. NSF Award ID: 2543091 | Program: 01002930DB NSF RESEARCH & RELATED ACTIVIT,01002627DB NSF RESEARCH & RELATED ACTIVIT,01003031DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Daniel Grier | Institution: University of California-San Diego, LA JOLLA, CA | Award Amount: $468,145 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2543091 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2543091.html