PaperlayerView exact revision on arXiv

Source-linked AI summary

Local Automorphism-Aware Syndrome Compilation for General Quantum LDPC Codes

Eugenio Durazo Rocha, Olai Å. Mostad, Hsuan-Yin Lin, Eirik Rosnes

arXiv:2609.40319v1quant-phcs.ITmath.IT

TL;DR

CSS syndrome extraction must schedule gates without collisions while also respecting parity constraints on overlapping X- and Z-check interactions. The paper reduces this constraint system through Tanner-graph automorphisms, finding depth-optimal schedules for multiple two-block and quantum Tanner code instances where the degree bound applies.

  • Problem

    Proper edge coloring prevents gate collisions but does not ensure valid X/Z interaction ordering, and the Tanner-degree lower bound can be unattainable for some codes.

    Source: §I · p. 1, §III · p. 5

  • Method

    LocalASC assigns one tick variable per Tanner-graph edge orbit under a selected automorphism subgroup, retains all QCEC constraints, and lifts feasible assignments to the full graph.

    Source: §I · p. 1

  • Results

    For 18 measured-PCM pairs, LocalASC finds depth-w schedules with χ′Q = w = ∆(G) and w ∈ {6, 8, 9, 12}.

    Source: §VII · p. 12

  • Takeaways & Limitations

    The published IBM bivariate bicycle codes instead have verified depth-7 schedules, with optimality established using unreduced ASC infeasibility at depth 6.

    Source: §VII · p. 12

    Infeasibility of an orbit-reduced model excludes only schedules invariant under that subgroup, not all schedules at the same depth.

    Source: §IV · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper formulates fixed-PCM CSS syndrome extraction as quantum-constrained ordered edge coloring and introduces LocalASC to reduce variables using Tanner-graph automorphisms while retaining the constraints. It reports depth-optimal schedules for qualifying two-block and quantum Tanner code instances.

I. INTRODUCTION

  • The Tanner-degree lower bound is not always attainable: ASC proves depth 6 is impossible for published weight-6 IBM bivariate bicycle codes.Proper edge coloring prevents gate collisions, while quantum parity constraints enforce valid ordering for overlapping X/Z checks.Source: §I · p. 1
  • LocalASC assigns one tick variable per edge orbit under a selected vertex-class-preserving subgroup and retains all QCEC constraints, so feasible assignments lift to valid invariant schedules.The subgroup may come from a generic graph-automorphism routine or the code construction.Source: §I · p. 1
  • Every completed Table I instance reaches depth w; LocalASC averages at most 11 seconds, while ASC finds no schedule for eight instances within 30 minutes.The eight include the [[108, 12, 6]] two-block code and the [[180, 26, 6]] quantum Tanner code.Source: §I · p. 2
  • For identified two-block codes with unequal odd component weights, LocalASC finds depth-(wA + wB) schedules, one layer below cited constructions, and finds additional depth-optimal quantum Tanner schedules.The cited constructions give depth-(wA + wB + 1) schedules for unequal odd weights.Source: §I · p. 2
  • For the same [[12, 4, 2]] measured PCMs, LocalASC finds a depth-6 schedule using 24 edge orbits, versus depth 7 from the analytical construction.The reduced model uses an order-3 automorphism subgroup.Source: §I · p. 2
  • The paper constructs translation subgroups for two-block group-algebra codes over abelian groups and gives conditions for quantum Tanner square-complex symmetries to extend to Tanner graph automorphisms.It also gives conditions for local CSS ordered colorings to lift to full-graph QCEC schedules.Source: §I · p. 2

B. Quantum CSS Codes

  • A fixed pair of PCMs specifies the measured X- and Z-checks; the same code may have different generator sets, including redundant low-weight checks.The CSS Tanner graph connects check vertices to data vertices wherever the corresponding PCM has a 1.Source: B. Quantum CSS Codes · p. 3

