38 Rem 15: Hypergraph Generalization of Gauging Measurement
The gauging measurement procedure can be generalized by replacing the graph \(G\) with a hypergraph to measure multiple operators simultaneously. For qubits, this is equivalent to replacing the graph \(G\) with a hypergraph. The generalized gauging procedure performs a code deformation by introducing a qubit for each hyperedge and measuring into new Gauss’s law checks \(A_v\) given by the product of \(X\) on a vertex and the adjacent hyperedges.
A hypergraph on vertices \(V\) with hyperedges indexed by \(H\) is a structure consisting of an incidence function
mapping each hyperedge to the set of its incident vertices. This generalizes a graph, where each edge connects exactly two vertices, to the case where each hyperedge may connect an arbitrary subset of vertices.
The incidence entry of a hypergraph \(\mathrm{HG}\) at hyperedge \(h\) and vertex \(v\) is defined as
where the values are taken in \(\mathbb {Z}/2\mathbb {Z}\).
The parity-check map \(H_Z : \mathbb {Z}_2^V \to \mathbb {Z}_2^H\) of a hypergraph \(\mathrm{HG}\) is the \(\mathbb {Z}_2\)-linear map defined by
for each hyperedge \(h \in H\). The kernel of this map characterizes the abelian group of commuting \(X\)-type operators.
The operator kernel of a hypergraph \(\mathrm{HG}\) is the kernel of the parity-check map:
This is a \(\mathbb {Z}_2\)-submodule of \(\mathbb {Z}_2^V\) that characterizes the abelian group of commuting \(X\)-type operators.
For a hypergraph \(\mathrm{HG}\) and a vector \(x \in \mathbb {Z}_2^V\),
We unfold the definition of \(\mathrm{operatorKernel}\) as \(\ker (\mathrm{parityCheckMap})\). We prove both directions. For the forward direction, assume \(H_Z(x) = 0\). For any hyperedge \(h\), we extract the \(h\)-th component of this equation, which by simplification gives \(\sum _{v \in \mathrm{incidence}(h)} x_v = 0\). For the reverse direction, assume \(\sum _{v \in \mathrm{incidence}(h)} x_v = 0\) for all \(h\). By extensionality, we show \(H_Z(x) = 0\) component-wise, which follows by simplification using the hypothesis applied to each \(h\).
A hyperedge \(h\) is \(k\)-local if it contains at most \(k\) vertices:
A hypergraph is \(k\)-local if all of its hyperedges are \(k\)-local:
If a hyperedge \(h\) is \(k\)-local, then the corresponding row of the incidence matrix has at most \(k\) nonzero entries:
We first establish that the set \(\{ v \in V \mid \mathrm{incidenceEntry}(h,v) \neq 0\} \) equals the set \(\{ v \in V \mid v \in \mathrm{incidence}(h)\} \). By extensionality, for each vertex \(v\): if \(\mathrm{incidenceEntry}(h,v) \neq 0\), we argue by contradiction that \(v \in \mathrm{incidence}(h)\) (since \(v \notin \mathrm{incidence}(h)\) would give \(\mathrm{incidenceEntry}(h,v) = 0\), contradiction); conversely, if \(v \in \mathrm{incidence}(h)\), then by simplification \(\mathrm{incidenceEntry}(h,v) = 1 \neq 0\). Rewriting with this equality, we compute
where the first inequality follows because the filter is a subset of \(\mathrm{incidence}(h)\), and the second is the \(k\)-locality hypothesis.
The set of hyperedges incident to vertex \(v\) is
The vertex support of the generalized Gauss law operator \(A_v\) is a binary vector on \(V\) with \(1\) at position \(v\) and \(0\) elsewhere, representing the \(X_v\) factor:
The hyperedge support of \(A_v\) is a binary vector on \(H\) with \(1\) at each hyperedge containing \(v\):
The \(Z\)-type support of \(A_v\) on vertex qubits is the zero vector, since \(A_v\) is a purely \(X\)-type operator:
The \(Z\)-type hyperedge support of \(A_v\) is also the zero vector:
The symplectic inner product on vertex qubits for two Pauli operators with \(X\)-type supports \(xS_1, xS_2\) and \(Z\)-type supports \(zS_1, zS_2\) is
The symplectic inner product on hyperedge qubits is defined analogously:
For any two vertices \(v_1, v_2 \in V\), the generalized Gauss law operators \(A_{v_1}\) and \(A_{v_2}\) commute. Specifically, the symplectic inner product of their supports is zero on both vertex and hyperedge qubits:
We prove each conjunct separately. For the vertex part, we unfold the definitions of \(\mathrm{symplecticInnerProductV}\) and \(\mathrm{gaussLawZTypeSupport}\). Since the \(Z\)-type support is the zero vector, every term in the sum \(xS_1(i) \cdot 0 + 0 \cdot xS_2(i) = 0\), so the entire sum simplifies to \(0\). The hyperedge part follows identically using \(\mathrm{symplecticInnerProductH}\) and \(\mathrm{gaussLawZTypeHyperedgeSupport} = 0\).
The sum of all vertex supports equals the all-ones vector on \(V\):
corresponding to \(\prod _v A_v\) having \(L = \prod _v X_v\) as its vertex component.
By extensionality, it suffices to show equality for an arbitrary vertex \(w\). We unfold the pointwise sum and \(\mathrm{gaussLawVertexSupport}\). Using \(\mathrm{Finset.sum\_ eq\_ single}\; w\), we isolate the term \(v = w\), which contributes \(\mathrm{Pi.single}\; w\; 1\; w = 1\) by simplification. For any \(v \neq w\), \(\mathrm{Pi.single}\; v\; 1\; w = 0\) by the definition of \(\mathrm{Pi.single}\) for distinct indices. The case that \(w \notin \mathrm{univ}\) is absurd since \(w \in \mathrm{Finset.univ}\).
For each hyperedge \(h\), the sum of hyperedge supports over all vertices equals the cardinality of \(h\) modulo \(2\):
We unfold \(\mathrm{gaussLawHyperedgeSupport}\) and split the sum over \(V\) into vertices that belong to \(\mathrm{incidence}(h)\) and those that do not, using \(\mathrm{Finset.sum\_ filter\_ add\_ sum\_ filter\_ not}\). For vertices \(v \in \mathrm{incidence}(h)\), the conditional evaluates to \(1\); for vertices \(v \notin \mathrm{incidence}(h)\), it evaluates to \(0\). Rewriting via \(\mathrm{Finset.sum\_ congr}\) for each part, the sum over the complement contributes \(0\), and the sum over \(\mathrm{incidence}(h)\) contributes \(|\mathrm{incidence}(h)| \cdot 1\). We then observe that \(\{ v \in \mathrm{univ} \mid v \in \mathrm{incidence}(h)\} = \mathrm{incidence}(h)\) and simplify.
If every hyperedge has exactly \(2\) vertices (graph-like case), then for each hyperedge \(h\),
Rewriting using the hyperedge support sum theorem, the sum equals \(|\mathrm{incidence}(h)| \pmod{2}\). By the graph-like hypothesis, \(|\mathrm{incidence}(h)| = 2\), so the result is \(2 \pmod{2} = 0\), which is verified by computation.
A hypergraph is graph-like if every hyperedge has exactly \(2\) vertices:
Given a \(\mathrm{GraphWithCycles}\) \(G\) on vertices \(V\), edges \(E\), and cycles \(C\), we construct a hypergraph on vertices \(V\) with hyperedges indexed by \(E\) by setting
for each edge \(e \in E\). This embeds ordinary graphs into the hypergraph framework.
A hypergraph constructed from a \(\mathrm{GraphWithCycles}\) is graph-like.
Let \(e\) be an edge. We unfold the definitions of \(\mathrm{ofGraphWithCycles}\) and \(\mathrm{isGraphLike}\). The incidence set of \(e\) is \(\mathrm{edgeVertices}(e) = \{ G.\mathrm{edgeStart}(e),\, G.\mathrm{edgeEnd}(e)\} \). Since the two endpoints are distinct (by \(G.\mathrm{edge\_ endpoints\_ ne}\)), the cardinality of this pair equals \(2\).
For a \(k\)-local hypergraph, the parity-check matrix has at most \(k\) entries per row:
This follows directly from the definition of \(k\)-local hypergraph applied to \(h\).
For a \(k\)-local hypergraph, the total number of nonzero entries in the incidence matrix is bounded by \(k \cdot |H|\):
We compute:
where the first inequality uses \(\mathrm{Finset.sum\_ le\_ sum}\) with the \(k\)-locality bound \(|\mathrm{incidence}(h)| \le k\) for each \(h\), and the second equality follows by rewriting the constant sum as \(k \cdot |\mathrm{Finset.univ}|\) and using \(|\mathrm{Finset.univ}| = |H|\).
The kernel of the parity-check map forms a \(\mathbb {Z}_2\)-submodule (abelian group over \(\mathbb {F}_2\)):
We take \(S = \mathrm{operatorKernel} = \ker (H_Z)\). The equivalence \(x \in S \iff H_Z(x) = 0\) is exactly \(\mathrm{LinearMap.mem\_ ker}\).
The zero vector is always in the kernel: \(0 \in \ker (H_Z)\).
We unfold the definition of \(\mathrm{operatorKernel}\) and apply \(\mathrm{LinearMap.mem\_ ker}\). Since \(H_Z\) is a linear map, \(H_Z(0) = 0\) by \(\mathrm{map\_ zero}\).
The kernel is closed under addition: if \(x, y \in \ker (H_Z)\), then \(x + y \in \ker (H_Z)\).
This follows directly from the fact that \(\mathrm{operatorKernel}\) is a submodule, and submodules are closed under addition.
The number of new qubits introduced in the generalized gauging procedure equals the number of hyperedges:
The number of new checks equals the number of vertices (one \(A_v\) per vertex):
The generalized coboundary map \(\delta : \mathbb {Z}_2^V \to \mathbb {Z}_2^H\) for the hypergraph is the \(\mathbb {Z}_2\)-linear map defined by
This is the transpose of the incidence matrix.
The hypergraph coboundary map equals the parity-check map:
By extensionality in both the input vector \(x\) and the hyperedge \(h\), both maps evaluate to \(\sum _{v \in \mathrm{incidence}(h)} x_v\), which holds by simplification of the definitions.
The all-ones vector on \(V\) is the constant function \(\mathbf{1}_V : V \to \mathbb {Z}_2\) defined by \(\mathbf{1}_V(v) = 1\) for all \(v \in V\). This represents the logical operator \(L = \prod _v X_v\).
The logical operator \(L\) (represented by the all-ones vector) is in the kernel if and only if every hyperedge has even cardinality:
We rewrite using the kernel membership characterization with \(x = \mathbf{1}_V\). For the forward direction, assume \(\sum _{v \in \mathrm{incidence}(h)} 1 = 0\) in \(\mathbb {Z}_2\) for all \(h\). Since \(\sum _{v \in \mathrm{incidence}(h)} 1 = |\mathrm{incidence}(h)| \cdot 1\), taking the \(\mathrm{ZMod.val}\) of both sides yields \(|\mathrm{incidence}(h)| \bmod 2 = 0\). For the reverse direction, assume \(|\mathrm{incidence}(h)| \bmod 2 = 0\) for all \(h\). Then \(|\mathrm{incidence}(h)|\) is even, so its natural number cast into \(\mathbb {Z}_2\) is \(0\), giving \(\sum _{v \in \mathrm{incidence}(h)} 1 = 0\) as required.
In the graph case (every hyperedge has exactly \(2\) vertices), the logical operator \(L\) is always in the kernel.
We rewrite using the characterization that \(\mathbf{1}_V \in \ker (H_Z)\) iff all hyperedges have even cardinality. For each hyperedge \(h\), the graph-like hypothesis gives \(|\mathrm{incidence}(h)| = 2\), and \(2 \bmod 2 = 0\).