Skip to content

Quantum Tanner Explicit Gap Reduction

Claim/Theorem

For one parity \(i\in\{0,1\}\) of a quantum Tanner code, let \(I_i\) be the square-vertex incidence graph from [[quantum-tanner-incidence-spectral-gap.md]], and let \(H_i\) be the constant local gadget determined by the chosen basis \(\beta_i\) of local generators: its left vertices are the local coordinates in \(A\times B\), its right vertices are the basis elements of \(\beta_i\), and a coordinate is connected to a basis element when that basis vector is nonzero on that coordinate.

If

\[ a_i:=\min_{c}\deg_{H_i}(c)>0 \]

and

\[ \eta_i:=\min\bigl\{\,|\partial_{H_i}W|:\emptyset\neq W\subsetneq V(H_i),\;W\cap\beta_i\notin\{\emptyset,\beta_i\}\bigr\}>0, \]

then the chosen parity Tanner graph is a local expander. The reason is:

  1. [[quantum-tanner-diagonal-expansion-structure.md]] gives a constant spectral gap for the one-parity diagonal graph \(G_i^\square\), while [[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. [[quantum-tanner-local-generator-blowup.md]] identifies the chosen parity Tanner graph as exactly the lift \(T(I_i,H_i)\).
  4. [[incidence-expansion-to-parity-tanner-expansion.md]] then upgrades the incidence expansion to Tanner expansion.

Therefore the remaining explicit-family gap for quantum Tanner codes has been reduced to two concrete tasks:

  • invoke the standard spectral-gap-to-expansion step for \(I_i\),
  • choose a local basis for which the finite constants \(a_i>0\) and \(\eta_i>0\) hold.

Moreover, [[dual-distance-excludes-zero-coordinates.md]] and [[tensor-product-preserves-no-zero-coordinates.md]] show that the second task is already solved deterministically under the paper's own Theorem 17 distance assumptions: once \(\delta\Delta\ge 2\), the local tensor codes have no zero coordinates, and [[connected-basis-for-nonzero-coordinate-code.md]] then supplies a connected basis forcing \(\eta_i\ge 1\) and \(a_i\ge 1\). The earlier random-model node [[random-local-codes-generic-no-zero-coordinates.md]] is therefore now best viewed as a corollary for the paper's probabilistic existence mechanism, not as the main frontier.

Because a full CSS syndrome-extraction round must include the extraction of each parity, local expansion for either parity Tanner graph is already enough to force the same asymptotic lower bound for the full round.

Dependencies

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

Conflicts/Gaps

  • The node is still conditional on invoking a connected-basis choice, but the local-gadget obstruction has now been reduced to the deterministic distance hypotheses recorded in [[quantum-tanner-theorem17-parity-expander.md]].
  • The spectral-to-incidence-expansion chain is now explicit on the graph, but it still works via the diagonal graph \(G_i^\square\) rather than a direct biregular Cheeger theorem for \(I_i\).
  • The conclusion is for one parity Tanner graph. This is enough for a round lower bound, but it does not yet assert that the full stabilizer Tanner graph is itself a local expander.

Sources

  • 10.48550/arXiv.2202.13641
  • 10.1007/BF02579166