51 Cor 2: Subsystem Code Parameters

Theorem 672 Number of Physical Qubits

✓

Let \(H\) be a finite group acting on \(\mathbb {F}_\ell \) for some \(\ell \geq 3\) odd, let \(X\) be a graph with \(H\)-action, let \(\Lambda \) be an \(s\)-regular \(H\)-invariant cell labeling, and let the action be cycle-compatible. Suppose:

\(\operatorname {hdim_components}\): \(\dim _{\mathbb {F}_2}(\operatorname {Tot}_1) = |X_1| + s \cdot |X_0|\), where \(\operatorname {Tot}_1\) denotes the degree-\(1\) component of the balanced product Tanner cycle complex;
\(\operatorname {hreg}\): \(2|X_1| = s \cdot |X_0|\) (i.e. the graph \(X\) is \(s\)-regular).

Then

\[ \dim _{\mathbb {F}_2}(\operatorname {Tot}_1) = 3|X_1|. \]

Proof ▶

Rewriting with the hypothesis \(\operatorname {hdim_components}\), the goal becomes \(|X_1| + s \cdot |X_0| = 3|X_1|\). By the regularity hypothesis \(\operatorname {hreg}\), we have \(s \cdot |X_0| = 2|X_1|\), so \(|X_1| + s \cdot |X_0| = |X_1| + 2|X_1| = 3|X_1|\). This follows by linear integer arithmetic.

Theorem 673 Logical Qubit Count

✓

The horizontal subsystem logical qubit space satisfies

\[ \dim _{\mathbb {F}_2}\bigl(\operatorname {HL}(X, \Lambda , \ell )\bigr) = \dim _{\mathbb {F}_2}\bigl(H_1^h(X, \Lambda , \ell )\bigr). \]

Proof ▶

Unfolding the definition of \(\operatorname {HL}\) as the range of the embedding map \(\operatorname {embH}\), it suffices to show that \(\operatorname {embH}\) is injective, and then apply the fact that the rank of the range of an injective linear map equals the rank of the domain.

We show injectivity of \(\operatorname {embH} = \operatorname {kunnethIso}^{-1} \circ \operatorname {incH}\). Suppose \(\operatorname {embH}(a) = \operatorname {embH}(b)\). Unfolding, we have \(\operatorname {kunnethIso}^{-1}(\operatorname {incH}(a)) = \operatorname {kunnethIso}^{-1}(\operatorname {incH}(b))\). By injectivity of \(\operatorname {kunnethIso}^{-1}\) (as a linear equivalence), we obtain \(\operatorname {incH}(a) = \operatorname {incH}(b)\). Unfolding \(\operatorname {incH}\) as the direct sum inclusion \(\operatorname {DirectSum.lof}(\cdot , 1)\), injectivity of direct sum inclusions then gives \(a = b\).

Theorem 674 Logical Qubit Lower Bound

✓

Let \(k_L = \dim _{\mathbb {F}_2}(\ker (\partial ^{\mathrm{quot}}))\) be the local code dimension, and let \(m = |(X/H)_1|\) be the number of edges of the quotient graph, satisfying \(m = |X_1|/\ell \) (the free action hypothesis). Assume \(s \geq 1\) and that the quotient Tanner code homology satisfies the Sipser–Spielman bound

\[ \dim _{\mathbb {F}_2}\bigl(H_1(C(X/H, L))\bigr) \geq \Bigl(\frac{2k_L}{s} - 1\Bigr) \cdot m. \]

Then

\[ \dim _{\mathbb {F}_2}\bigl(\operatorname {HL}(X, \Lambda , \ell )\bigr) \geq \Bigl(\frac{2k_L}{s} - 1\Bigr) \cdot \frac{|X_1|}{\ell }. \]

Proof ▶

We proceed in three steps.

Step 1. By Theorem 673,

\[ \dim _{\mathbb {F}_2}(\operatorname {HL}) = \dim _{\mathbb {F}_2}(H_1^h). \]

Step 2. By Theorem 636 (encoding rate for the circle complex),

