43 Rem 20: Cohen Scheme as Gauging
This chapter establishes that the Cohen et al. scheme for logical measurement can be recovered as a hypergraph gauging measurement. The construction restricts Z-type checks to the support of an irreducible X logical \(L\), forming a hypergraph whose kernel is \(\{ 0, L\} \), then builds a layered structure with dummy vertices, chain connections, and hypergraph copies. The Cross et al. modification and product measurement via bridge edges are also formalized.
The Cohen hypergraph \(\mathrm{CohenHypergraph}(W, \mathrm{numChecks})\) is a hypergraph with vertex set \(\mathrm{Fin}(W)\) and hyperedge set \(\mathrm{Fin}(\mathrm{numChecks})\). The vertices represent the \(W\) qubits in \(\mathrm{supp}(L)\), and the hyperedges are the restricted Z-type checks.
The logical vector \(\mathbf{L} \in (\mathrm{Fin}(W) \to \mathbb {Z}/2\mathbb {Z})\) is the all-ones vector, defined by \(\mathbf{L}(v) = 1\) for all \(v\). This represents the logical operator \(L = \prod _{v \in \mathrm{supp}(L)} X_v\).
If \(W \ge 1\), then \(\mathrm{logicalVector}(W) \neq 0\).
Assume for contradiction that \(\mathrm{logicalVector}(W) = 0\). Then by function extensionality at the index \(\langle 0, hW \rangle \in \mathrm{Fin}(W)\), we obtain \(\mathrm{logicalVector}(W)(\langle 0, hW \rangle ) = 0\). By the definition of \(\mathrm{logicalVector}\), this value equals \(1\), yielding a contradiction via simplification.
The Cohen kernel property for a Cohen hypergraph \(HG\) states that the operator kernel of \(HG\) is exactly \(\{ 0, L\} \):
This is the defining property of the Cohen scheme: the restriction of Z-type checks to \(\mathrm{supp}(L)\) has kernel spanned by the logical operator \(L\) (i.e., \(L\) is irreducible).
When the Cohen kernel property holds for \(HG\), the logical vector \(\mathbf{L}\) is in the operator kernel of \(HG\).
Rewriting the membership condition using the Cohen kernel property, it suffices to show \(\mathbf{L} = 0 \lor \mathbf{L} = \mathbf{L}\). This follows from \(\mathrm{Or.inr}(\mathrm{rfl})\).
When the Cohen kernel property holds, every element \(x\) in the operator kernel of \(HG\) satisfies \(x = 0\) or \(x = \mathbf{L}\).
Let \(x\) be an element in the operator kernel. By the forward direction of the Cohen kernel property applied to \(x\), we obtain \(x = 0 \lor x = \mathbf{L}\).
When the Cohen kernel property holds, both \(0\) and \(\mathbf{L}\) are in the operator kernel of \(HG\).
We construct the pair. For \(0 \in \mathrm{operatorKernel}(HG)\), we use the backward direction of the kernel property with \(\mathrm{Or.inl}(\mathrm{rfl})\). For \(\mathbf{L} \in \mathrm{operatorKernel}(HG)\), we use the backward direction with \(\mathrm{Or.inr}(\mathrm{rfl})\).
The layered construction has vertex type \(\mathrm{Fin}(d+1) \times \mathrm{Fin}(W)\), where layer \(0\) is the original (base) layer and layers \(1, \ldots , d\) are dummy layers. The total number of vertices is \((d+1) \cdot W\).
By simplification using the cardinality of the product type \(\mathrm{Fin}(d+1) \times \mathrm{Fin}(W)\) and the cardinality of finite types.
The base layer vertices are the vertices \((l, i)\) with \(l = 0\):
These correspond to the original qubits in \(\mathrm{supp}(L)\).
The dummy layer vertices are the vertices \((l, i)\) with \(l \neq 0\):
The base layer has exactly \(W\) vertices: \(|\mathrm{baseLayerVertices}(W, d)| = W\).
By simplification, the filtered set \(\{ v \mid v_1 = 0\} \) equals \(\{ 0\} \times \mathrm{Fin}(W)\), shown by extensionality: for each pair \((l, i)\), membership in the filter is equivalent to \(l = 0\) and \(i \in \mathrm{Fin}(W)\). The cardinality of \(\{ 0\} \times \mathrm{Fin}(W)\) is \(1 \cdot W = W\).
The dummy layers have exactly \(d \cdot W\) vertices: \(|\mathrm{dummyLayerVertices}(W, d)| = d \cdot W\).
We use the total vertex count \((d+1) \cdot W\) and the base layer cardinality \(W\). The universe partitions into base and dummy layer vertices (shown by extensionality and the fact that for any vertex, either \(v_1 = 0\) or \(v_1 \neq 0\)). These two sets are disjoint (a vertex cannot satisfy both \(v_1 = 0\) and \(v_1 \neq 0\)). By the cardinality of a disjoint union, \((d+1) \cdot W = W + |\mathrm{dummyLayerVertices}|\). Since \((d+1) \cdot W = W + d \cdot W\) by ring arithmetic, the result \(|\mathrm{dummyLayerVertices}| = d \cdot W\) follows by integer arithmetic.
The layered hyperedge type combines two kinds of edges:
Chain edge \(\mathrm{chain}(l, i)\): connects vertex \((l, i)\) to \((l+1, i)\) for \(l \in \mathrm{Fin}(d)\) and \(i \in \mathrm{Fin}(W)\).
Hypergraph copy \(\mathrm{hypergraphCopy}(\ell , c)\): a copy of check \(c\) in layer \(\ell \), for \(\ell \in \mathrm{Fin}(d+1)\) and \(c \in \mathrm{Fin}(\mathrm{numChecks})\).
The number of chain edges is \(d \cdot W\).
By the cardinality of the image under an injective map. Injectivity is shown by the fact that the chain constructor is injective on pairs: if \(\mathrm{chain}(l_1, i_1) = \mathrm{chain}(l_2, i_2)\) then \(l_1 = l_2\) and \(i_1 = i_2\). The domain \(\mathrm{Fin}(d) \times \mathrm{Fin}(W)\) has cardinality \(d \cdot W\).
The number of hypergraph copy edges is \((d+1) \cdot \mathrm{numChecks}\).
By the cardinality of the image under an injective map. Injectivity follows from the fact that the hypergraphCopy constructor is injective on pairs. The domain \(\mathrm{Fin}(d+1) \times \mathrm{Fin}(\mathrm{numChecks})\) has cardinality \((d+1) \cdot \mathrm{numChecks}\).
The layered Cohen construction builds a hypergraph from the original Cohen hypergraph \(HG\). The incidence function is defined by:
For a chain edge \(\mathrm{chain}(l, i)\): the incidence set is \(\{ (l, i),\, (l+1, i)\} \).
For a hypergraph copy \(\mathrm{hypergraphCopy}(\ell , c)\): the incidence set is the image of \(HG\)’s incidence of check \(c\) under the embedding \(v \mapsto (\ell , v)\).
Each chain edge is a 2-element hyperedge: for all \(l \in \mathrm{Fin}(d)\) and \(i \in \mathrm{Fin}(W)\),
By simplification using the definition of the layered construction, the incidence set of a chain edge is \(\{ (l, i), (l+1, i)\} \). The cardinality is \(2\) because the two endpoints are distinct: \((l, i) \neq (l+1, i)\) since \(l \neq l+1\) as elements of \(\mathrm{Fin}(d+1)\).
Hypergraph copy edges have the same cardinality as the original: for all layers \(\ell \) and checks \(c\),
By simplification using the definition of the layered construction, the incidence set is the image of \(HG\)’s incidence under an injective embedding. The cardinality of a mapped finset equals the cardinality of the original.
The base logical vector is all-ones on the base layer and zeros elsewhere:
The all-layers logical vector is the all-ones vector on the full layered vertex set:
This represents the full product of \(L\) across all layers.
If the Cohen kernel property holds for \(HG\), then the all-layers logical vector is in the operator kernel of the layered Cohen construction.
Rewriting using the kernel membership criterion, we must show that for every hyperedge \(e\), the sum of the all-layers logical vector over the incidence of \(e\) vanishes. We consider two cases:
Chain edge \(\mathrm{chain}(l, i)\): By simplification, the incidence is \(\{ (l, i), (l+1, i)\} \). The sum is \(1 + 1 = 0\) in \(\mathbb {Z}/2\mathbb {Z}\), verified by computation.
Hypergraph copy \(\mathrm{hypergraphCopy}(\ell , c)\): By simplification and rewriting the sum over the mapped finset, the sum equals the sum of the constant \(1\) function over \(HG\)’s incidence of check \(c\). Since \(\mathbf{L}\) is in the kernel of \(HG\) (by the Cohen logical in kernel theorem), this sum vanishes.
For any \(l \in \mathrm{Fin}(d)\) and \(i \in \mathrm{Fin}(W)\), the layers \(l\) and \(l+1\) are distinct as elements of \(\mathrm{Fin}(d+1)\).
By simplification using the \(\mathrm{Fin}\) extensionality lemma and the fact that \(l \neq l + 1\).
For \(d \ge 1\) and any vertex \(i \in \mathrm{Fin}(W)\), the chain from layer \(0\) to layer \(d\) has exactly \(d\) edges: there exists \(\mathrm{edges} \subseteq \mathrm{Fin}(d)\) with \(|\mathrm{edges}| = d\) and \(\mathrm{edges} = \mathrm{Fin}(d)\).
For any \(i\), we take \(\mathrm{edges} = \mathrm{Fin}(d)\) (the full universe). Then \(|\mathrm{Fin}(d)| = d\) and \(\mathrm{Fin}(d) = \mathrm{Fin}(d)\) holds by reflexivity.
The Cross et al. vertex type uses \(m\) layers (where \(m {\lt} d\)) instead of \(d\): the vertex set is \(\mathrm{Fin}(m+1) \times \mathrm{Fin}(W)\).
If \(m {\lt} d\) and \(W \ge 1\), then the Cross et al. construction has strictly fewer vertices:
Since \(m {\lt} d\), we have \(m + 1 {\lt} d + 1\). Multiplying both sides by \(W \ge 1\) preserves the strict inequality.
The Cross et al. construction with \(m {\lt} d\) layers is defined as \(\mathrm{LayeredCohenConstruction}(W, m, \mathrm{numChecks}, HG)\), i.e., the same layered construction but with parameter \(m\) instead of \(d\).
If the Cohen kernel property holds for \(HG\), then the all-layers logical vector for the \(m\)-layer construction is in the operator kernel of the Cross et al. construction.
This follows directly from the layered kernel theorem applied with parameter \(m\) instead of \(d\).
The product vertex type for combining two ancilla systems is the disjoint union \(\mathrm{Fin}(W_1) \oplus \mathrm{Fin}(W_2)\).
The total vertex count of the product measurement graph is \(W_1 + W_2\).
By simplification using the cardinality of the sum type and the cardinality of finite types.
A bridge edge configuration consists of:
A finset of bridge connections \(\mathrm{bridges} \subseteq \mathrm{Fin}(W_1) \times \mathrm{Fin}(W_2)\), specifying which pairs of vertices to connect between the two systems.
A proof that at least one bridge edge exists (\(\mathrm{bridges}\) is nonempty).
The product hyperedge type has three constructors:
\(\mathrm{left}(h)\): a check from the first ancilla system, indexed by \(h \in \mathrm{Fin}(nc_1)\).
\(\mathrm{right}(h)\): a check from the second ancilla system, indexed by \(h \in \mathrm{Fin}(nc_2)\).
\(\mathrm{bridge}(i, j)\): a bridge edge connecting vertex \(i \in \mathrm{Fin}(W_1)\) to vertex \(j \in \mathrm{Fin}(W_2)\).
The product measurement hypergraph combines two hypergraphs \(HG_1\) and \(HG_2\) with bridge edges. Its incidence function is:
For \(\mathrm{left}(h)\): the image of \(HG_1.\mathrm{incidence}(h)\) under \(\mathrm{inl}\).
For \(\mathrm{right}(h)\): the image of \(HG_2.\mathrm{incidence}(h)\) under \(\mathrm{inr}\).
For \(\mathrm{bridge}(i, j)\): the set \(\{ \mathrm{inl}(i), \mathrm{inr}(j)\} \).
Bridge edges are 2-element hyperedges: for all \(i \in \mathrm{Fin}(W_1)\) and \(j \in \mathrm{Fin}(W_2)\),
By simplification using the definition of the product measurement graph, the incidence is \(\{ \mathrm{inl}(i), \mathrm{inr}(j)\} \). The cardinality is \(2\) because \(\mathrm{inl}(i) \neq \mathrm{inr}(j)\) (elements from different sides of a sum type are distinct).
Left check edges have the same cardinality as in the original first system:
By simplification, the incidence of a left check is the image of \(HG_1\)’s incidence under the injective map \(\mathrm{inl}\). The cardinality of a mapped finset equals the original cardinality.
Right check edges have the same cardinality as in the original second system:
By simplification, the incidence of a right check is the image of \(HG_2\)’s incidence under the injective map \(\mathrm{inr}\). The cardinality of a mapped finset equals the original cardinality.
The product logical vector is the all-ones vector on the combined vertex set \(\mathrm{Fin}(W_1) \oplus \mathrm{Fin}(W_2)\):
If the all-ones vector \(\mathbf{1}\) is in the operator kernel of both \(HG_1\) and \(HG_2\), then the product logical vector is in the operator kernel of the product measurement graph.
Rewriting kernel membership using the characterization \(\sum _{v \in \mathrm{incidence}(e)} f(v) = 0\) for all hyperedges \(e\), and applying the same rewriting to the hypotheses \(hL_1\) and \(hL_2\), we consider three cases:
Left check \(\mathrm{left}(h)\): By simplification and rewriting the sum over the mapped finset, the sum reduces to \(\sum _{v \in HG_1.\mathrm{incidence}(h)} 1\), which vanishes by the hypothesis \(hL_1\) applied to \(h\).
Right check \(\mathrm{right}(h)\): Similarly, the sum reduces to \(\sum _{v \in HG_2.\mathrm{incidence}(h)} 1\), which vanishes by \(hL_2\) applied to \(h\).
Bridge \(\mathrm{bridge}(i, j)\): By simplification and the pair sum formula (using \(\mathrm{inl}(i) \neq \mathrm{inr}(j)\)), the sum is \(1 + 1 = 0\) in \(\mathbb {Z}/2\mathbb {Z}\), verified by computation.
The sum of all Gauss’s law vertex supports over the layered construction equals the all-ones function:
This is an instantiation of the hypergraph Gauss’s law property.
This follows directly from the general hypergraph theorem that the sum of Gauss’s law vertex supports equals the all-ones vector, applied to the layered Cohen construction.
The layered construction is \(k\)-local when the original Cohen hypergraph is \(k\)-local and \(k \ge 2\).
Let \(e\) be any hyperedge. We consider two cases:
Chain edge \(\mathrm{chain}(l, i)\): By the \(k\)-locality condition, we must show \(|\mathrm{incidence}(e)| \le k\). By the chain-edge-is-pair result, \(|\mathrm{incidence}(\mathrm{chain}(l, i))| = 2 \le k\) since \(k \ge 2\).
Hypergraph copy \(\mathrm{hypergraphCopy}(\ell , c)\): By the hypergraph copy cardinality result, \(|\mathrm{incidence}(\mathrm{hypergraphCopy}(\ell , c))| = |HG.\mathrm{incidence}(c)| \le k\), where the last inequality follows from the hypothesis that \(HG\) is \(k\)-local.