Local Automorphism-Aware Syndrome Compilation for General Quantum LDPC Codes

AI summary

Overview

Research area: Quantum error correction — specifically, scheduling of syndrome-extraction circuits for Calderbank-Shor-Steane (CSS) quantum low-density parity-check (LDPC) codes.

Technical level: Advanced. The paper assumes familiarity with stabilizer/CSS codes, Tanner graphs, edge-coloring, and automorphism groups.

Scope: The paper introduces a symmetry-reduced compilation method (LocalASC) for producing low-depth syndrome-extraction schedules for general CSS quantum LDPC codes, and demonstrates it on two-block CSS codes and quantum Tanner codes.

What This Paper Is About

Measuring the stabilizer checks of a CSS quantum LDPC code requires scheduling many two-qubit gates into layers, and the number of layers is the circuit depth that largely determines how much noise accumulates. A valid schedule must satisfy two different conditions: no qubit may be used in two gates in the same layer (a proper edge-coloring of the code's Tanner graph), and the X-check and Z-check measurements must be interleaved so that the quantum parity constraints hold. The paper's goal is to find schedules with the fewest possible layers while making the search tractable, by exploiting symmetries of the Tanner graph rather than solving the full constraint system edge by edge.

Key Contributions

1. A precise coloring formulation of the scheduling problem. The authors frame low-depth syndrome extraction as a proper ordered edge-coloring subject to quantum parity constraints, and state that the minimum number of colors in such a coloring equals the minimum two-qubit depth when each check is measured with a single ancilla. They make explicit that a proper edge-coloring alone is insufficient: for every pair of overlapping X and Z checks, the number of shared data qubits on which the X interaction precedes the Z interaction must be even.

2. The LocalASC method. Local automorphism-aware syndrome compilation reduces the constraint system to variables attached to edge orbits under a chosen subgroup of the Tanner graph's automorphism group, then lifts any feasible orbit assignment back to a schedule on the full graph.

3. Demonstrations that a known depth lower bound is not universal. Although the 6-layer degree lower bound cannot be attained for the published weight-6 IBM bivariate bicycle codes, the authors show this is not true of all two-block CSS codes. Where the maximum check weight equals the maximum Tanner graph degree, LocalASC finds depth-optimal schedules for several two-block CSS codes with odd component weights, including cases with unequal odd weights, and lower-bound-saturating schedules for several quantum Tanner codes.

4. Constructive symmetry subgroups. To avoid computing the full automorphism group of the Tanner graph, the paper builds translation subgroups for two-block group-algebra CSS codes over abelian groups, and gives conditions under which square-complex symmetries of quantum Tanner codes extend to Tanner graph automorphisms.

Main Findings

• Coloring is necessary but not sufficient: A proper edge-coloring guarantees at most one two-qubit gate per qubit per layer, but valid X/Z interleaving requires the additional even-overlap parity condition on each overlapping check pair.
• Depth equals a chromatic quantity: Under single-ancilla-per-check measurement, the minimum two-qubit depth coincides with the minimum number of colors in a proper ordered edge-coloring satisfying the parity constraints.
• The 6-layer bound is not universal: The impossibility of reaching the degree lower bound for published weight-6 IBM bivariate bicycle codes does not generalize to all two-block CSS codes.
• Depth-optimal schedules found: For code instances where the maximum check weight equals the maximum Tanner graph degree, LocalASC attains depth-optimal schedules for several two-block CSS codes with odd component weights, including unequal odd weights.
• Lower-bound saturation for Tanner codes: Several quantum Tanner codes meeting the same degree condition admit schedules that saturate the lower bound.
• Symmetries can be built, not computed: Usable subgroups for LocalASC can be constructed directly for two-block group-algebra codes over abelian groups, and square-complex symmetries are shown to extend to Tanner graph automorphisms under stated conditions, sidestepping full automorphism-group computation.

Methodology in Plain English

The code is drawn as a graph whose vertices are data and ancilla qubits and whose edges are the two-qubit interactions a check measurement needs. A schedule is an assignment of edges to layers such that no vertex is touched twice in a layer, plus an ordering rule that keeps X and Z measurements from interfering. Solving this directly is expensive because every edge is a separate decision variable.

LocalASC instead picks a set of graph symmetries — transformations that map the graph onto itself while preserving its structure — and groups edges that are equivalent under those symmetries. The solver then works only with these groups (orbits), which is a far smaller problem. Once a feasible assignment of orbits to layers is found, it is expanded back into a concrete schedule covering every edge of the original graph. Because the symmetries must be supplied, the authors show how to write them down explicitly for two families of codes rather than searching for the full automorphism group.

Why This Matters

Research impact: Low-depth syndrome extraction is a central bottleneck for making quantum LDPC codes practical, and this work ties schedule depth to a well-studied combinatorial object (ordered edge-coloring) while showing that symmetry reduction can make the search tractable. It also clarifies when the widely cited degree lower bound is achievable and when it is not.

Real-world applications (as motivated by the problem domain):

• Fault-tolerant quantum memory built on quantum LDPC codes, where shallower extraction directly reduces accumulated noise.
• Compilation and scheduling toolchains for hardware with limited qubit connectivity.
• Evaluation and benchmarking of candidate code families during code design.
• Architectures based on bivariate bicycle and Tanner codes, which are leading candidates for near-term demonstrations.

Industry relevance: The explicit reference to IBM's published bivariate bicycle codes places the work close to industrial roadmaps for qLDPC-based fault tolerance, where automated, symmetry-aware scheduling could become part of a hardware compiler.

Future Directions

• Extending LocalASC to code instances where the maximum check weight does not equal the maximum Tanner graph degree, the condition under which the reported optimality results are obtained.
• Broadening the constructive subgroup machinery beyond abelian-group two-block codes and the square-complex symmetries analyzed for Tanner codes.
• Determining whether stronger lower bounds than the degree bound are needed to certify optimality where the bound is unreachable.
• Assessing scalability and robustness of orbit-based compilation under realistic hardware connectivity and noise, and for codes lacking easily described symmetries.

Target Audience

Quantum error correction researchers and graduate students working on qLDPC codes and fault-tolerant circuit design; quantum compiler and architecture engineers interested in automated syndrome-extraction scheduling; and researchers in algebraic graph theory or combinatorics who want to see edge-coloring and automorphism-group methods applied to quantum hardware constraints.

Authors’ abstract

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.