\[ \dim _{\mathbb {F}_2}(H_1^h) = \dim _{\mathbb {F}_2}(H_1(C(X/H, L))). \]

Combining steps 1 and 2, we obtain

\[ \dim _{\mathbb {F}_2}(\operatorname {HL}) = \dim _{\mathbb {F}_2}(H_1(C(X/H, L))). \]

Step 3. Substituting the hypothesis \(m = |X_1|/\ell \) (i.e. \(\operatorname {hQuotEdges}\)) into the assumed Sipser–Spielman lower bound \(\operatorname {hQuotHomology}\), and combining with step 2 via the chain of equalities (cast to \(\mathbb {R}\)), the conclusion follows directly.

Theorem 675 Z-Distance Bound

✓

Let \(\alpha _{\mathrm{ho}}, \beta _{\mathrm{ho}} {\gt} 0\) and suppose the Tanner differential \(\partial ^{\mathrm{Tanner}}\) is \((\alpha _{\mathrm{ho}}, \beta _{\mathrm{ho}})\)-expanding. For every nontrivial homology class \(x \in H_1 \setminus \{ 0\} \) whose horizontal projection \(\pi _H(x) \neq 0\),

\[ \operatorname {wt}(x) \geq |X_1| \cdot \min \! \Bigl(\frac{\alpha _{\mathrm{ho}}}{2},\, \frac{\alpha _{\mathrm{ho}} \beta _{\mathrm{ho}}}{4}\Bigr). \]

Proof ▶

This is a direct application of Theorem 659 (homological distance bound, horizontal case) with the given expansion parameters and the hypotheses \(x \neq 0\) and \(\pi _H(x) \neq 0\).

Theorem 676 X-Distance Bound, Vertical Case

✓

Let \(\alpha _{\mathrm{co}}, \beta _{\mathrm{co}} {\gt} 0\) and suppose the coboundary map is \((\alpha _{\mathrm{co}}, \beta _{\mathrm{co}})\)-expanding. For every nontrivial cohomology class \(x \in H_1 \setminus \{ 0\} \) whose vertical co-projection \(\tilde{\pi }_V(x) \neq 0\),

\[ \operatorname {wt}(x) \geq (|X_0| \cdot s) \cdot \min \! \Bigl(\frac{\alpha _{\mathrm{co}}}{2},\, \frac{\alpha _{\mathrm{co}} \beta _{\mathrm{co}}}{4}\Bigr). \]

Since \(s\)-regularity gives \(s \cdot |X_0| = 2|X_1|\), this is equivalent to

\[ \operatorname {wt}(x) \geq \min \! \Bigl(\alpha _{\mathrm{co}} |X_1|,\, \frac{\alpha _{\mathrm{co}} \beta _{\mathrm{co}} |X_1|}{2}\Bigr). \]

Proof ▶

This is a direct application of Theorem 668 (cohomological distance bound, vertical case) with the given expansion parameters and the hypotheses \(x \neq 0\) and \(\tilde{\pi }_V(x) \neq 0\).

Theorem 677 X-Distance Bound, Horizontal Case

✓

Let \(\alpha _{\mathrm{co}}, \beta _{\mathrm{co}} {\gt} 0\), \(s \geq 1\), and suppose the coboundary map is \((\alpha _{\mathrm{co}}, \beta _{\mathrm{co}})\)-expanding. For every nontrivial cohomology class \(x \in H_1 \setminus \{ 0\} \) whose vertical co-projection satisfies \(\tilde{\pi }_V(x) = 0\) (purely horizontal class),

\[ \operatorname {wt}(x) \geq \ell \cdot \min \! \Bigl(\frac{\alpha _{\mathrm{co}}}{4s},\, \frac{\alpha _{\mathrm{co}} \beta _{\mathrm{co}}}{4s}\Bigr). \]

Proof ▶

This is a direct application of Theorem 669 (cohomological distance bound, horizontal case) with the given expansion parameters and the hypotheses \(x \neq 0\) and \(\tilde{\pi }_V(x) = 0\).

