39 Rem 17: Hypergraph Generalization
This remark shows that the gauging measurement procedure can be generalized by replacing the graph \(G\) with a hypergraph \(H = (V, E)\), where each hyperedge \(e \in E\) is a nonempty subset of vertices. One introduces one auxiliary qubit per hyperedge, defines Gauss’s law operators \(A_v = X_v \prod _{e \ni v} X_e\), and a boundary map \(\partial : \mathbb {Z}_2^E \to \mathbb {Z}_2^V\) with \((\partial \gamma )_v = \sum _{e \ni v} \gamma _e\). The key result is that \(\gamma \in \ker (\partial )\) if and only if the corresponding pure-\(Z\) hyperedge operator commutes with all \(A_v\).
Given a hypergraph incidence relation \(\operatorname {incident} : V \to E \to \operatorname {Prop}\) and a vertex \(v \in V\), the set of hyperedges incident to \(v\) is
Given a hyperedge \(e \in E\), the set of vertices contained in \(e\) is
The hypergraph boundary map \(\partial : \mathbb {Z}_2^E \to \mathbb {Z}_2^V\) is the \(\mathbb {Z}_2\)-linear map defined by
for \(\gamma \in \mathbb {Z}_2^E\) and \(v \in V\). This generalizes the graph boundary map: for graphs, each edge is incident to exactly two vertices; for hypergraphs, a hyperedge can be incident to any nonempty set of vertices.
The hypergraph coboundary map \(\delta : \mathbb {Z}_2^V \to \mathbb {Z}_2^E\) is the transpose of \(\partial \). For \(f \in \mathbb {Z}_2^V\),
For all \(f \in \mathbb {Z}_2^V\) and \(\gamma \in \mathbb {Z}_2^E\),
Expanding the definitions, the left-hand side becomes \(\sum _e \bigl(\sum _v [\operatorname {incident}(v,e)] \cdot f_v\bigr) \cdot \gamma _e\) and the right-hand side becomes \(\sum _v f_v \cdot \bigl(\sum _e [\operatorname {incident}(v,e)] \cdot \gamma _e\bigr)\). Distributing the sums, both sides equal \(\sum _v \sum _e [\operatorname {incident}(v,e)] \cdot f_v \cdot \gamma _e\) after exchanging the order of summation and applying commutativity of multiplication in \(\mathbb {Z}_2\). The terms where \(\operatorname {incident}(v,e)\) is false contribute zero, so the sums agree.
The hypergraph Gauss’s law operator \(A_v\) on the extended system \(V \oplus E\) is defined as the Pauli operator with
i.e., its \(X\)-vector is \((\operatorname {xVec})_q = \begin{cases} 1 & \text{if } q = \operatorname {inl}(v), \\ 1 & \text{if } q = \operatorname {inr}(e) \text{ and } \operatorname {incident}(v,e), \\ 0 & \text{otherwise,} \end{cases}\) and its \(Z\)-vector is identically zero.
For every vertex \(v \in V\), the operator \(A_v\) is pure \(X\)-type: its \(Z\)-vector is identically zero.
By definition, the \(Z\)-vector of \(A_v\) is set to \(0\), so for any qubit \(q \in V \oplus E\), \((\operatorname {zVec}(A_v))_q = 0\). This holds by simplification.
For all vertices \(v, w \in V\), the operators \(A_v\) and \(A_w\) commute:
Commutation of Pauli operators is determined by the symplectic inner product \(\langle A_v, A_w \rangle = \sum _q (\operatorname {xVec}(A_v)_q \cdot \operatorname {zVec}(A_w)_q + \operatorname {zVec}(A_v)_q \cdot \operatorname {xVec}(A_w)_q)\). Since both \(A_v\) and \(A_w\) have \(\operatorname {zVec} = 0\), every term in the sum is zero. Hence \(\langle A_v, A_w \rangle = 0\), which means they commute.
Given an edge vector \(\gamma \in \mathbb {Z}_2^E\), the corresponding \(X\)-type operator on vertex qubits \(V\) is
defined as the Pauli operator with \(\operatorname {xVec} = \partial \gamma \) and \(\operatorname {zVec} = 0\).
On vertex qubits, the sum of \(X\)-vectors of all Gauss operators gives the all-ones vector: for each vertex \(w\),
The \(X\)-vector of \(A_v\) at position \(\operatorname {inl}(w)\) equals \(1\) if \(w = v\) and \(0\) otherwise. Therefore the sum over all \(v \in V\) has exactly one nonzero term (when \(v = w\)), giving \(1\). This is verified using the singleton sum lemma.
On edge qubits, the sum of \(X\)-vectors of all Gauss operators gives the cardinality of the hyperedge modulo 2: for each hyperedge \(e\),
The \(X\)-vector of \(A_v\) at position \(\operatorname {inr}(e)\) equals \(1\) if \(\operatorname {incident}(v,e)\) and \(0\) otherwise. The sum \(\sum _v [\operatorname {incident}(v,e)]\) counts the number of vertices in hyperedge \(e\), which equals \(|\operatorname {hyperedgeVertices}(e)|\) in \(\mathbb {Z}_2\). This follows by rewriting the sum as a Boolean indicator sum and the definition of \(\operatorname {hyperedgeVertices}\).
An edge vector \(\gamma \in \mathbb {Z}_2^E\) lies in \(\ker (\partial )\) if and only if \((\partial \gamma )_v = 0\) for all \(v \in V\).
By definition, \(\gamma \in \ker (\partial )\) means \(\partial \gamma = 0\) as a function \(V \to \mathbb {Z}_2\). By function extensionality, this is equivalent to \((\partial \gamma )_v = 0\) for all \(v\).
If \(\gamma \in \ker (\partial )\), then the \(X\)-type operator on \(V\) from \(\gamma \) is the identity: \(\operatorname {xOpFromBoundary}(\gamma ) = \mathbf{1}\).
Since \(\gamma \in \ker (\partial )\), we have \(\partial \gamma = 0\). The \(X\)-vector of \(\operatorname {xOpFromBoundary}(\gamma )\) is \(\partial \gamma = 0\), and the \(Z\)-vector is \(0\) by definition. By extensionality, this equals the identity operator \(\mathbf{1}\).
The Gauss subset product for a vector \(c \in \mathbb {Z}_2^V\) is the product \(\prod _{v : c_v = 1} A_v\), defined as the Pauli operator on \(V \oplus E\) with
and \(\operatorname {zVec} = 0\). On vertex qubits the \(X\)-vector is \(c\); on edge qubits it equals the coboundary \(\delta c\).
For all \(c_1, c_2 \in \mathbb {Z}_2^V\),
By extensionality on each qubit \(q\). For vertex qubits \(q = \operatorname {inl}(v)\): both sides give \((c_1 + c_2)_v = (c_1)_v + (c_2)_v\) by the definition of Pauli multiplication (component-wise addition of \(X\)-vectors in \(\mathbb {Z}_2\)). For edge qubits \(q = \operatorname {inr}(e)\): the left side gives \(\sum _v [\operatorname {incident}(v,e)] \cdot (c_1 + c_2)_v\), which distributes as \(\sum _v [\operatorname {incident}(v,e)] \cdot (c_1)_v + \sum _v [\operatorname {incident}(v,e)] \cdot (c_2)_v\) by linearity of summation; this matches the right side. For the \(Z\)-vector, both sides are zero since \(0 + 0 = 0\).
For all \(c \in \mathbb {Z}_2^V\) and \(e \in E\),
By simplification: both sides equal \(\sum _{v \in V} [\operatorname {incident}(v,e)] \cdot c_v\), which is the definition of the coboundary map applied to \(c\) at \(e\).
Given an edge vector \(\gamma \in \mathbb {Z}_2^E\), the pure-\(Z\) hyperedge operator on \(V \oplus E\) acts as \(Z\) on hyperedge qubit \(e\) if and only if \(\gamma _e = 1\). Formally, \(\operatorname {xVec} = 0\) and
For all \(\gamma \in \mathbb {Z}_2^E\) and \(v \in V\),
where \(Z(\gamma )\) denotes the pure-\(Z\) hyperedge operator and \(\langle \cdot , \cdot \rangle \) is the symplectic inner product.
We expand the symplectic inner product \(\langle Z(\gamma ), A_v \rangle = \sum _{q \in V \oplus E} (\operatorname {xVec}(Z(\gamma ))_q \cdot \operatorname {zVec}(A_v)_q + \operatorname {zVec}(Z(\gamma ))_q \cdot \operatorname {xVec}(A_v)_q)\) and split the sum over \(V\) and \(E\) using \(\operatorname {Fintype.sum\_ sum\_ type}\). For the sum over vertex qubits: \(\operatorname {xVec}(Z(\gamma )) = 0\) and \(\operatorname {zVec}(Z(\gamma ))_{\operatorname {inl}(w)} = 0\) for all \(w\), so every term vanishes and the vertex sum is \(0\). For the sum over edge qubits: \(\operatorname {xVec}(Z(\gamma )) = 0\), so the first product in each term is zero. The second product gives \(\gamma _e \cdot [\operatorname {incident}(v,e)]\), which equals \([\operatorname {incident}(v,e)] \cdot \gamma _e\). Summing over all \(e\) yields \(\sum _e [\operatorname {incident}(v,e)] \cdot \gamma _e = (\partial \gamma )_v\).
For all \(\gamma \in \mathbb {Z}_2^E\) and \(v \in V\),
Commutation of Pauli operators is equivalent to their symplectic inner product being zero. By the previous theorem, \(\langle Z(\gamma ), A_v \rangle = (\partial \gamma )_v\), so \(\operatorname {PauliCommute}(Z(\gamma ), A_v) \Leftrightarrow (\partial \gamma )_v = 0\).
For all \(\gamma \in \mathbb {Z}_2^E\),
We rewrite \(\gamma \in \ker (\partial )\) as \((\partial \gamma )_v = 0\) for all \(v\) using the kernel characterization. For each direction: if \((\partial \gamma )_v = 0\) for all \(v\), then the commutation condition \((\partial \gamma )_v = 0\) holds for each \(v\), so \(Z(\gamma )\) commutes with each \(A_v\). Conversely, if \(Z(\gamma )\) commutes with each \(A_v\), then \((\partial \gamma )_v = 0\) for each \(v\) by the pointwise equivalence.
If \(P\) is a Pauli operator on \(V \oplus E\) with \(\operatorname {xVec}(P) = 0\), \(\operatorname {zVec}(P)_{\operatorname {inl}(v)} = 0\) for all \(v \in V\), and \([P, A_v] = 0\) for all \(v \in V\), then the edge \(Z\)-vector \(\gamma _e := \operatorname {zVec}(P)_{\operatorname {inr}(e)}\) lies in \(\ker (\partial )\).
We first rewrite the goal using the characterization that \(\gamma \in \ker (\partial )\) iff \(Z(\gamma )\) commutes with all \(A_v\). Let \(v \in V\) be arbitrary. We show that \(P = \operatorname {pureZHyperedgeOp}(\gamma )\) by extensionality: for \(\operatorname {xVec}\), both sides are zero (on vertex qubits by hypothesis \(\operatorname {xVec}(P) = 0\), and on edge qubits similarly); for \(\operatorname {zVec}\), on vertex qubits both are zero (by hypothesis for \(P\), by definition for \(Z(\gamma )\)), and on edge qubits both equal \(\gamma _e\) by construction. Since \(P = Z(\gamma )\), the commutation hypothesis \([P, A_v] = 0\) gives \([Z(\gamma ), A_v] = 0\).
A hypergraph is graph-like if every hyperedge has exactly \(2\) vertices:
For a graph-like hypergraph, the boundary of a single edge indicator sums to zero over all vertices: for any \(e_0 \in E\),
This holds because each edge has exactly \(2\) endpoints and \(2 \equiv 0 \pmod{2}\).
By the single-edge boundary formula, \((\partial \mathbf{1}_{e_0})_v = [\operatorname {incident}(v, e_0)]\), so \(\sum _v (\partial \mathbf{1}_{e_0})_v = \sum _v [\operatorname {incident}(v, e_0)]\). This sum counts the number of vertices in hyperedge \(e_0\), which is \(|\operatorname {hyperedgeVertices}(e_0)|\). Rewriting the sum as a Boolean indicator sum and using the filter characterization, we get \(|\operatorname {univ}.\operatorname {filter}(\operatorname {incident}(\cdot , e_0))| = |\operatorname {hyperedgeVertices}(e_0)| = 2\) by the graph-like hypothesis. Since \(2 = 0\) in \(\mathbb {Z}_2\) (verified by computation), the sum equals \(0\).
For CSS code initialization with physical qubits \(Q\), \(X\)-type check index set \(I\), and check supports \(\operatorname {xCheckSupport} : I \to \operatorname {Finset}(Q)\), the hypergraph boundary map with incidence \(\operatorname {incident}(q, i) \Leftrightarrow q \in \operatorname {xCheckSupport}(i)\) satisfies
for all \(\gamma \in \mathbb {Z}_2^I\) and \(q \in Q\).
This follows directly by simplification from the definition of \(\operatorname {hyperBoundaryMap}\): substituting the incidence relation \(\operatorname {incident}(v, i) := v \in \operatorname {xCheckSupport}(i)\) into the formula \((\partial \gamma )_q = \sum _i [\operatorname {incident}(q, i)] \cdot \gamma _i\) yields the stated identity.
The hypergraph generalization of the gauging framework satisfies the following four properties simultaneously:
All Gauss operators mutually commute: \(\forall \, v, w \in V\), \([A_v, A_w] = 0\).
Pure-\(Z\) edge operators commute with all \(A_v\) iff \(\gamma \in \ker (\partial )\): \(\forall \, \gamma \in \mathbb {Z}_2^E\), \(\gamma \in \ker (\partial ) \Leftrightarrow \forall \, v \in V,\; [Z(\gamma ), A_v] = 0\).
The coboundary \(\delta \) is the transpose of \(\partial \): \(\forall \, f \in \mathbb {Z}_2^V,\, \gamma \in \mathbb {Z}_2^E\), \(\sum _e (\delta f)_e \gamma _e = \sum _v f_v (\partial \gamma )_v\).
The Gauss subset product for the zero vector gives the identity: \(\operatorname {hyperGaussSubsetProduct}(0) = \mathbf{1}\).
This is the conjunction of the four results proved above:
follows from hyperGaussLaw_commute,
follows from ker_boundary_iff_commutes_all_gaussLaw,
follows from hyperCoboundaryMap_eq_transpose,
follows from hyperGaussSubsetProduct_zero.