C. Coset-Based Two-Block CSS Codes

  • Coset-based two-block codes use a finite group, a subgroup, and two group-algebra elements; when the subgroup is normal, the construction reduces to a two-block group-algebra code.The left and right coset actions commute.Source: C. Coset-Based Two-Block CSS Codes · p. 3

D. Quantum Tanner Codes

The section introduces quantum Tanner codes through graph-based constructions using regular graphs, local classical codes, and square-complex structure. It also describes how labeled incidence and base graphs encode Tanner-code structure.

D. Quantum Tanner Codes

  • Quantum Tanner codes use a pair of regular graphs together with a pair of classical codes whose lengths equal the graph degree.Source: D. Quantum Tanner Codes · p. 3
  • An incidence graph joins graph vertices to their incident edges, with local edge orderings inducing labels on its edges.Source: D. Quantum Tanner Codes · p. 4
  • A Tanner code is defined from a base graph and a local code, with its parity-check matrix obtained from the graph construction described by R.The construction uses a biregular graph with locally labeled edges to connect the base graph and local code.Source: D. Quantum Tanner Codes · p. 4
  • The square complex is built from group elements and subsets A and B, with squares indexed by choices of a, g, and b.Source: D. Quantum Tanner Codes · p. 4
  • The square complex yields two graphs whose edges are its squares viewed along diagonals, and the local parity-check and generator matrices define the quantum Tanner code on this data.Source: D. Quantum Tanner Codes · p. 4

III. QUANTUM ORDERING CONSTRAINT

The quantum-ordering constraint supplements collision-free edge scheduling with a parity condition on the relative order of overlapping X- and Z-check interactions. Together, these constraints characterize valid syndrome-extraction schedules, but do not guarantee distance preservation or hook-error optimality.

III. Quantum Ordering Constraint

  • The quantum parity condition prevents residual CZ coupling between overlapping ancillas when the inversion parity is even.The residual coupling is absent exactly when ηij(t)=0.Source: §III · p. 5
  • For each overlapping X/Z check pair, the number of shared data qubits where the X interaction precedes the Z interaction must be even.This is the vanishing-modulo-2 condition on inversion parity.Source: §III · pp. 4–5
  • Distinct ticks on edges incident to check or data vertices make each tick class a matching, enforcing collision-free layers.The edge-coloring constraints are supplemented by the ordering-parity condition for every X/Z overlap.Source: §III · p. 5
  • A valid schedule ensures correct syndrome measurement but does not by itself ensure distance preservation or hook-error optimality.Different CX orderings at the same depth can yield different residual errors and circuit distances.Source: §III · p. 5

A. Quantum-Constrained Edge Chromatic Number

The quantum-constrained edge chromatic number is the minimum number of colors in a proper ordered Tanner-graph edge coloring that satisfies quantum ordering constraints. It characterizes optimal two-qubit depth in the standard single-ancilla model.

A. Quantum-Constrained Edge Chromatic Number

IV. LOCALASC: LOCAL AUTOMORPHISM-AWARE SYNDROME COMPILATION

LocalASC uses Tanner-graph automorphisms to reduce syndrome compilation to edge-orbit tick variables while retaining the original graph’s constraints. Feasible orbit assignments lift to valid global schedules; examples illustrate the reduction and its limits.

Motivating Example

  • A depth-4 schedule is also found for the example code’s unreduced 24-variable ASC model, while its Tanner-graph automorphism group has order 48.The example motivates searching subgroups to reduce variables; the order-3 subgroup supports a feasible schedule at depth 4.Source: §IV · p. 6
  • For the [[6, 2, 2]] example, an order-3 subgroup reduces 24 Tanner edges to 8 orbit variables and lifts a valid depth-4 coloring.Each orbit contains three edges, and the lifted coloring satisfies the quantum-validity constraints for all 9 overlapping check pairs.Source: §IV · p. 6, Figure 3 · p. 6