Theorem 678 Combined X-Distance Bound

✓

\[ \operatorname {wt}(x) \geq \min \! \left( (|X_0| \cdot s) \cdot \min \! \Bigl(\frac{\alpha _{\mathrm{co}}}{2},\, \frac{\alpha _{\mathrm{co}} \beta _{\mathrm{co}}}{4}\Bigr),\; \ell \cdot \min \! \Bigl(\frac{\alpha _{\mathrm{co}}}{4s},\, \frac{\alpha _{\mathrm{co}} \beta _{\mathrm{co}}}{4s}\Bigr) \right). \]

Using \(s\)-regularity \(s \cdot |X_0| = 2|X_1|\), this gives

\[ D_X \geq \min \! \Bigl(\alpha _{\mathrm{co}} |X_1|,\; \tfrac {\alpha _{\mathrm{co}} \beta _{\mathrm{co}} |X_1|}{2},\; \tfrac {\ell \alpha _{\mathrm{co}}}{4s},\; \tfrac {\ell \alpha _{\mathrm{co}} \beta _{\mathrm{co}}}{4s}\Bigr). \]

Proof ▶

We perform a case analysis on whether the vertical co-projection \(\tilde{\pi }_V(x)\) is zero or not.

Case 1: \(\tilde{\pi }_V(x) = 0\) (purely horizontal). We apply Theorem 677 to obtain

\[ \operatorname {wt}(x) \geq \ell \cdot \min \! \Bigl(\frac{\alpha _{\mathrm{co}}}{4s},\, \frac{\alpha _{\mathrm{co}} \beta _{\mathrm{co}}}{4s}\Bigr). \]

Since the right-hand side equals the second term of the outer minimum, the conclusion follows from \(\min (A, B) \leq B\).

Case 2: \(\tilde{\pi }_V(x) \neq 0\) (nontrivial vertical component). We apply Theorem 676 to obtain

\[ \operatorname {wt}(x) \geq (|X_0| \cdot s) \cdot \min \! \Bigl(\frac{\alpha _{\mathrm{co}}}{2},\, \frac{\alpha _{\mathrm{co}} \beta _{\mathrm{co}}}{4}\Bigr). \]

Since the right-hand side equals the first term of the outer minimum, the conclusion follows from \(\min (A, B) \leq A\).

Theorem 679 Combined X-Distance Bound for Nontrivial Classes

✓

Under the same hypotheses as Theorem 678, for every nontrivial homology class \(x \in H_1 \setminus \{ 0\} \),

Note: The existence of nontrivial homology classes for specific graph families (Cayley expanders) is a constructive combinatorial result from the balanced product code construction [ .

Proof ▶

This is a direct application of Theorem 678 with the given expansion parameters and the hypothesis \(x \neq 0\).

[Paper Corrections] redErrata. The following errors were identified in the original paper and corrected in this formalization:

Paper Corollary (cor:distanceboundssybsystemcode) states \(D_X \geq \min \{ \alpha _{\mathrm{co}}|X_1|,\, \alpha _{\mathrm{co}}|X_1|/2,\, \ell \alpha _{\mathrm{co}}/(4s),\, \ell \alpha _{\mathrm{co}}\beta _{\mathrm{co}}/(4s)\} \) but the second term is missing \(\beta _{\mathrm{co}}\). From Theorem thm:distco Case 1, \(|x| \geq |X_0|s \cdot \min \{ \alpha _{\mathrm{co}}/2,\, \alpha _{\mathrm{co}}\beta _{\mathrm{co}}/4\} \). Substituting \(|X_0|s = 2|X_1|\) gives \(\min \{ \alpha _{\mathrm{co}}|X_1|,\, \alpha _{\mathrm{co}}\beta _{\mathrm{co}}|X_1|/2\} \), so the correct second term should be \(\alpha _{\mathrm{co}}\beta _{\mathrm{co}}|X_1|/2\), not \(\alpha _{\mathrm{co}}|X_1|/2\).