Quantum Computational Advantage with Polyloglog-Depth Noisy Circuits

Explore quantum computational advantage through a conference talk examining fault-tolerant quantum protocols with polylogarithmic depth overhead in noisy circuit environments. Learn about a fully-quantum fault tolerance protocol that operates without assumptions of noiseless auxiliary classical computation and adaptivity, representing a significant advancement in quantum error correction. Discover how classical fault tolerance techniques can be incorporated to enhance existing protocols, specifically building upon the work of Nguyen and Pattison. Understand the application of these methods to constant-depth IQP (Instantaneous Quantum Polynomial-time) circuits and examine the complexity-theoretic implications that demonstrate superpolynomial quantum advantage in sampling from noisy quantum circuits with polylogarithmic depth. Gain insights into the intersection of quantum algorithms, complexity theory, and fault tolerance through this technical presentation delivered at the Simons Institute's Quantum Algorithms, Complexity, and Fault Tolerance Reunion.