Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates

Published

January 11, 2026

Author(s)

Jon Nelson, Joel Rajakumar, Dominik Hangleiter, Michael Gullans

Abstract

We construct a polynomial-time classical algorithm that sample from the output distribution of low- depth noisy Clifford circuits with magic-state inputs and final single-qubit measurements in any basis. This class of circuits includes Clifford-magic circuits and Conjugated-Clifford circuits, which are im- portant candidates for demonstrating quantum advantage using non-universal gates. Additionally, our results generalize existing simulation algorithms for IQP circuits to the case of IQP circuits augmented with CNOT gates, which is another class of non-universal circuits that are relevant for current experi- ments. Importantly, our results do not require randomness assumptions over the circuit families consid- ered (such as anticoncentration properties) and instead hold for every circuit in each class. This allows us to place tight limitations on the robustness of these circuits to noise. In particular, we show that in order to achieve quantum advantage at large depths with realistically noisy circuits, one must be able to apply non-Clifford gates mid-circuit even with the ability to prepare perfect magic-states. The key insight behind the algorithm is that interspersed noise causes a decay of long-range entanglement, and at depths beyond a critical threshold, the noise builds up to an extent that most correlations can be clas- sically simulated. To prove our results, we merge techniques from percolation theory with tools from Pauli path analysis.

Proceedings Title

Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

Conference Dates

January 11-14, 2026

Conference Location

Vancouver, CA

Conference Title

ACM-SIAM Symposium on Discrete Algorithms (SODA26)

Pub Type

Conferences

Download Paper

https://doi.org/10.1137/1.9781611978971.50

Local Download

Keywords

quantum computing, quantum error correction, quantum algorithms

Citation

Nelson, J. , Rajakumar, J. , Hangleiter, D. and Gullans, M. (2026), Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, CA, [online], https://doi.org/10.1137/1.9781611978971.50, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=958932 (Accessed May 1, 2026)

Additional citation formats