Rem_22: Gross Code Gauging Example #
Statement #
The gauging measurement for X̄_α in the Gross code provides a concrete example demonstrating the efficiency of the gauging approach.
Goal: Measure X̄_α = X(αf, 0) while keeping all new checks and qubits at Tanner graph degree at most 6 (the 12 qubits in X̄_α and 18 adjacent Z checks will become degree 7).
Graph construction:
- Vertices: The 12 monomials in f correspond to the 12 vertices of G
- Initial edges: Connect γ, δ ∈ f if qubits (γ, L) and (δ, L) participate in the same Z check, i.e., if γ = Bᵢᵀ Bⱼ δ for some i, j ∈ {1, 2, 3}. This gives 18 edges.
- Expansion edges: Add 4 additional edges to achieve distance 12: (x², x⁵y³), (x², x⁶), (x⁵y³, x¹¹y³), (x⁷y³, x¹¹y³)
Cycle basis: With 12 vertices and 22 edges, G has 22 - 12 + 1 = 11 independent cycles. Due to redundancy in the BB code's Z checks (4 redundant cycles), only 11 - 4 = 7 independent B_p checks are needed.
Overhead summary:
- 12 new X checks (Gauss's law operators A_v)
- 7 new Z checks (flux operators B_p)
- 22 new qubits (edge qubits)
- Total additional elements: 41
This is significantly more efficient than the O(Wd) = O(12 · 12) = O(144) overhead of previous schemes.
Main Results #
GrossGaugingGraph: The graph parameters for gauging X̄_α in the Gross codenumVertices_eq: The graph has 12 vertices (monomials in f)numInitialEdges_eq: 18 edges from Z-check connectivitynumExpansionEdges_eq: 4 additional expansion edgesnumTotalEdges_eq: Total 22 edgesnumIndependentCycles_eq: 22 - 12 + 1 = 11 independent cyclesnumRedundantCycles_eq: 4 redundant cycles from BB codenumNewXChecks_eq: 12 new X checks (Gauss's law operators)numNewZChecks_eq: 7 new Z checks (flux operators)numNewQubits_eq: 22 new qubits (edge qubits)totalOverhead_eq: Total overhead is 41previous_scheme_overhead: Previous scheme overhead is O(144)efficiency_improvement: 41 < 144
Corollaries #
maxNewDegree_eq: New elements have Tanner graph degree ≤ 6maxAffectedDegree_eq: Affected existing elements have degree 7logicalX_weight_eq: Weight of X̄_α is 12targetDistance_eq: Target distance is 12 (matching code distance)
Section 1: Logical Operator Parameters #
X̄_α = X(αf, 0) is supported on 12 qubits (the monomials of f). The Gross code has distance d = 12.
Weight of the logical operator X̄_α: the number of monomials in f.
Equations
Instances For
The code distance of the Gross code.
Equations
Instances For
The weight of X̄_α equals the code distance (a key property of the Gross code).
Section 2: Graph Construction Parameters #
The gauging graph G for the Gross code has specific structural parameters arising from the BB code's Z-check connectivity and additional expansion edges.
The parameters of the gauging graph for X̄_α in the Gross code.
- numVertices : ℕ
Number of vertices: monomials in f
- numInitialEdges : ℕ
Number of initial edges from Z-check connectivity
- numExpansionEdges : ℕ
Number of expansion edges added for distance
- numRedundantCycles : ℕ
Number of redundant cycles from BB code Z-check structure
- maxNewDegree : ℕ
Maximum Tanner graph degree for new elements
- maxAffectedDegree : ℕ
Maximum Tanner graph degree for affected existing elements
Instances For
The concrete gauging graph for X̄_α in the Gross code.
Equations
- QEC1.GrossCodeGaugingExample.grossGaugingGraph = { numVertices := 12, numInitialEdges := 18, numExpansionEdges := 4, numRedundantCycles := 4, maxNewDegree := 6, maxAffectedDegree := 7 }
Instances For
Section 3: Basic Parameter Values #
The vertices correspond to monomials in f, so numVertices = logicalWeight.
Section 4: Edge Count Computation #
Total edges = initial edges + expansion edges = 18 + 4 = 22.
Total number of edges in the gauging graph.
Equations
Instances For
The total edges break down as 18 initial + 4 expansion.
Section 5: Cycle Basis Computation #
By Euler's formula for connected graphs: number of independent cycles = |E| - |V| + 1. With 22 edges and 12 vertices: 22 - 12 + 1 = 11.
Number of independent cycles by Euler's formula: |E| - |V| + 1.
Equations
Instances For
The gauging graph has 11 independent cycles.
Euler's formula verification: 22 - 12 + 1 = 11.
Section 6: Redundant Cycles and Flux Operator Count #
The BB code's Z checks introduce 4 redundant cycles, so only 11 - 4 = 7 independent B_p checks are needed.
Number of needed B_p flux checks: independent cycles minus redundant.
Equations
Instances For
Only 7 independent B_p checks are needed.
The redundancy reduces 11 cycles to 7 checks.
Section 7: Overhead Summary #
The total overhead consists of:
- numVertices new X checks (Gauss's law operators A_v): 12
- numNeededFluxChecks new Z checks (flux operators B_p): 7
- numTotalEdges new qubits (edge qubits): 22
- Total: 12 + 7 + 22 = 41
Number of new X checks = number of vertices (one A_v per vertex).
Equations
Instances For
Number of new Z checks = number of needed flux checks.
Equations
Instances For
Number of new qubits = number of edges (one gauge qubit per edge).
Instances For
Total overhead: new X checks + new Z checks + new qubits.
Equations
Instances For
Total overhead is 41.
The total overhead breaks down as 12 + 7 + 22 = 41.
Section 8: Comparison with Previous Schemes #
Previous schemes have O(Wd) overhead, where W is the logical operator weight and d is the code distance. For the Gross code: W = d = 12, so O(Wd) = O(144).
Previous scheme overhead bound: W × d = 12 × 12 = 144.
Equations
Instances For
The gauging overhead (41) is strictly less than the previous scheme overhead (144).
The improvement ratio: the gauging overhead is less than 29% of the previous scheme.
The gauging saves 103 = 144 - 41 elements compared to previous schemes.
Section 9: Degree Bound Properties #
New elements have Tanner graph degree ≤ 6. The 12 qubits in X̄_α and the 18 adjacent Z checks will become degree 7.
New checks and qubits have degree at most 6.
Affected existing elements have degree at most 7.
The degree increase for affected elements is exactly 1 (from 6 to 7).
Section 10: Expansion Edge Details #
The 4 expansion edges connect specific monomials to achieve distance 12. We record these as pairs of monomials in ZMod 12 × ZMod 6.
Type alias for monomials in the Gross code group.
Equations
Instances For
All expansion edges are between distinct vertices.
There are exactly 4 expansion edges.
Section 11: Monomials of f #
The polynomial f has 12 monomials, which correspond to the 12 vertices of G: f = 1 + x + x² + x³ + x⁶ + x⁷ + x⁸ + x⁹ + (x + x⁵ + x⁷ + x¹¹)y³
The monomials are: {(0,0), (1,0), (2,0), (3,0), (6,0), (7,0), (8,0), (9,0), (1,3), (5,3), (7,3), (11,3)}
The 12 monomials appearing in f, represented as elements of ZMod 12 × ZMod 6.
Equations
Instances For
f has exactly 12 monomials.
The number of monomials equals the number of graph vertices.
All monomials in f are distinct.
Section 12: Initial Edge Construction #
Connect γ, δ ∈ f if γ = Bᵢᵀ Bⱼ δ for some i, j ∈ {1,2,3}. The polynomial B = y³ + x² + x, so B acts by shifting monomials. The matrices B₁ = y³, B₂ = x², B₃ = x give: Bᵢᵀ Bⱼ sends δ ↦ -Bᵢ + Bⱼ + δ
This connectivity gives exactly 18 edges.
The number of Z checks adjacent to X̄_α.
Equations
Instances For
The number of adjacent Z checks equals the number of initial edges.
Section 13: Target Distance #
The expansion edges are added to ensure the gauging graph achieves distance 12, matching the Gross code distance.
The target distance for the gauging graph matches the code distance.
Equations
Instances For
The target distance equals the Gross code distance.
The target distance equals the number of vertices (a coincidence for this code).
Section 14: Overhead Breakdown Verification #
Verify all components of the overhead.
The number of new X checks equals the number of vertices (Gauss's law: one A_v per vertex).
The number of new Z checks is determined by cycle analysis.
The number of new qubits equals the total edges (one gauge qubit per edge).
All three overhead components add to 41.
Section 15: Consistency with Gross Code Parameters #
The number of vertices matches the Gross code's grossCodeParams_d.
The previous scheme overhead matches W * d = 12 * 12.
The previous scheme overhead equals a gross (144 = 12²).
Section 16: Summary of Efficiency #
The gauging approach for the Gross code uses only 41 additional elements, compared to 144 for previous schemes — a reduction by a factor of > 3.5×.
The gauging overhead is at most 41.
The efficiency factor: gauging uses less than 1/3 of previous overhead.
The gauging overhead is strictly less than half the previous scheme overhead.