Quantum computational advantage with polyloglog-depth 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.