Breakthrough in Quantum Computing: Achieving Advantage with Ultra-Deep Noisy Circuits 🧠

Quynh Nguyen (Harvard University)
https://simons.berkeley.edu/talks/quynh-nguyen-harvard-university-2025-05-28
Quantum Algorithms, Complexity, and Fault Tolerance Reunion

In the standard local stochastic noise model, we construct a fully-quantum fault tolerance protocol with polyloglog depth overhead (and polylog-space). Our protocol is fully quantum in the sense that it does not assume noiseless auxiliary classical computation and adaptivity. The main component in our construction is a procedure of incorporating classical fault tolerance to remove these assumptions from a current protocol of Nguyen and Pattison. When applied to constant-depth IQP circuits, this allows us to conclude (under complexity-theoretic assumptions) that sampling from noisy quantum circuits of polyloglog-depth gives a superpolynomial quantum advantage.