Skip to content

Quantum Tanner Constituent Tanner Code Is Locally Testable

Claim/Theorem

Under the hypotheses of Leverrier and Zemor's main robustness theorem, the classical Tanner constituent used in the Quantum Tanner construction is a constant-query locally testable code.

More precisely, let \(C_A=C_B\) be a length-\Delta code of rate \(\rho\in(0,1)\) and distance \delta\Delta, and suppose the associated dual tensor code satisfies the robustness hypothesis of Theorem 1 in [Leverrier--Zemor 2022]. Let

\[ C_{\mathrm{LTC}} \;:=\; T(G^\square, C_A\otimes C_B). \]

Then:

  1. \(C_{\mathrm{LTC}}\) is exactly the Dinur--Evra--Livne locally testable code built on the same square complex.

  2. It has parameters

    \[ [n,\;k\ge (2\rho^2-1)n,\; d\ge \delta^2(\delta-\lambda/\Delta)n], \]

    where \(\lambda\) is the second eigenvalue of the constituent Ramanujan Cayley graphs.

  3. The natural local tester that samples one vertex and checks whether the local view lies in the tensor code uses \Delta^2 queries and achieves constant soundness

    \[ \zeta(x)\;\ge\;\kappa\,\frac{d(x,C_{\mathrm{LTC}})}{n}, \qquad \kappa=\min\!\left\{\frac{a}{a+1},\frac{\delta}{8\Delta^{3/2+\varepsilon}}\right\}, \]

    for some constant \(a>0\) independent of \(n\).

    So at least one classical constituent naturally adjacent to the Quantum Tanner construction has much stronger structure than mere LDPC sparsity: it is a constant-rate, linear-distance LTC on a fixed local test.

This does not yet solve Conjecture 3, but it identifies a concrete candidate source of the extra structure missing from the current cutwidth route. In particular, it makes the following question precise: can constant-query local testability force large trellis-width, branchwidth, or balanced-cut rank-connectivity?

Dependencies

  • None.

Conflicts/Gaps

  • This node is about the Dinur--Evra--Livne classical Tanner code attached to the same square complex, not directly about the constituent CSS codes \(C_0=\ker H_0\) and \(C_1=\ker H_1\) that appear in the quantum code.
  • Therefore it does not immediately bypass [[qldpc-css-constituent-codes-not-good.md]].
  • The current graph contains no theorem linking local testability of a classical code to large trellis-width, branchwidth, or intrinsic cut-rank. That is now an explicit frontier.

Sources

  • 10.1145/3519935.3520024
  • 10.48550/arXiv.2202.13641