Polynomial-time simulation of non-Clifford quantum error correction

Abstract

We show that every intermediate state of a broad class of non-Clifford quantum error-correction circuits is a third-order phase-polynomial state, even under stochastic Pauli noise. The class includes magic state distillation and cultivation, code switching and gauge fixing, transversal non-Clifford gates with syndrome extraction, and injection of diagonal magic states. Third-order phase-polynomial states strictly generalize stabilizer states, and we prove that they are exactly the stabilizer states of the diagonal-Clifford-and-Pauli (DCP) stabilizer formalism that we introduce. We characterize these states and show that their representations can be updated in polynomial time. This yields an exact polynomial-time simulation algorithm for these circuits and, more broadly, a framework for reasoning about their internal states and about magic states in general. We provide an open-source implementation, \texttt{merlin}, and benchmark it against existing non-Clifford simulators on distillation, cultivation, and code switching circuits. The benchmarks demonstrate improved runtime and memory scaling as the number of logical outputs grows in Bravyi-Haah distillation, and simulation of a code switching circuit beyond the reach of all other tested simulators.

Bosonic quantum error correction with microwave cavities for quantum repeaters
S. Siddardha Chelluri, Sanchar Sharma, Frank Schmidt +2
Physical Review A21 Jul 2026Peer-reviewedLicence not statedFull textQuantum physics & quantum informationHAL
Error-Correction Transitions in Finite-Depth Quantum Channels
Arman Sauliere, Guglielmo Lami, Pedro Ribeiro +2
Physical Review Letters16 Sep 2026Peer-reviewedLicence not statedGeneral physicsHAL
Decoder- and Noise-Aware Optimization Framework for Clifford-Deformed Quantum Error-Correcting Codes
Julius Rye Bønnelykke, Benjamin Joecker, Peter Krogstrup +2
arXiv9 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
clifford_qc: A Python Toolkit for Quantum Simulation
Ginanjar Utama, Hermawan Kresno Dipojono
arXiv18 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Quantum quenches of scar states in the Affleck-Kennedy-Lieb-Tasaki model via Clifford augmented tensor network simulation
Azar C. Nakhl, Ben Harper, Muhammad Usman +1
arXiv28 Oct 2026PreprintCC BY 4.0Full textCondensed matter Quantum physics & quantum informationarXiv

Cite

BibTeX RIS

BibTeX

@misc{cercelescu2026polynomialtime,
  title = {{Polynomial-time simulation of non-Clifford quantum error correction}},
  author = {Serban Cercelescu and Mark Koch and Arthur Pesah},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.06811},
  eprint = {2610.06811},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.06811},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Polynomial-time simulation of non-Clifford quantum error correction
AU  - Serban Cercelescu
AU  - Mark Koch
AU  - Arthur Pesah
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.06811
UR  - https://arxiv.org/abs/2610.06811
AB  - We show that every intermediate state of a broad class of non-Clifford quantum error-correction circuits is a third-order phase-polynomial state, even under stochastic Pauli noise. The class includes magic state distillation and cultivation, code switching and gauge fixing, transversal non-Clifford gates with syndrome extraction, and injection of diagonal magic states. Third-order phase-polynomial states strictly generalize stabilizer states, and we prove that they are exactly the stabilizer states of the diagonal-Clifford-and-Pauli (DCP) stabilizer formalism that we introduce. We characterize these states and show that their representations can be updated in polynomial time. This yields an exact polynomial-time simulation algorithm for these circuits and, more broadly, a framework for reasoning about their internal states and about magic states in general. We provide an open-source implementation, \texttt{merlin}, and benchmark it against existing non-Clifford simulators on distillation, cultivation, and code switching circuits. The benchmarks demonstrate improved runtime and memory scaling as the number of logical outputs grows in Bravyi-Haah distillation, and simulation of a code switching circuit beyond the reach of all other tested simulators.
ER  -

Abstract

Related

Cite