Skip to content

Quantum Tanner Incidence Spectral Gap

Claim/Theorem

Fix one parity \(i\in\{0,1\}\). Let \(I_i\) be the bipartite graph whose left vertices are the square qubits \(Q\) of the left-right Cayley complex and whose right vertices are the complex vertices \(V_i\), with an edge whenever a square is incident to a vertex in \(V_i\). Equivalently, \(I_i\) is the vertex-edge incidence graph of the diagonal graph \(G_i^\square\).

If \(G_i^\square\) is \(\Delta^2\)-regular, then the unsigned incidence matrix \(B_i\) of \(I_i\) satisfies

\[ B_i B_i^\top \;=\; A(G_i^\square)+\Delta^2 I. \]

Hence, if the nontrivial adjacency eigenvalues of \(G_i^\square\) are bounded in absolute value by \(4\Delta\) as in [[quantum-tanner-diagonal-expansion-structure.md]], then the adjacency eigenvalues of \(I_i\) are

\[ \pm\sqrt{\Delta^2+\lambda_j(G_i^\square)}. \]

In particular, the largest eigenvalue is \(\sqrt{2}\,\Delta\) and every nontrivial eigenvalue has absolute value at most

\[ \sqrt{\Delta^2+4\Delta}. \]

Therefore the one-parity square-vertex incidence graph underlying the quantum Tanner construction has a constant normalized spectral gap for every fixed sufficiently large \(\Delta\).

Dependencies

  • [[quantum-tanner-diagonal-expansion-structure.md]]

Conflicts/Gaps

  • This is a spectral statement about the base incidence graph \(I_i\), not yet a Cheeger-expansion statement for the chosen X- or Z-Tanner graph.
  • The node applies to one parity at a time. It does not by itself give expansion of the full Tanner graph containing both X and Z generators.
  • Passing from the incidence graph \(I_i\) to the actual stabilizer Tanner graph still requires the local-basis blow-up analysis isolated in [[quantum-tanner-local-generator-blowup.md]].

Sources

  • 10.48550/arXiv.2202.13641