Skip to content

Quantum Tanner Theorem 17 Parity Expander

Claim/Theorem

Fix \(\Delta>4\) large enough, and let \(C_A,C_B\) be local codes of length \(\Delta\) satisfying the hypotheses of Theorem 17 in Leverrier and Zemor:

  • \(0<\dim C_A\le \rho\Delta\) and \(\dim C_B=\Delta-\dim C_A\),
  • the minimum distances of \(C_A,C_B,C_A^\perp,C_B^\perp\) are all at least \(\delta\Delta\),
  • the required robustness and puncturing-resistance assumptions hold.

Then, for each parity \(i\in\{0,1\}\), one can choose a local generator basis so that the corresponding parity Tanner graph is a bounded-degree local expander.

The proof chain on the current graph is:

  1. [[quantum-tanner-diagonal-expansion-structure.md]] gives a constant spectral gap for the one-parity diagonal graph \(G_i^\square\), and [[quantum-tanner-incidence-spectral-gap.md]] identifies \(I_i\) as its vertex-edge incidence graph.
  2. [[spectral-gap-to-regular-graph-expansion.md]] and [[regular-graph-expansion-to-incidence-expansion.md]] convert that regular-graph spectral gap into local expansion of \(I_i\).
  3. Because \(\delta\Delta\ge 2\) for large enough \(\Delta\), [[dual-distance-excludes-zero-coordinates.md]] implies that each of \(C_A,C_B,C_A^\perp,C_B^\perp\) has no zero coordinates.
  4. [[tensor-product-preserves-no-zero-coordinates.md]] then implies that the local parity code \(L_i\) is also free of zero coordinates, where
\[ L_0=C_A\otimes C_B, \qquad L_1=C_A^\perp\otimes C_B^\perp. \]
  1. [[connected-basis-for-nonzero-coordinate-code.md]] yields a connected basis of \(L_i\), so the constant-size gadget in [[quantum-tanner-local-generator-blowup.md]] has strictly positive coordinate degree and strictly positive partial-boundary constant.
  2. [[incidence-expansion-to-parity-tanner-expansion.md]] then upgrades the incidence expansion of \(I_i\) to local expansion of the chosen parity Tanner graph.

Therefore the earlier random-model gadget step is not actually needed to obtain a parity-Tanner local-expander theorem. The paper's own Theorem 17 distance assumptions already force the local gadget condition deterministically.

Dependencies

  • [[quantum-tanner-diagonal-expansion-structure.md]]
  • [[quantum-tanner-incidence-spectral-gap.md]]
  • [[spectral-gap-to-regular-graph-expansion.md]]
  • [[regular-graph-expansion-to-incidence-expansion.md]]
  • [[dual-distance-excludes-zero-coordinates.md]]
  • [[tensor-product-preserves-no-zero-coordinates.md]]
  • [[connected-basis-for-nonzero-coordinate-code.md]]
  • [[quantum-tanner-local-generator-blowup.md]]
  • [[incidence-expansion-to-parity-tanner-expansion.md]]

Conflicts/Gaps

  • This is a deterministic conditional theorem about any component-code choice satisfying Theorem 17. It is still not an explicit deterministic construction of such component codes.
  • The node proves local expansion for the chosen parity Tanner graphs, not yet for an arbitrary stabilizer presentation of the same quantum code.
  • The conclusion still lives inside the current Tanner-expansion route to the stabilizer-measurement lower bound. It does not by itself prove the full compiler-independent CD(T_n,\mathfrak G) conjecture.

Sources

  • 10.48550/arXiv.2202.13641
  • 10.1007/BF02579166
  • 10.48550/arXiv.2109.14599