Orbit Model

  • LocalASC assigns one tick variable per edge orbit under a subgroup of Tanner-graph automorphisms, while retaining the QCEC constraints on the full graph.The subgroup preserves the X-check, Z-check, and data-qubit vertex classes.Source: §IV · p. 7
  • The orbit model is equivalent to the full model for schedules invariant under the chosen subgroup: feasible assignments lift bijectively to such schedules.This does not imply that every full-graph schedule is subgroup-invariant.Source: §IV · p. 7
  • Infeasibility at a tested depth rules out only schedules invariant under the tested subgroup, and a smaller subgroup cannot increase the minimum invariant-schedule depth.A smaller subgroup imposes fewer equal-tick constraints on edges.Source: §IV · p. 7

2 Form all constraints of Definition 2 on G

The procedure screens candidate automorphism subgroups for conflicts with proper edge coloring, then solves reduced models and verifies any lifted assignment against the full constraints.

2 Form all constraints of Definition 2 on G

  • Reject a subgroup if two distinct edges incident on the same vertex belong to the same orbit, since the orbit model would force them to share a tick.This violates the proper-edge-coloring constraint.Source: LocalASC Procedure · p. 7, §2 · p. 7
  • Accept an orbit assignment only after its lift passes verification against all global constraints (C1)–(C3).The assignment is checked on the full Tanner graph.Source: LocalASC Procedure · p. 7, §2 · p. 7
  • For a general CSS code, compute the Tanner-graph automorphism group with nauty, using VF2 when necessary.A verified subgroup is required, but need not be the full automorphism group.Source: LocalASC Procedure · p. 7, §V · p. 8
  • If the automorphism group has a nontrivial odd-order element, first test the subgroup generated by one of maximum odd order.This candidate is screened for incident edges in the same orbit before solving.Source: LocalASC Procedure · p. 7
  • If the first subgroup is unavailable, fails screening, or yields an infeasible model, try selected subgroups in decreasing order of cardinality.The selection can include cyclic subgroups, two-generator subgroups, and the full automorphism group.Source: LocalASC Procedure · pp. 7–8
  • The search returns the first ASC-feasible schedule found among the selected subgroups; the identity subgroup recovers unreduced ASC.The selected family need not include every subgroup because nontrivial subgroups are used to search for schedules with fewer variables.Source: LocalASC Procedure · p. 8

A. Automorphism Subgroups for Two-Block CSS Codes

For two-block group-algebra CSS codes over abelian groups, simultaneous translations can supply verified Tanner-graph automorphisms for LocalASC. The construction is implemented for the full translation group, not general coset spaces.

A. Automorphism Subgroups for Two-Block CSS Codes

  • For abelian G, simultaneous translation of checks and both data-qubit blocks preserves the two-block code’s parity-check matrices.Verified coordinate translations generate the translation subgroup used by LocalASC.Source: A. Automorphism Subgroups for… · p. 8
  • The implementation constructs the full translation group for coset-based codes with K = {1}, but does not implement general coset spaces G/K.Potential nonabelian subgroup candidates from the general construction are not studied.Source: A. Automorphism Subgroups for… · p. 8
  • The construction verifies induced check and data-qubit permutations on the measured PCMs before returning candidate subgroups.Preserving incidences alone is insufficient: adjacent edges must also lie in distinct edge orbits, and lifted schedules are verified.Source: Construction of the Translation Action · pp. 8–9
  • For the [[36, 4, 4]], [[36, 4, 6]], and [[108, 12, 6]] codes, translation subgroups yield depth-6 schedules without computing the full automorphism group.For the [[108, 12, 6]] code, average LocalASC runtime falls from 769 to 31 milliseconds.Source: Construction of the Translation Action · p. 9

B. Automorphism Groups of Quantum Tanner Codes

The section derives Tanner-graph automorphisms from symmetries of quantum Tanner codes’ underlying square complexes and local graphs. It also gives a product construction for quantum-valid colorings of codes with local restrictions.

