Skip to content

Cross-Cut Stabilizer Rank Rank Formula

Claim/Theorem

Let \(H\) be any full-row-rank binary matrix whose row space is the stabilizer space \(\mathcal S\), and let the qubit set be partitioned as \(L\sqcup R\). Write

\[ H=\begin{bmatrix}H_L\mid H_R\end{bmatrix} \]

for the corresponding column split. Then the intrinsic cross-cut stabilizer rank from [[cross-cut-stabilizer-rank.md]] satisfies

\[ \chi_L(\mathcal S) \;=\; \operatorname{rank}(H_L)+\operatorname{rank}(H_R)-\operatorname{rank}(H). \]

Equivalently, if \(C=\ker H\) is the classical code with parity-check matrix \(H\), then

\[ \chi_L(\mathcal S) \;=\; \dim(C|_L)+\dim(C|_R)-\dim(C), \]

so \(\chi_L(\mathcal S)\) is exactly the usual connectivity function of the column matroid of \(H\), or equivalently of the classical code \(C\).

Proof sketch:

  1. From [[cross-cut-stabilizer-rank.md]],
\[ \chi_L(\mathcal S)=\dim\mathcal S-\dim\mathcal S_L-\dim\mathcal S_R, \]

because \(\mathcal S_L\cap\mathcal S_R=\{0\}\). 2. The projection of \(\mathcal S\) onto the \(R\) coordinates has dimension \(\operatorname{rank}(H_R)\), so

\[ \dim\mathcal S_L=\dim\mathcal S-\operatorname{rank}(H_R). \]

Similarly,

\[ \dim\mathcal S_R=\dim\mathcal S-\operatorname{rank}(H_L). \]

Substituting gives the rank formula. 3. For the code expression, use the standard projection identity

\[ \dim(C|_L)=|L|-\dim\mathcal S_L, \qquad \dim(C|_R)=|R|-\dim\mathcal S_R, \]

and \(\dim(C)=|L|+|R|-\dim\mathcal S\).

This makes the current frontier more concrete: proving a linear lower bound on \(\chi_L(\mathcal S)\) is the same as proving linear code or matroid connectivity across balanced qubit partitions.

Dependencies

  • [[cross-cut-stabilizer-rank.md]]

Conflicts/Gaps

  • This node makes \(\chi_L(\mathcal S)\) operational, but it does not yet provide a lower bound for the parity-check matrices coming from Quantum Tanner codes or other expander-style QLDPC families.
  • The equivalence is for a fixed stabilizer space \(\mathcal S\) viewed as a binary linear space on qubit coordinates. Turning this into a hardware-depth theorem still requires [[stabilizer-cut-rank-functional.md]].
  • The current graph does not yet contain a theorem saying that Tanner expansion of a chosen presentation forces linear column-matroid connectivity of its parity-check matrix across balanced cuts.

Sources

  • 10.48550/arXiv.2109.14599
  • 10.48550/arXiv.0805.2199