32 Cor 1: Overhead Bound
The gauging measurement procedure for measuring a logical operator \(L\) of weight \(W = |\mathrm{supp}(L)|\) can be implemented with qubit overhead \(O(W \log ^2 W)\). Specifically, the number of additional auxiliary qubits required is at most \(c \cdot W \log ^2 W\) for some universal constant \(c {\gt} 0\).
A QubitOverhead structure records the components of the qubit overhead in the gauging measurement construction. Each edge qubit is an auxiliary qubit initialized in \(|0\rangle \). It consists of:
\(W\): the weight of the logical operator (number of qubits in its support),
\(\mathtt{baseEdges}\): the number of edges in the base graph \(G_0\),
\(\mathtt{numLayers}\): the number of layers added for cycle sparsification,
\(\mathtt{cellulationEdges}\): the number of cellulation (triangulation) edges added.
The number of layer 0 edge qubits equals the number of base edges:
The number of inter-layer edge qubits, with \(W\) edges connecting each layer to the next:
The number of intra-layer edge qubits for layers \(1, \ldots , R\), where each layer has a copy of \(G_0\):
The number of cellulation edge qubits equals the number of cellulation (triangulation) edges:
The total number of auxiliary qubits is the sum of all components:
For any \(Q : \mathtt{QubitOverhead}\),
This holds by definitional unfolding (reflexivity).
For any \(Q : \mathtt{QubitOverhead}\),
By simplification using the expanded formula for \(\mathtt{totalQubits}\), the result follows by ring arithmetic.
An LDPCProperty consists of a maximum degree bound \(\mathtt{maxDegree} {\gt} 0\), expressing that each vertex participates in at most \(\mathtt{maxDegree}\) edges.
For an LDPC graph with \(W\) vertices and maximum degree \(d\), the number of edges is at most:
For \(d {\gt} 0\),
Unfolding the definition, \(\mathtt{maxEdgesLDPC}(W,d) = \lfloor W \cdot d / 2 \rfloor \). This follows from the fact that \(\lfloor n/2 \rfloor \leq n\) for all natural numbers \(n\) (i.e., Nat.div_le_self).
An OverheadConfig specifies the parameters for the overhead bound calculation:
\(W \geq 2\): the weight of the logical operator,
\(d \geq 1\): the LDPC degree bound,
\(C_{\mathrm{FH}} {\gt} 0\): the Freedman–Hastings constant.
The number of layers from the Freedman–Hastings construction:
The upper bound on base edges (linear in \(W\)):
The upper bound on cellulation edges (linear in \(W\)):
The qubit overhead structure for a given configuration, setting:
For any configuration \(\mathrm{cfg}\),
Unfolding the definition, \(\mathtt{numLayers} = C_{\mathrm{FH}} \cdot (\log _2 W)^2 + C_{\mathrm{FH}}\). After normalizing by ring arithmetic, the inequality holds by integer arithmetic (omega).
For any configuration \(\mathrm{cfg}\),
By simplification using the definitions of \(\mathtt{toQubitOverhead}\) and \(\mathtt{totalQubits\_ eq}\).
The universal constant for the overhead bound:
For any overhead configuration \(\mathrm{cfg}\) with parameters \(W \geq 2\), \(d \geq 1\), and \(C_{\mathrm{FH}} {\gt} 0\),
where \(c(d, C_{\mathrm{FH}}) = 2d + C_{\mathrm{FH}}(d+1) + C_{\mathrm{FH}}\).
We expand all definitions. Set \(L = (\log _2 W)^2\), and let \(C = C_{\mathrm{FH}}\). The left-hand side expands to:
We rearrange the LHS:
The RHS expands to:
Expanding both sides fully:
After canceling common terms (\(2dW\), \(CdWL\), \(CdW\)), it suffices to show:
This is established by:
\(CWL \leq 2CWL\) (since \(CWL \leq CWL + CWL\)),
\(CW \leq 2CW\) (since \(CW \leq CW + CW\)),
\(2dWL \geq 0\).
Combining via linear arithmetic gives the result.
For \(W \geq 4\),
Since \(W \geq 4\), we have \(\log _2 W \geq 1\), hence \((\log _2 W)^2 \geq 1\). This gives:
Applying the main bound from Theorem 1044:
The intermediate inequality uses nonlinear arithmetic.
The Cohen et al. overhead for measuring a weight-\(W\) logical operator with code distance \(d\):
For \(W \geq 4\) and \(d {\gt} (\log _2 W)^2\), there exists \(c {\gt} 0\) such that
Take \(c = 1\). Then \(c {\gt} 0\) holds trivially. We need \(W \cdot (\log _2 W)^2 {\lt} W \cdot d\). Since \(W {\gt} 0\) (from \(W \geq 4\)) and \((\log _2 W)^2 {\lt} d\) by hypothesis, this follows by nonlinear arithmetic: \(1 \cdot W \cdot (\log _2 W)^2 = W \cdot (\log _2 W)^2 {\lt} W \cdot d\).
For \(W \geq 4\) and \(c {\gt} 0\),
Since \(W {\gt} 0\) (from \(W \geq 4\)), the factor \(W\) can be cancelled from both sides. The forward direction follows by nonlinear arithmetic from \(c \cdot W \cdot (\log _2 W)^2 {\lt} W \cdot d\), and the reverse direction follows similarly.
The overhead function:
The reference function for comparison:
For all \(c, W\),
By simplification of the definitions and ring arithmetic.
The Cohen overhead as a function of \(W\):
For any fixed \(d\) and \(c {\gt} 0\), there exists \(W_0\) such that for all \(W \geq W_0\) with \(c \cdot (\log _2 W)^2 {\lt} d\),
Take \(W_0 = 4\). Let \(W \geq 4\) with \(c \cdot (\log _2 W)^2 {\lt} d\). Since \(W {\gt} 0\), we have \(c \cdot W \cdot (\log _2 W)^2 {\lt} W \cdot d\) by nonlinear arithmetic.
An OverheadBreakdown provides a step-by-step breakdown of overhead sources:
\(W\): weight of the logical operator,
\(\mathtt{matchingEdges} \leq W\): edges from the matching step,
\(\mathtt{expansionEdges} \leq 3W\): edges from the expansion step (constant-degree expanders),
\(\mathtt{layers}\): number of sparsification layers, satisfying \(\mathtt{layers} \leq C \cdot (\log _2 W)^2 + C\) for all \(C {\gt} 0\).
Total edge qubits in the base graph \(G_0\):
Total edge qubits from layering:
Total auxiliary qubits:
The base graph has \(O(W)\) edges:
By unfolding the definition, \(\mathtt{baseEdgeQubits} = \mathtt{matchingEdges} + \mathtt{expansionEdges}\). Using the constraints \(\mathtt{matchingEdges} \leq W\) and \(\mathtt{expansionEdges} \leq 3W\), we obtain \(\mathtt{baseEdgeQubits} \leq W + 3W = 4W\) by integer arithmetic.
For any \(C {\gt} 0\),
By the layers bound, \(\mathtt{layers} \leq C \cdot (\log _2 W)^2 + C\). Therefore:
Adding these inequalities:
where the last step uses nonlinear arithmetic.
For any number of dummy vertices and any number of dummy edges, the dummy vertices themselves contribute \(0\) physical qubits:
Only their incident edges contribute qubits.
Let the number of dummy vertices and dummy edges be arbitrary. The statement \(0 = 0\) holds by reflexivity.
The total physical qubit count counts only edge qubits, not dummy vertex qubits:
(Corollary 1: Overhead Bound.) For any LDPC code with parameters \(W \geq 2\), \(d \geq 1\), and Freedman–Hastings constant \(C_{\mathrm{FH}} {\gt} 0\), there exists \(c {\gt} 0\) and a qubit overhead structure \(Q\) with \(Q.W = W\) such that
Let \(W, d, C_{\mathrm{FH}}\) be given with \(W \geq 2\), \(d \geq 1\), \(C_{\mathrm{FH}} {\gt} 0\).
Take \(c = \mathtt{overheadConstant}(d, C_{\mathrm{FH}}) = 2d + C_{\mathrm{FH}}(d+1) + C_{\mathrm{FH}}\). We verify \(c {\gt} 0\) by integer arithmetic (since \(d \geq 1\) and \(C_{\mathrm{FH}} {\gt} 0\)).
Construct the overhead configuration \(\mathrm{cfg}\) with the given parameters and take \(Q = \mathrm{cfg}.\mathtt{toQubitOverhead}\). Then \(Q.W = W\) holds by reflexivity.
The bound \(\mathtt{totalQubits}(Q) \leq c \cdot W \cdot ((\log _2 W)^2 + 1)\) follows directly from the qubit overhead bound theorem (Theorem 1044).
For good qLDPC codes with \(d = \Theta (n)\) and \(W = O(n)\), we have \(d {\gt} (\log _2 W)^2\), so the gauging measurement provides a significant improvement. Specifically, for \(W \geq 4\) and \(d {\gt} (\log _2 W)^2\), there exists \(c {\gt} 0\) such that
This follows directly from the overhead improvement theorem (Theorem 1047).