Skip to content

Lesson 07 - CSS and QLDPC Codes

Prerequisites And Diagnostic Checks

Ask:

  1. What does \(H_XH_Z^T=0\) check?
  2. Why are logical operators quotient or coset objects rather than arbitrary Pauli strings?
  3. What does \(k,d=\Theta(n)\) mean?
  4. Why might expansion help distance but hurt 2D routing?

Concrete Motivation From The Research Map

Now the algebra, graph, and expansion pieces meet. The question is not just "what is a QLDPC code?" The research question is:

How can an asymptotically good bounded-degree quantum code exist, and why should such a code stress a 2D machine?

Quantum Tanner codes are the anchor family in this course because they are theorem-level good QLDPC codes with explicit expander scaffolding.

CSS Construction Revisited

Build a CSS code from two classical binary codes satisfying the appropriate dual containment. In parity-check form, the stabilizer commutativity condition is

\[ H_XH_Z^T=0. \]

Rows of \(H_X\) give X-type checks. Rows of \(H_Z\) give Z-type checks. Columns are qubits.

For a CSS code from classical codes \(C_X\) and \(C_Z\), the number of logical qubits is

\[ k=k_X+k_Z-n \]

in the standard compatible-code convention. This formula is useful, but the deeper issue is distance.

Logical Operators And Distance

Logical operators are Pauli operators that commute with all stabilizers but are not themselves stabilizers.

In CSS language, X-logicals and Z-logicals are quotient objects. A typical expression is:

\[ C_X/C_Z^\perp \]

for one side, with the analogous quotient on the other side. The exact convention depends on how \(C_X\) and \(C_Z\) are assigned, but the conceptual point is invariant: stabilizers are trivial representatives, logicals are nontrivial cosets.

The distance is the minimum weight of a nontrivial logical representative. This is why distance is not simply "the minimum distance of one classical code" unless the relative quotient issue has been handled.

Worked Example: The [[4,2,2]] CSS Code

Take four qubits and use the all-ones parity check on both sides:

\[ H_X=[1\;1\;1\;1], \qquad H_Z=[1\;1\;1\;1]. \]

The overlap is \(4\), so \(H_XH_Z^T=0\) over GF(2). The two stabilizer generators are \(XXXX\) and \(ZZZZ\).

There are \(4\) qubits and \(2\) independent stabilizers, so \(k=2\). A weight-\(1\) Pauli anticommutes with one stabilizer, so it is detected. Weight-\(2\) representatives such as \(XXII\) can be nontrivial logicals. Thus the distance is \(2\).

This example is tiny, but it makes the quotient picture concrete: multiplying by \(XXXX\) changes a representative without changing the logical operator.

Good Parameters And The LDPC Tension

A QLDPC family is good when:

  • check weights are bounded
  • qubit degrees are bounded
  • \(k=\Theta(n)\)
  • \(d=\Theta(n)\)

Bounded degree makes each check small. Linear distance demands that nontrivial logicals cannot be localized on small supports. Expansion is the usual mechanism that forces that delocalization.

This is the tension:

  • bounded degree makes the code physically plausible
  • expansion makes the code powerful
  • expansion also creates global routing demand

Why Linear Distance Pushes Toward Expansion

The distance proof shape is again contrapositive. If a small set of qubits has too few boundary checks, it can support a low-weight undetected or weakly detected pattern. Expansion rules out such hiding places.

Be precise: good parameters alone do not automatically prove the exact expansion hypothesis needed for every Conjecture 3 node. The course focuses on expander-style QLDPC families and on quantum Tanner codes because their construction exposes expansion explicitly.

Left-Right Cayley Complexes

Quantum Tanner codes start from a group and two generating sets, usually thought of as left and right directions. The resulting left-right Cayley complex contains square-like local structure.

The construction defines two diagonal graphs, often denoted

\[ G_0^\square,\qquad G_1^\square. \]

These diagonal graphs are the classical Tanner-code scaffolds used to assemble the CSS pair.

The point of the complex is not decorative. It gives enough algebraic structure for commutativity and enough graph expansion for distance.

Quantum Tanner Codes

At the level needed for this course, the construction is:

\[ C_0=T(G_0^\square,C_A^\perp), \qquad C_1=T(G_1^\square,C_B^\perp). \]

These two Tanner codes form the CSS pair. Leverrier and Zemor prove theorem-level good parameters under explicit hypotheses on the component codes. The local node quantum-tanner-expander-anchor.md records:

  • Theorem 17 gives \(k=\Theta(n)\) and \(d=\Theta(n)\) under component-code hypotheses
  • Theorem 18 shows those hypotheses are achievable with nonzero probability for random component-code choices

So quantum Tanner codes are not just an analogy. They are a concrete good QLDPC anchor family.

Spectral Expansion And The Anchor Gap

The diagonal graphs have a spectral expansion theorem. If the underlying Cayley graphs are Ramanujan, then

\[ \lambda(G_0^\square),\lambda(G_1^\square)\le 4\Delta. \]

That is strong, but it lives at the auxiliary diagonal-graph level. The lower-bound route wants an expansion or cut-rank statement tied to the stabilizer presentation measured by a syndrome-extraction circuit.

This is the anchor gap:

diagonal spectral expansion -> incidence expansion -> parity-Tanner expansion -> syndrome-depth demand.

The local research graph has made much of this bridge precise, but the lesson-level takeaway is that "the code uses expanders" is not yet the same as "the exact measured stabilizer presentation satisfies every lower-bound hypothesis."

Other QLDPC Families In Context

Use this only as orientation:

  • hypergraph product codes made QLDPC constructions broadly usable, but their distance is typically square-root scale in the basic form
  • fiber bundle codes improved the distance landscape
  • the 2021-2022 breakthrough line produced asymptotically good QLDPC families
  • quantum Tanner codes are the preferred anchor here because their expander scaffolding is explicit and locally represented in this repo

What This Does And Does Not Prove

This lesson explains why quantum Tanner codes are the right guest objects for the course. It does not prove a hardware lower bound by itself. Hardware lower bounds require syndrome-extraction and cut-capacity arguments.

It also does not claim every good QLDPC family has the same explicit Tanner expansion in every presentation.

Active Recall

  • Explain logical operators as quotient representatives.
  • Why does \([[4,2,2]]\) have distance \(2\)?
  • What four properties define an asymptotically good QLDPC family?
  • What is the role of the diagonal graphs in quantum Tanner codes?
  • State the anchor gap in your own words.

Next-Step Handoff

Next we translate code demand into circuit demand: stabilizer measurement circuits, hardware graphs, SWAP routing, congestion, dilation, and the difference between the static 2D theorem and the full CD conjecture.