B. Automorphism Groups of Quantum Tanner Codes

  • A square-complex symmetry extends to a quantum Tanner code’s Tanner graph when its induced local-check permutations satisfy the stated compatibility conditions.Theorem 3 formulates this condition for automorphisms of the vertex-square incidence graph and permutations of local check nodes.Source: B. Automorphism Groups of Quantum… · p. 9
  • An automorphism of the vertex-square incidence graph is uniquely determined by its restriction to one local incidence graph when the induced map has the required extension.The extension to the other local incidence graph is unique.Source: B. Automorphism Groups of Quantum… · p. 9
  • For a quantum Tanner code built from an abelian group using the bipartite construction, that group embeds in the Tanner-graph automorphism group.The result supplies a subgroup that can be used in LocalASC.Source: B. Automorphism Groups of Quantum… · p. 9
  • For the [[45, 7, 4]] quantum Tanner code, LocalASC uses a C5 subgroup to find a depth-6 schedule while reducing the coloring model from 240 to 48 variables.The code has maximum row and column weight 6.Source: B. Automorphism Groups of Quantum… · p. 10
  • For the [[180, 26, 6]] code built using the Petersen graph, LocalASC finds a depth-6 schedule using either C5 or C10.The code’s maximum row and column weight is 6.Source: B. Automorphism Groups of Quantum… · p. 10
  • Quantum-valid local CSS colorings of depths λ1 and λ2 induce a quantum-valid coloring of depth λ1λ2 for quantum Tanner codes under Theorem 5’s conditions.The section notes that the needed local coloring condition requires B to contain no self-inverse elements.Source: B. Automorphism Groups of Quantum… · p. 10

VI. NUMERICAL RESULTS

The experiments benchmark circuit-level behavior for schedules produced by different methods, using filtering to select schedules by estimated logical error rate (LER) per cycle. In the [[48, 4, 8]] comparison, the filtered depth-6 LocalASC schedule has lower estimated LER than the depth-6 ASC and depth-7 Aydin et al. schedules; a separate [[72, 12, 6]] comparison also favors LocalASC over Bravyi et al.

VI. NUMERICAL RESULTS

  • Schedule comparisons use memory circuits with d rounds of syndrome extraction and no perfect final round, matching the coset-based-code implementation.The circuit-level noise model assigns physical error rate p to gates, initialization, measurement, and idle locations.Source: §VI · p. 11
  • Filtering runs LocalASC repeatedly and selects the schedule with the lowest estimated LER per cycle from decoding experiments at p = 0.001.Each candidate schedule is evaluated for 10^4 trials; Fig. 4 uses 50 filtering steps.Source: §VI · p. 11, Figure 4 · p. 12
  • The circuit-distance upper bound for all [[48, 4, 8]] schedules is 5, and that bound is used in the extrapolation.The circuit distance is estimated from memory experiments and determines the leading-order scaling of logical failure probability.Source: §VI · pp. 11–12
  • In Fig. 5, for the coset-based [[48, 4, 8]] code, the depth-6 LocalASC schedule selected by circuit filtering has lower estimated LER than depth-6 ASC and depth-7 Aydin et al. [11] schedules at the same simulated noise levels.The Fig. 5 memory experiments used BP+OSD-CS10; circuits were selected after filtering when possible.Source: §VI · p. 12, Figure 5 · p. 12
  • The depth-7 LocalASC schedule has lower estimated LER than Bravyi et al.'s depth-7 schedule in the [[72, 12, 6]] BB-code simulations.Both schedules used the same noise model and decoder settings; this instance has χ′_Q = 7 > Δ = 6.Source: §VI · p. 12

VII. DISCUSSION AND CONCLUSION

LocalASC finds depth-w schedules for 18 measured CSS PCM pairs from two-block and quantum Tanner codes, with w = Δ(G) and zero quantum scheduling gap. The discussion highlights dependence on the measured PCM presentation, distinguishes orbit-model infeasibility from full-model infeasibility, and identifies further construction and performance objectives.

