UC Berkeley

A fundamental goal of quantum computing is to demonstrate computational advantage over classical computers. Shallow quantum circuits play a central role in this effort as the field transits from the Noisy Intermediate Scale Quantum (NISQ) era to the Early Fault Tolerant era. This thesis describes three lines of research on the theoretical foundation of achieving quantum computational advantage using shallow quantum circuits.

The first is complexity and applications of random circuit sampling (RCS), an experiment at the heart of recent "quantum supremacy" experiments. We describe recent progress in understanding the computational complexity of RCS and its applications in benchmarking noisy quantum devices.

The second is learning algorithms. We give polynomial time algorithms for learning shallow quantum circuits and quantum states prepared by shallow circuits.

The third is fault tolerance. We discuss the prospects of achieving quantum computational advantage using fault tolerance techniques within noisy shallow circuits, and describe two new techniques toward this goal, including fault tolerance against input noise and single-shot logical state preparation.