arXiv:2610.06811
Polynomial-time simulation of non-Clifford quantum error correction
Serban Cercelescu, Mark Koch, Arthur Pesah
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.
AI Summary
The paper asks when noisy non-Clifford error-correction protocols can be simulated exactly in time polynomial in both physical size and logical output count. It studies third-order phase-polynomial (3PP) states: uniform superpositions over affine binary subspaces, with weighted cubic phases modulo eight. These are proved equivalent to states uniquely specified by diagonal-Clifford-and-Pauli (DCP) stabilizers, generalizing Pauli stabilizer states. The framework supports $|0\rangle,|+\rangle$ preparations, Pauli, CNOT and $T$ gates, arbitrary $Z$-type measurements, and compatible $X$-type measurements. Necessary and sufficient compatibility conditions, polynomial-time tests, and conditional-state updates are derived using discrete phase derivatives and DCP tableaux. The phase-polynomial simulator uses $O(n^3)$ bits and $O(mn^3)$ expected time for $m$ operations, excluding classical feedforward. It also provides exact amplitudes and Pauli expectations. A noise-robustness theorem shows that if each ideal $X$ measurement is deterministic or anticommutes with a current $Z$ constraint, compatibility survives arbitrary inserted DCP faults, provided outcome-dependent corrections are DCP. This covers specified distillation, cultivation, gauge-fixing, code-switching and syndrome-extraction constructions. The open-source implementation, `merlin`, is benchmarked on 1,000 attempted shots at noise parameter $10^{-3}$. It shows polynomial scaling with Bravyi–Haah output count and simulates a $[[81,3,5]]$ code-switching circuit where all tested alternatives exhaust memory or fail. Alternatives have lower per-shot costs on single-output examples. Arbitrary $X$ measurements, general adaptive feedforward and several check implementations are not covered; cultivation benchmarks omit escape. DCP decompositions extend to universal simulation but can require exponentially many terms, and arbitrary DCP-state overlaps are not efficiently evaluated.
AI tools were used to edit the text, assist with proofs, and write significant parts of the software package.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.