Quantum error-correction code and circuit construction is an active field of research, motivating automated methods for identifying equivalent designs. We develop and evaluate automated strategies for deciding whether two descriptions of quantum error-correction codes are equivalent under specified transformations. We formalize permutation equivalence for stabilizer and CSS codes and local-Clifford equivalence for stabilizer codes within a unified framework that separates physical from representation freedom. We develop three decision strategies (group-action search, isomorphism-based methods, and constraint solving), together with invariants and signatures for preprocessing. The empirical evaluation shows that no paradigm dominates across equivalence notions, code families, and parameter ranges. We therefore combine their complementary strengths in input-dependent hybrid checkers following a staged Refute-Refine-Decide architecture. Mean hybrid runtimes remain below 10 s for most evaluated structured-code cases with $n \leq 37$; for inequivalent code instances with $n=144$, they are about 310 s for permutation and 16 s for local-Clifford equivalence.
AI Summary
This paper studies automated equivalence checking for stabilizer-code descriptions: permutation equivalence for general stabilizer and CSS codes, and local-Clifford equivalence for stabilizer codes, without simultaneous qubit permutations. It separates generator-basis and logical-framework freedom from allowed physical transformations. The binary symplectic formulation discards phases, so its permutation-equivalence test additionally identifies codes related by Pauli conjugation.
It implements group-action searches, graph-isomorphism reductions using full stabilizer groups or CSS matroid circuits, and SAT encodings, alongside invariants and coordinate signatures. These are combined into input-dependent “Refute–Refine–Decide” checkers in MQT QECC. Evaluation uses ten seeded randomized instances per sampled parameter setting through $n=47$, plus transformed structured codes, with limits of 1.5 hours and 13 GiB per run. Full-group encodings work best at low stabilizer rank but grow exponentially; SAT covers the broadest evaluated range, although CSS permutation instances can be orders of magnitude slower. An appendix relates this slowdown to unbalanced check ranks and proposes dualizing large check blocks.
Most evaluated structured-code cases through $n=37$ have mean hybrid runtimes below 10 seconds. At $n=144$, inequivalent CSS permutation instances take about 310 seconds and inequivalent local-Clifford instances about 16 seconds; larger equivalent instances frequently time out. The polynomial-time graph-state method applies only for $k<2$, because it cannot accommodate arbitrary logical Clifford freedom otherwise.
The stated principal limitation is sampling bias, especially where inequivalent partners are certified using an invariant. Practical method-selection thresholds are empirical; extensions to joint permutation/local-Clifford equivalence and geometry-preserving transformations remain future work.
Little sign of AI-generated textIncrementalUnclear novelty
Error found: The abstract leaves unspecified that its approximately 310-second permutation-equivalence result for inequivalent 144-qubit instances uses the CSS-specific checker; the general stabilizer permutation checker times out on the corresponding evaluated instances.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Comments
22 pages, 16 main text + 2 references + 4 appendix, 19 figures
Quantum error-correction code and circuit construction is an active field of research, motivating automated methods for identifying equivalent designs. We develop and evaluate automated strategies for deciding whether two descriptions of quantum error-correction codes are equivalent under specified transformations. We formalize permutation equivalence for stabilizer and CSS codes and local-Clifford equivalence for stabilizer codes within a unified framework that separates physical from representation freedom. We develop three decision strategies (group-action search, isomorphism-based methods, and constraint solving), together with invariants and signatures for preprocessing. The empirical evaluation shows that no paradigm dominates across equivalence notions, code families, and parameter ranges. We therefore combine their complementary strengths in input-dependent hybrid checkers following a staged Refute-Refine-Decide architecture. Mean hybrid runtimes remain below 10 s for most evaluated structured-code cases with n≤37; for inequivalent code instances with n=144, they are about 310 s for permutation and 16 s for local-Clifford equivalence.
This paper studies automated equivalence checking for stabilizer-code descriptions: permutation equivalence for general stabilizer and CSS codes, and local-Clifford equivalence for stabilizer codes, without simultaneous qubit permutations. It separates generator-basis and logical-framework freedom from allowed physical transformations. The binary symplectic formulation discards phases, so its permutation-equivalence test additionally identifies codes related by Pauli conjugation.
It implements group-action searches, graph-isomorphism reductions using full stabilizer groups or CSS matroid circuits, and SAT encodings, alongside invariants and coordinate signatures. These are combined into input-dependent “Refute–Refine–Decide” checkers in MQT QECC. Evaluation uses ten seeded randomized instances per sampled parameter setting through n=47, plus transformed structured codes, with limits of 1.5 hours and 13 GiB per run. Full-group encodings work best at low stabilizer rank but grow exponentially; SAT covers the broadest evaluated range, although CSS permutation instances can be orders of magnitude slower. An appendix relates this slowdown to unbalanced check ranks and proposes dualizing large check blocks.
Most evaluated structured-code cases through n=37 have mean hybrid runtimes below 10 seconds. At n=144, inequivalent CSS permutation instances take about 310 seconds and inequivalent local-Clifford instances about 16 seconds; larger equivalent instances frequently time out. The polynomial-time graph-state method applies only for k<2, because it cannot accommodate arbitrary logical Clifford freedom otherwise.
The stated principal limitation is sampling bias, especially where inequivalent partners are certified using an invariant. Practical method-selection thresholds are empirical; extensions to joint permutation/local-Clifford equivalence and geometry-preserving transformations remain future work.
Quantum error-correcting codes (QECC's) are needed to combat the inherent noise affecting quantum processes. Using ZX calculus, we represent QECC's in a form called a ZX diagram, consisting of a tensor network. In this paper, we present canonical forms for CSS codes and CSS states (which are CSS codes with 0 inputs), and we show the resulting canonical forms for the toric code and certain surface codes. Next, we introduce the notion of prime code diagrams, ZX diagrams of codes that have a single connected component with the property that no sequence of rewrite rules can split such a diagram into two connected components. We also show the Fundamental Theorem of Clifford Codes, proving the existence and uniqueness of the prime decomposition of Clifford codes. Next, we tabulate equivalence classes of ZX diagrams under a different definition of equivalence that allows output permutations and any local operations on the outputs. Possible representatives of these equivalence classes are analyzed. This work expands on previous works in exploring the canonical forms of QECC's in their ZX diagram representations.
Verifying whether two quantum circuits are equivalent is a central challenge in the compilation and optimization of quantum programs. We introduce \textsc{Manjushri}, a new automated framework for scalable quantum-circuit equivalence checking. \textsc{Manjushri} uses local projections as discriminative circuit fingerprints, implemented with weighted binary decision diagrams (WBDDs), yielding a compact and efficient symbolic representation of quantum behavior. We present an extensive experimental evaluation that, for random 1D Clifford+T circuits, explores the trade-off between \textsc{Manjushri} and \textsc{ECMC}, a tool for equivalence checking based on a much different approach. \textsc{Manjushri} is much faster up to depth 30 (with the crossover point varying from 39--49, depending on the number of qubits and whether the input circuits are equivalent or inequivalent): when inputs are equivalent, \textsc{Manjushri} is about 10× faster (or more); when inputs are inequivalent, \textsc{Manjushri} is about 8× faster (or more). For both kinds of equivalence-checking outcomes, \textsc{ECMC}'s success rate out to depth 50 is impressive on 32- and 64-qubit circuits: on such circuits, \textsc{ECMC} is almost uniformly successful. However, \textsc{ECMC} struggled on 128-qubit circuits for some depths. \textsc{Manjushri} is almost uniformly successful out to about depth 38, before tailing off to about 75\% at depth 50 (falling to 0\% at depth 48 for 128-qubit circuits that are equivalent). These results establish that \textsc{Manjushri} is a practical and scalable solution for large-scale quantum-circuit verification, and would be the preferred choice unless clients need to check equivalence of circuits of depth $>$38.
Calderbank--Shor--Steane (CSS) codes support decoding and fault-tolerant logical operations through separate pure X and pure Z stabilizer checks. Generator choices and single-qubit Clifford transformations can obscure this structure. We give a deterministic polynomial-time algorithm that decides whether an arbitrary stabilizer code is locally Clifford-equivalent to a CSS code and constructs the required transformation and CSS checks whenever such a form exists. For m possibly redundant generator rows on n qubits, the algorithm uses O(mn2+n4) binary field operations. We reduce the problem to affine linear systems by characterizing local projectors that preserve the span of the binary stabilizer labels. The conversion preserves code parameters and check sparsity for quantum low-density parity-check (qLDPC) codes. We demonstrate CSS recovery and decoder reuse and resolve previously open LC-to-CSS classification questions for published code constructions. For graph states, LC-to-CSS equivalence corresponds to the existence of a bipartite graph in the local-complementation orbit. We derive a necessary-and-sufficient adjacency-matrix criterion for this property and construct such a graph whenever one exists. Our algorithm makes CSS decoding and fault-tolerant constructions accessible throughout the local Clifford equivalence classes of CSS codes.
Quantum circuit equivalence checking is essential for validating compiler optimizations, but its computational cost can vary substantially with circuit structure. We present a structure-aware equivalence checker for unitary quantum circuits based on sparse Pauli propagation. It combines two complementary verification strategies: generator propagation compares the conjugation actions of the circuits on Pauli generators, while Cut-Miter exploits cancellation between circuit products at selected cut points. A structure-aware verification procedure uses circuit characteristics to select between these strategies while explicitly accounting for numerical and approximation errors. We evaluate our framework against three existing equivalence checkers on two benchmark suites containing circuit pairs with up to 512 qubits. Across 434 scored circuit pairs, our framework produces reference-consistent decisions for 96.3% of the pairs without any incorrect verdicts, while the evaluated baselines achieve at most 68.7% reference-consistent decisions. It also achieves the lowest aggregate runtime among the evaluated tools, reducing total runtime by 48.5%--76.0% relative to these baselines. Ablation studies confirm the benefits of cut-based verification, Pauli-term pruning, and bounded propagation attempts. These results indicate that structure-aware sparse Pauli propagation, combined with complementary verification strategies and explicit error accounting, can provide an effective approach to practical quantum circuit equivalence checking.
Formal verification of quantum circuits becomes difficult as circuit size grows because exhaustive reasoning over the Hilbert space is computationally expensive. In previous work [1], we introduced a bit-vector abstraction that separates superposition tracking from basis-state behavior, enabling SMT-based verification of fixed-size error-detection and entanglement circuits built from H, X, and C-NOT gates. This paper extends the framework in five directions. First, we generalise correctness properties to parametrised repetition and concatenated phase-flip codes with up to 101 logical elements. Second, we verify syndrome extraction for CSS codes specified by arbitrary parity-check matrices, including the Steane, [[15,7,3]] Hamming, [[15,1,3]] Reed-Muller, and rotated surface codes with distances up to 101. We consider arbitrary error patterns, detection up to a specified weight, and recovery using a classical decoder, with counterexamples beyond each code's correction or detection capability. Third, we characterize the {H,X,C-NOT} fragment for which the abstraction faithfully represents Hilbert-space semantics. We prove soundness, demonstrate necessity with counterexamples, validate the characterisation against state-vector simulation, and prove the six lemmas from the original work. Fourth, a mutation study using 13 operators identifies equivalent mutants and detects all 622 non-equivalent mutants within the evaluated fault model. Fifth, a direct Z3 implementation verifies GHZ circuits with up to 262,144 qubits across three topologies on a 16GB laptop. Random H+C-NOT networks show verification cost rises sharply with depth when outputs depend on many inputs. The approach does not target general stabilizer circuits, Y-type stabilizers, fault-tolerant protocols, or physical noise; we identify extensions needed to address these cases.
Abstract We introduce a high-level graphical framework for designing and analysing quantum error correcting codes, centred on what we term the coherent parity check (CPC). The graphical formulation is based on the diagrammatic tools of the ZX-calculus of quantum observables. The resulting framework leads to a construction for stabilizer codes that allows us to design and verify a broad range of quantum codes based on classical ones, and that gives a means of discovering large classes of codes using both analytical and numerical methods. We focus in particular on the smaller codes that will be the first used by near-term devices. We show how CSS codes form a subset of CPC codes and, more generally, how to compute stabilizers for a CPC code. As an explicit example of this framework, we give a method for turning almost any pair of classical [ n , k , 3 ] codes into a [ [ 2 n − k + 2 , k , 3 ] ] CPC code. Further, we give a simple technique for machine search which yields thousands of potential codes, and demonstrate its operation for distance 3 and 5 codes. Finally, we use the graphical tools to demonstrate how Clifford computation can be performed within CPC codes. As our framework gives a new tool for constructing small- to medium-sized codes with relatively high code rates, it provides a new source for codes that could be suitable for emerging devices, while its ZX-calculus foundations enable natural integration of error correction with graphical compiler toolchains. It also provides a powerful framework for reasoning about all stabilizer quantum error correction codes of any size.