VII. DISCUSSION AND CONCLUSION

  • LocalASC finds depth-w schedules for 18 two-block and quantum Tanner PCM pairs, with w ∈ {6, 8, 9, 12}; all are weight-optimal and have zero quantum scheduling gap.For every listed pair, χ′_Q = w = Δ(G).Source: §VII · p. 12
  • QCEC and LocalASC depend on the measured CSS PCMs, so adding dependent checks can increase symmetry if the original checks remain and Δ(G) is unchanged.A schedule for the enlarged PCM pair can be restricted to the original checks without increasing its depth.Source: §VII · p. 12
  • For the seven published IBM BB codes, translation symmetry reduces each scheduling instance to 12 edge-orbit variables, while depth-7 optimality requires solver-certified depth-6 infeasibility in the unreduced model.Infeasibility of the orbit-reduced model alone does not establish infeasibility of the full model.Source: §VII · p. 12
  • The authors identify constructing qLDPC codes with measured PCMs admitting depth-w schedules and finding algebraic conditions for zero quantum scheduling gap as future directions.They also propose minimizing χ′_Q over bounded-weight generator presentations as a code-level invariant.Source: §VII · p. 12
  • Variation in LER among schedules at a fixed depth shows that depth alone does not determine logical-error performance.The authors suggest adding constraints to limit hook-error propagation or require a lower bound on circuit distance.Source: §VII · pp. 12–13
  • The released ASC implementation treats solver UNKNOWN and INFEASIBLE alike when advancing its search, so the authors accept only explicit INFEASIBLE statuses as evidence of depth infeasibility.This qualification is relevant to establishing optimality for the published IBM BB-code schedules.Source: §VII · p. 12

APPENDIX A PROOF OF THEOREM 2

The appendix illustrates why quotienting the Tanner graph can lose quantum parity constraints, then proves that exact orbit substitution preserves them for H-invariant schedules.

APPENDIX A PROOF OF THEOREM 2

  • The paper presents an example before Theorem 2 to illustrate that constraints (6) and (7) in Definition 6 rule out quantum-invalid schedules.For the described automorphism, every edge is paired with its image, forming eight orbits of two edges that share neither endpoint.Source: Appendix A · p. 13, A. Proper Edge Coloring in O is Not… · p. 13

A. Proper Edge Coloring in O is Not Enough

  • A quotient assignment can pass its aggregate parity test while both original-graph parities are odd, unlike the exact orbit-reduced formulation.The example uses two proper depth-4 colorings; only one lifts to an ASC-feasible schedule.Source: A. Proper Edge Coloring in O is Not… · p. 13

B. The Proof

  • Exact orbit substitution gives a one-to-one correspondence between feasible orbit assignments and H-invariant ASC-feasible schedules on the full graph.The proof checks proper coloring and each original overlapping-check parity constraint in both directions.Source: B. The Proof · pp. 13–14

APPENDIX B PROOF OF PROPOSITION 2

These appendices characterize when local symmetries yield Tanner graph automorphisms and show how quantum-valid edge colorings combine in quantum Tanner codes. The circuit-level comparison also notes decoder-setting differences from prior results.

APPENDIX B PROOF OF PROPOSITION 2

  • A lifted map is a Tanner graph automorphism exactly when each local map σv ⊔ f|δ(v) is an automorphism of the corresponding local graph.The local maps act on variable nodes of the graph associated with the base-graph neighborhood.Source: Appendix B · p. 14

APPENDIX C PROOF OF COROLLARY 1

  • A graph automorphism f is label-preserving precisely when the map in (15) is the identity for every check vertex.In this special case, the identity must be an automorphism of the local graph.Source: Appendix C · pp. 14–15

APPENDIX D PROOF OF THEOREM 5

  • Ordering the product of two quantum-valid colorings row-wise yields an ASC-feasible schedule for the product code, including the quantum Tanner code.The proof checks both quantum-ordering constraints and proper edge coloring.Source: Appendix D · p. 15

CIRCUIT-LEVEL NOISE

  • The BB-code memory comparison uses 1000 rather than 10000 BP iterations and CS order 10 rather than 1, so performance can differ from [7, Fig. 2].The compared circuits use LocalASC schedules and official BB-code schedules.Source: CIRCUIT-LEVEL NOISE · p. 15
Loading 2609.40319v1…