9 Rem 8: Desiderata for Graph \(G\) in Gauging Measurement
This chapter formalizes the three desiderata for choosing the graph \(G\) in the gauging measurement procedure: short paths between \(Z\)-type support vertices, sufficient expansion (Cheeger constant \(h(G) \geq 1\)), and low-weight generating cycles. When all three hold simultaneously, the gauging measurement has constant qubit overhead and maintains fault tolerance.
Desideratum 1: Short Paths Property.
Let \(G = (V, E)\) be a simple graph, let \(\mathcal{Z}\) be a collection of \(Z\)-type support sets (each a finite subset of \(V\)), and let \(k \in \mathbb {N}\) be a constant path length bound.
The short paths property \(\mathrm{ShortPaths}(G, \mathcal{Z}, k)\) holds if: for every \(Z\)-type support set \(S \in \mathcal{Z}\) and every pair of vertices \(u, v \in S\), there exists a walk from \(u\) to \(v\) in \(G\) of length at most \(k\):
This ensures that deformed checks have bounded weight.
Desideratum 2: Sufficient Expansion.
A simple graph \(G = (V, E)\) has sufficient expansion if it is a strong expander, i.e., its Cheeger constant satisfies \(h(G) \geq 1\). Formally, \(\mathrm{SufficientExpansion}(G)\) is defined to be the property \(\mathrm{IsStrongExpander}(G)\).
For a simple graph \(G\), the sufficient expansion property holds if and only if \(h(G) \geq 1\):
This holds by reflexivity, since \(\mathrm{SufficientExpansion}(G)\) is defined to be \(\mathrm{IsStrongExpander}(G)\), which is itself defined as \(h(G) \geq 1\). The biconditional is definitionally equal to \(\mathrm{Iff.rfl}\).
Desideratum 3: Low-Weight Cycles Property.
Let \(G\) be a graph with a chosen collection of cycles (a \(\mathrm{GraphWithCycles}\) structure over vertex type \(V\), edge type \(E\), and cycle type \(C\)), and let \(w \in \mathbb {N}\) be a constant weight bound.
The low-weight cycles property \(\mathrm{LowWeightCycles}(G, w)\) holds if every cycle \(c \in C\) has at most \(w\) edges:
This ensures that the \(B_p\) flux operators \(B_p = \prod _{e \in p} Z_e\) have bounded weight.
The Three Desiderata for Gauging Graph \(G\).
A graph \(G\) (equipped with a cycle structure) satisfies the gauging graph desiderata with respect to a collection of \(Z\)-type supports \(\mathcal{Z}\), path bound \(k\), and cycle bound \(w\) if the following three conditions hold simultaneously:
Short paths: \(\mathrm{ShortPaths}(G.\mathrm{graph}, \mathcal{Z}, k)\) — there exist paths of length at most \(k\) between any two vertices in the same \(Z\)-type support set.
Sufficient expansion: \(\mathrm{SufficientExpansion}(G.\mathrm{graph})\) — the Cheeger constant satisfies \(h(G) \geq 1\).
Low-weight cycles: \(\mathrm{LowWeightCycles}(G, w)\) — all generating cycles have weight at most \(w\).
The informal justifications from the remark are:
Short paths \(\Longrightarrow \) deformed checks have bounded weight.
\(h(G) \geq 1\) \(\Longrightarrow \) deformed code distance \(\geq \) original code distance.
Low-weight cycles \(\Longrightarrow \) \(B_p\) flux operators have bounded weight.
All three together \(\Longrightarrow \) constant qubit overhead.
Let \(G\) be a graph with cycles, let \(w \in \mathbb {N}\), and suppose the low-weight cycles property \(\mathrm{LowWeightCycles}(G, w)\) holds. Then for every cycle \(c \in C\), the flux operator \(B_c = \prod _{e \in c} Z_e\) has weight at most \(w\):
This is immediate from the definition of flux operators.
The result follows directly by applying the hypothesis \(\mathrm{hlw}\) (which states \(\mathrm{LowWeightCycles}(G, w)\)) to the cycle \(c\). That is, \(\mathrm{hlw}(c)\) yields \(|\mathrm{cycles}(G, c)| \leq w\) immediately.