Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
We introduce the Diagonal-Clifford-and-Pauli (DCP) stabilizer formalism to precisely characterize intermediate states in non-Clifford quantum error-correction circuits as third-order phase-polynomial states, even with stochastic Pauli noise. This formalism allows for polynomial-time updates of state representations, enabling an exact polynomial-time simulation algorithm for a broad class of circuits including magic state distillation and code switching. Benchmarking with the open-source implementation `merlin` demonstrates significant runtime and memory improvements over existing simulators, particularly for larger logical outputs and complex circuits.
Non-Clifford quantum error correction circuits can be simulated in polynomial time by precisely characterizing their intermediate states as third-order phase-polynomial states within a novel DCP stabilizer formalism.
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.