A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits

Quantum computers hold the promise of solving certain problems much faster than classical computers, but real devices are unavoidably affected by noise. This raises a central question: Does noise place a fundamental limit on how much of an advantage quantum computers can achieve? Working in collaboration with researchers at the University of Colorado Boulder, Dr. Thomas Schuster (now a Sherman Fairchild Postdoctoral Scholar at Caltech) and Prof. Norman Yao have taken a significant step toward answering this question by developing a classical algorithm that can efficiently simulate noisy quantum circuits. Their work was featured on the cover of Physical Revew X  and demonstrates that noise restricts quantum computational power more severely and more generally than was previously recognized:

Thomas Schuster, Chao Yin, Xun Gao, and Norman Y. Yao, "A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits," Phys. Rev. X 15, 041018 (2025). DOI: https://doi.org/10.1103/xct1-7kf2.

When asked about this work, Dr. Schuster explains: “Our method computes the expectation value of any observable for any circuit, with only a small average error when input states are sampled from ensembles such as the computational basis. The key idea is that noise strongly suppresses nonlocal quantum correlations while leaving local ones more intact, making the overall system easier to approximate classically. Our results go well beyond earlier work, which focused only on narrow tasks such as random circuit sampling.”

Although the work establishes strict limits on quantum advantage in noisy systems, there are important caveats. The algorithm becomes inefficient as the noise level decreases, so it does not rule out advantages at levels reached in state-of-the-art experiments. Moreover, it does not apply to error-corrected quantum computations, which can in principle overcome noise entirely. Moving forward, extending this framework to more realistic thermal noise models and to the broader complexity of quantum dynamics may reveal even deeper insights into the boundary between classical and quantum computational power.