Low-depth syndrome extraction for Calderbank-Shor-Steane (CSS) quantum low-density parity-check codes can be formulated as a proper ordered edge-coloring problem subject to quantum parity constraints. A proper edge-coloring of the CSS Tanner graph ensures that each data or ancilla qubit participates in at most one two-qubit gate per layer, but does not guarantee a valid interleaving of the X- and Z-check measurements as for every overlapping X/Z check pair, the number of shared data qubits on which the X interaction precedes the Z interaction must be even. The minimum number of colors in a proper ordered edge-coloring satisfying the quantum parity constraints equals the minimum two-qubit depth when each stabilizer check is measured with a single ancilla.
We introduce local automorphism-aware syndrome compilation (LocalASC), which reduces the constraint system to edge-orbit variables under a subgroup of the Tanner graph automorphisms and lifts each feasible orbit assignment to the full graph. Although the $6$-layer degree lower bound is unattainable for the published weight-$6$ IBM bivariate bicycle codes, we show that this is not universal among two-block CSS codes. Among code instances for which the maximum check weight equals the maximum Tanner graph degree, LocalASC finds depth-optimal syndrome-extraction schedules for several two-block CSS codes with odd component weights, including instances with unequal odd weights. We also obtain lower-bound-saturating syndrome-extraction schedules for several quantum Tanner codes satisfying the same degree condition. To obtain the subgroups used by LocalASC without computing the full automorphism group of the Tanner graph, we construct translation subgroups for two-block group-algebra CSS codes over abelian groups. For quantum Tanner codes, we give conditions under which square-complex symmetries extend to Tanner graph automorphisms.
AI Summary
The paper studies minimum-two-qubit-depth syndrome extraction for fixed CSS parity-check matrices in the standard single-ancilla-per-check model. It expresses scheduling as ordered edge coloring of the Tanner graph: incident edges need distinct layers, and each overlapping $X/Z$ check pair requires even parity of the shared-qubit interactions ordered $X$ before $Z$. The resulting quantum-constrained edge chromatic number equals the minimum scheduling depth and is bounded below by the maximum Tanner degree $\Delta$.
LocalASC restricts schedules to those constant on edge orbits of a vertex-class-preserving automorphism subgroup. It solves the reduced constraint problem using CP-SAT, retains all original ordering constraints, and independently verifies the lifted schedule. Subgroups can come from generic graph-automorphism routines or construction-specific translations and square-complex symmetries.
For 18 selected two-block and quantum Tanner instances, LocalASC finds schedules saturating $\Delta=w$, with depths $6,8,9,$ or $12$ and runtimes at most 11 seconds. Unreduced ASC finds no schedule within 30 minutes for eight instances. Results include depth-8 schedules for unequal component weights $(3,5)$. A separate 1,225-qubit Tanner instance attains depth $\Delta=14>w=12$ in 309 seconds. Circuit-noise simulations report lower estimated logical error rates for selected schedules on two benchmark codes.
Orbit-model infeasibility excludes only subgroup-invariant schedules. The results depend on the measured generator presentation, and minimum depth does not guarantee distance preservation or favorable hook propagation. Logical-error comparisons use filtered schedules; circuit-distance searches provide upper bounds rather than certificates.
Little sign of AI-generated textIncremental
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Low-depth syndrome extraction for Calderbank-Shor-Steane (CSS) quantum low-density parity-check codes can be formulated as a proper ordered edge-coloring problem subject to quantum parity constraints. A proper edge-coloring of the CSS Tanner graph ensures that each data or ancilla qubit participates in at most one two-qubit gate per layer, but does not guarantee a valid interleaving of the X- and Z-check measurements as for every overlapping X/Z check pair, the number of shared data qubits on which the X interaction precedes the Z interaction must be even. The minimum number of colors in a proper ordered edge-coloring satisfying the quantum parity constraints equals the minimum two-qubit depth when each stabilizer check is measured with a single ancilla.
We introduce local automorphism-aware syndrome compilation (LocalASC), which reduces the constraint system to edge-orbit variables under a subgroup of the Tanner graph automorphisms and lifts each feasible orbit assignment to the full graph. Although the 6-layer degree lower bound is unattainable for the published weight-6 IBM bivariate bicycle codes, we show that this is not universal among two-block CSS codes. Among code instances for which the maximum check weight equals the maximum Tanner graph degree, LocalASC finds depth-optimal syndrome-extraction schedules for several two-block CSS codes with odd component weights, including instances with unequal odd weights. We also obtain lower-bound-saturating syndrome-extraction schedules for several quantum Tanner codes satisfying the same degree condition. To obtain the subgroups used by LocalASC without computing the full automorphism group of the Tanner graph, we construct translation subgroups for two-block group-algebra CSS codes over abelian groups. For quantum Tanner codes, we give conditions under which square-complex symmetries extend to Tanner graph automorphisms.
The paper studies minimum-two-qubit-depth syndrome extraction for fixed CSS parity-check matrices in the standard single-ancilla-per-check model. It expresses scheduling as ordered edge coloring of the Tanner graph: incident edges need distinct layers, and each overlapping X/Z check pair requires even parity of the shared-qubit interactions ordered X before Z. The resulting quantum-constrained edge chromatic number equals the minimum scheduling depth and is bounded below by the maximum Tanner degree Δ.
LocalASC restricts schedules to those constant on edge orbits of a vertex-class-preserving automorphism subgroup. It solves the reduced constraint problem using CP-SAT, retains all original ordering constraints, and independently verifies the lifted schedule. Subgroups can come from generic graph-automorphism routines or construction-specific translations and square-complex symmetries.
For 18 selected two-block and quantum Tanner instances, LocalASC finds schedules saturating Δ=w, with depths 6,8,9, or 12 and runtimes at most 11 seconds. Unreduced ASC finds no schedule within 30 minutes for eight instances. Results include depth-8 schedules for unequal component weights (3,5). A separate 1,225-qubit Tanner instance attains depth Δ=14>w=12 in 309 seconds. Circuit-noise simulations report lower estimated logical error rates for selected schedules on two benchmark codes.
Orbit-model infeasibility excludes only subgroup-invariant schedules. The results depend on the measured generator presentation, and minimum depth does not guarantee distance preservation or favorable hook propagation. Logical-error comparisons use filtered schedules; circuit-distance searches provide upper bounds rather than certificates.
Syndrome extraction for a CSS code has depth at least the Tanner-graph degree Δ, attained by edge colouring if gate order is ignored; correctness adds a parity constraint. We prove three general obstructions to depth-Δ extraction and show that, for every two-block group-algebra code with weight-three polynomials whose checks overlap in at most two qubits, no correct single-round circuit with one ancilla per check and one CNOT per Tanner edge has depth six: the minimum is seven, so the seven-layer cycle of Bravyi \emph{et al.} is optimal for their seven bivariate bicycle codes. This is the first analytic, family-wide impossibility result, extending prior instance-specific solver-based infeasibility results. The hypothesis cannot be dropped: a single orbit of four-qubit overlaps with a collision element of even order and 2-height at most eight makes depth six attainable, and a [[72,8,6]] code of this kind has a verified six-layer circuit. The refutations carry DRAT certificates. As a further application of the same scheduling scheme, we construct Stab-QRAM, a quantum random access memory for affine Boolean data that uses only CNOT and X gates and has the minimum depth possible for this gate set.
Quantum error correcting codes (QECC) are essential for constructing large-scale quantum computers that deliver faithful results. As strong competitors to the conventional surface code, quantum low-density parity-check (qLDPC) codes are emerging rapidly: they offer high encoding rates while maintaining reasonable physical-qubit connectivity requirements. Despite the existence of numerous code constructions, a notable gap persists between these designs -- some of which remain purely theoretical -- and their circuit-level deployment.
In this work, we propose Auto-Stabilizer-Check (ASC), a universal compilation framework that generates depth-optimal syndrome extraction circuits for arbitrary qLDPC codes. ASC leverages the sparsity of parity-check matrices and exploits the commutativity of X and Z stabilizer measurement subroutines to search for optimal compilation schemes. By iteratively invoking an SMT solver, ASC returns a depth-optimal solution if a satisfying assignment is found, and a near-optimal solution in cases of solver timeouts. Notably, ASC provides the first definitive answer to one of IBM's open problems: for all instances of bivariate bicycle (BB) code reported in their work, our compiler certifies that no depth-6 syndrome extraction circuit exists.
Furthermore, by integrating ASC with an end-to-end evaluation framework -- one that assesses different compilation settings under a circuit-level noise model -- ASC reduces circuit depth by approximately 50% and achieves an average 7x-8x suppression of the logical error rate for general qLDPC codes, compared with as-soon-as-possible (ASAP) and coloration-based scheduling. ASC thus substantially reduces manual design overhead and demonstrates its strong potential to serve as a key component in accelerating hardware deployment of qLDPC codes.
Quantum low-density parity-check (qLDPC) codes offer a promising route to scalable fault-tolerant quantum computing, but their practical implementation requires efficient circuits for syndrome extraction. Many qLDPC families are assembled from a small set of components through explicit operations that imprint edge symmetries on their Tanner graphs. We show that disassembling the code by quotienting its symmetries one at a time, reduces parity-check circuit design to a much smaller problem acting only on the underlying components. Solutions to the reduced problem can then be lifted to the full code, yielding circuit constructions that apply to entire families of codes built from the same components. For lifted-product codes, our approach provides an optimal analytical construction for parity-check circuits achieving the lower bound on CNOT depth. We obtain analogous constructions for balanced-product codes and quantum--classical homological product codes. For quantum Tanner codes, the reduced problem is small enough to solve numerically, reaching the CNOT-depth lower bound for nearly all instance tested, including codes with up to 576 data qubits.
The realization of quantum error correction protocols whose logical error rates are suppressed far below physical error rates relies on an intricate combination: the error-correcting code's efficiency, the syndrome extraction circuit's fault tolerance and overhead, the decoder's quality, and the device's constraints, such as physical qubit count and connectivity. This work makes two contributions towards error-corrected quantum devices. First, we introduce mirror codes, a simple yet flexible construction of LDPC stabilizer codes parameterized by a group G and two subsets of G whose total size bounds the check weight. These codes contain all abelian two-block group algebra codes, such as bivariate bicycle (BB) codes. At the same time, they are manifestly not CSS in general, thus deviating substantially from most prior constructions. Fixing a check weight of 6, we find [[60,4,10]],[[36,6,6]],[[48,8,6]], and [[85,8,9]] codes, all of which are not CSS; we also find several weight-7 codes with kd>n.
Next, we construct syndrome extraction circuits that trade overhead for provable fault tolerance. These circuits use 1-2, 3, and 6 ancillae per check, and respectively are partially fault-tolerant (FT), provably FT on weight-6 CSS codes, and provably FT on \emph{all} weight-6 stabilizer codes. Using our constructions, we perform end-to-end quantum memory experiments on several representative mirror codes under circuit-level noise. We achieve an error pseudothreshold on the order of 0.2%, approximately matching that of the [[144,12,12]] BB code under the same model. These findings position mirror codes as a versatile candidate for fault-tolerant quantum memory, especially on smaller-scale devices in the near term.
This paper develops a two-branch multiplicative-coset construction for regular Calderbank--Shor--Steane (CSS) quantum low-density parity-check base matrices. For a target column weight J and an even row weight L, the method reduces regularity, CSS orthogonality, and same-type 4-cycle exclusion to explicit quotient-coset conditions over a finite field. A normalized exhaustive search for these conditions produces base matrices for several (J,L) pairs, so the construction is not tied to a single degree distribution. The construction separates the finite-length design into two stages: the base matrix fixes the degree distribution and the first girth constraints, and a cyclic lift randomizes edge connections subject to exact algebraic checks. As a detailed example, we carry one (3,10)-regular base through the lift and decoding stages. For this example, the selected 64-fold lift gives a code whose same-type Tanner graphs have girth at least eight, and it also excludes a specified weight-16 nondegenerate logical-support orbit. Complete support enumeration excludes all nontrivial logical representatives of weight at most 16 on both sides. The resulting instance is a [[10240,4108,18≤d≤32]] CSS code. For decoding, we use joint log-domain belief propagation together with low-complexity deterministic post-processing rules for small residual syndromes, including repairs for residual patterns with two unsatisfied checks. The frame error rate (FER) measurements provide finite-length decoding data for this detailed example; at depolarizing probability p=0.058, the post-processing FER is 1.0×10−7.
Quantum low-density parity-check (QLDPC) codes provide a practical balance between error-correction capability and implementation complexity in quantum error correction (QEC). In this paper, we propose an algebraic construction based on dyadic matrices for designing both classical and quantum LDPC codes. The method first generates classical binary quasi-dyadic LDPC codes whose Tanner graphs have girth 6. It is then extended to the Calderbank-Shor-Steane (CSS) framework, where the two component parity-check matrices are built to satisfy the compatibility condition required by the recently introduced CAMEL-ensemble quaternary belief propagation decoder. This compatibility condition ensures that all unavoidable cycles of length 4 are assembled in a single variable node, allowing the mitigation of their detrimental effects by decimating that variable node.