47 Rem 22: Gross Code Gauging Example
This chapter provides a concrete example demonstrating the efficiency of the gauging approach, applied to measuring the logical operator \(\bar{X}_\alpha \) in the Gross code. The gauging graph construction is detailed, along with overhead calculations showing a significant improvement over previous schemes.
The weight of the logical operator \(\bar{X}_\alpha = X(\alpha f, 0)\), equal to the number of monomials in \(f\):
The code distance of the Gross code:
The weight of \(\bar{X}_\alpha \) equals the code distance: \(W = d\).
This holds by definitional equality, since both \(W\) and \(d\) are defined to be \(12\).
The structure recording the parameters of the gauging graph for \(\bar{X}_\alpha \) in the Gross code. It consists of:
numVertices : the number of vertices (monomials in \(f\)),
numInitialEdges : the number of initial edges from \(Z\)-check connectivity,
numExpansionEdges : the number of additional expansion edges,
numRedundantCycles : the number of redundant cycles from the BB code’s \(Z\)-check structure,
maxNewDegree : the maximum Tanner graph degree for new elements,
maxAffectedDegree : the maximum Tanner graph degree for affected existing elements.
The concrete gauging graph for \(\bar{X}_\alpha \) in the Gross code, with parameters:
\(|V| = 12\) vertices,
\(18\) initial edges from \(Z\)-check connectivity,
\(4\) expansion edges,
\(4\) redundant cycles,
maximum new degree \(6\),
maximum affected degree \(7\).
The gauging graph has \(12\) vertices: \(\texttt{grossGaugingGraph.numVertices} = 12\).
This holds by reflexivity from the definition.
The gauging graph has \(18\) initial edges: \(\texttt{grossGaugingGraph.numInitialEdges} = 18\).
This holds by reflexivity from the definition.
The gauging graph has \(4\) expansion edges: \(\texttt{grossGaugingGraph.numExpansionEdges} = 4\).
This holds by reflexivity from the definition.
The vertices of the graph correspond to monomials in \(f\), so \(|V| = W\):
This holds by reflexivity, since both sides equal \(12\).
The total number of edges in the gauging graph:
The total number of edges in the gauging graph is \(22\):
This holds by reflexivity from the definitions.
The total edges decompose as initial plus expansion:
This holds by reflexivity from the definition of numTotalEdges.
The number of independent cycles in the gauging graph, computed via Euler’s formula for connected graphs:
The gauging graph has \(11\) independent cycles:
This holds by reflexivity from the definitions.
Euler’s formula gives \(|E| - |V| + 1 = 22 - 12 + 1 = 11\).
By numerical computation, \(22 - 12 + 1 = 11\).
The number of needed \(B_p\) flux checks, after accounting for redundancy from the BB code’s \(Z\) checks:
Only \(7\) independent \(B_p\) checks are needed: \(11 - 4 = 7\).
This holds by reflexivity from the definitions.
The redundancy reduces \(11\) cycles to \(7\) checks:
This holds by reflexivity.
The number of new \(X\) checks equals the number of vertices (one Gauss’s law operator \(A_v\) per vertex):
The number of new \(Z\) checks equals the number of needed flux checks:
The number of new qubits equals the total number of edges (one gauge qubit per edge):
The number of new \(X\) checks is \(12\).
This holds by reflexivity from the definitions.
The number of new \(Z\) checks is \(7\).
This holds by reflexivity from the definitions.
The number of new qubits is \(22\).
This holds by reflexivity from the definitions.
The total overhead of the gauging approach:
The total overhead is \(41\):
This holds by reflexivity from the definitions.
The total overhead decomposes into its three components:
This holds by reflexivity from the definition of totalOverhead.
The overhead of previous schemes, which scales as \(O(Wd)\) where \(W\) is the logical operator weight and \(d\) is the code distance:
The previous scheme overhead is \(144\).
This holds by reflexivity, since \(12 \times 12 = 144\).
The gauging overhead (\(41\)) is strictly less than the previous scheme overhead (\(144\)):
By numerical computation, \(41 {\lt} 144\).
The gauging overhead is less than \(29\% \) of the previous scheme overhead:
By numerical computation, \(100 \times 41 = 4100 {\lt} 4176 = 29 \times 144\).
The gauging approach saves \(103\) elements compared to previous schemes:
By numerical computation, \(144 - 41 = 103\).
New checks and qubits have Tanner graph degree at most \(6\):
By numerical computation, \(6 \leq 6\).
Affected existing elements (the \(12\) qubits in \(\bar{X}_\alpha \) and the \(18\) adjacent \(Z\) checks) have degree at most \(7\):
By numerical computation, \(7 \leq 7\).
The degree increase for affected elements is exactly \(1\) (from \(6\) to \(7\)):
By numerical computation, \(7 - 6 = 1\).
The type alias for monomials in the Gross code group:
Expansion edge 1 connects \(x^2\) and \(x^5 y^3\):
Expansion edge 2 connects \(x^2\) and \(x^6\):
Expansion edge 3 connects \(x^5 y^3\) and \(x^{11} y^3\):
Expansion edge 4 connects \(x^7 y^3\) and \(x^{11} y^3\):
The endpoints of expansion edge 1 are distinct: \((2, 0) \neq (5, 3)\).
This is verified by computation (decide).
The endpoints of expansion edge 2 are distinct: \((2, 0) \neq (6, 0)\).
This is verified by computation (decide).
The endpoints of expansion edge 3 are distinct: \((5, 3) \neq (11, 3)\).
This is verified by computation (decide).
The endpoints of expansion edge 4 are distinct: \((7, 3) \neq (11, 3)\).
This is verified by computation (decide).
The list of expansion edges has exactly \(4\) elements.
This holds by reflexivity, since \([\text{e}_1, \text{e}_2, \text{e}_3, \text{e}_4].\text{length} = 4\).
The \(12\) monomials appearing in \(f\), represented as elements of \(\mathbb {Z}/12\mathbb {Z} \times \mathbb {Z}/6\mathbb {Z}\):
These correspond to the monomials of \(f = 1 + x + x^2 + x^3 + x^6 + x^7 + x^8 + x^9 + (x + x^5 + x^7 + x^{11})y^3\).
The polynomial \(f\) has exactly \(12\) monomials: \(|\text{monomialsOfF}| = 12\).
This holds by reflexivity from the list definition.
The number of monomials equals the number of graph vertices:
This holds by reflexivity, since both sides equal \(12\).
All monomials in \(f\) are distinct (the list has no duplicates).
This is verified by computation (decide).
The number of \(Z\) checks adjacent to \(\bar{X}_\alpha \):
These arise from the connectivity condition: vertices \(\gamma , \delta \in f\) are connected if \(\gamma = B_i^T B_j \delta \) for some \(i, j \in \{ 1,2,3\} \).
The number of adjacent \(Z\) checks equals the number of initial edges:
This holds by reflexivity.
The target distance for the gauging graph, set to match the Gross code distance:
The target distance equals the Gross code distance: \(\text{targetDistance} = d\).
This holds by reflexivity.
The target distance equals the number of vertices (a coincidence for this code):
This holds by reflexivity.
The number of new \(X\) checks equals the number of vertices (one Gauss’s law operator \(A_v\) per vertex):
This holds by reflexivity from the definition.
The number of new \(Z\) checks is determined by cycle analysis:
This holds by reflexivity from the definition.
The number of new qubits equals the total edges (one gauge qubit per edge):
This holds by reflexivity from thedefinition.
All three overhead components add to \(41\): \(12 + 7 + 22 = 41\).
By numerical computation, \(12 + 7 + 22 = 41\).
The number of vertices matches the Gross code’s distance parameter:
By simplification using the definition of grossCodeParams, both sides equal \(12\).
The previous scheme overhead equals \(d \times d = d^2\):
By simplification using the definitions of previousSchemeOverhead, logicalWeight, codeDistance, and grossCodeParams, both sides equal \(144\).
The previous scheme overhead equals the number of physical qubits \(n\) of the Gross code:
By simplification using the definitions, both sides equal \(144\).
The gauging overhead is at most \(41\):
This follows by reflexivity of \(\leq \) since both sides equal \(41\).
The gauging overhead is less than \(1/3\) of the previous scheme overhead:
By numerical computation, \(3 \times 41 = 123 {\lt} 144\).
The gauging overhead is strictly less than half the previous scheme overhead:
By numerical computation, \(2 \times 41 = 82 {\lt} 144\).