Simple Algorithm
Quantum Computing · Rydberg State · 30 min

Beyond the Surface Code: qLDPC Codes

Higher rates with long-range connectivity.

A distance-dd surface code spends about 2d22d^2 physical qubits on a single logical qubit, and with local checks in 2D that inefficiency is unavoidable. Allow some long-range checks and the picture changes: quantum LDPC codes protect many logical qubits at once, and in 2021 codes with linear rate and linear distance were finally shown to exist.

What you’ll learn

  • Define quantum LDPC codes and state the Bravyi–Poulin–Terhal bound that limits 2D-local codes.
  • Construct hypergraph product codes, prove HXHZT=0H_XH_Z^T=0, and derive k=k1k2+k1Tk2Tk=k_1k_2+k_1^Tk_2^T with the Künneth formula.
  • Explain what "good" qLDPC codes are and how they were obtained.
  • Describe bivariate bicycle codes, the [[144,12,12]][[144,12,12]] gross code, and their decoding and connectivity requirements.

The price of locality

A quantum LDPC (qLDPC) code family is a family of stabilizer codes in which every check acts on at most ww qubits and every qubit lies in at most ww checks, with w=O(1)w=\order{1} as n→∞n\to\infty. Bounded weight keeps syndrome circuits shallow and stops errors from spreading. The surface code is qLDPC, but its rate k/n=1/d2k/n=1/d^2 vanishes as the distance grows.

So in 2D any code with d∝nd\propto\sqrt{n} has k=O(1)k=\order{1}, and protecting kk logical qubits at distance dd costs Ω(kd2)\Omega(kd^2) qubits: among local codes, the surface code is essentially optimal. Beating it requires checks that reach across the chip.

FamilyParametersCheck weightGeometry
Rotated surface code[[d2,1,d]][[d^2,1,d]]42D nearest-neighbor
Hypergraph product of good classical LDPC codes[[n,Θ(n),Θ(n)]][[n,\Theta(n),\Theta(\sqrt{n})]]O(1)\order{1}non-local
Good qLDPC codes (2021–22)[[n,Θ(n),Θ(n)]][[n,\Theta(n),\Theta(n)]]O(1)\order{1}non-local (expander graphs)
Bivariate bicycle "gross" code[[144,12,12]][[144,12,12]]6degree 6, two planar layers
Check your understanding

What does the Bravyi–Poulin–Terhal bound imply for a family of 2D-local codes with d∝nd\propto\sqrt{n}?

  1. kk can grow linearly with nn
  2. dd cannot exceed log⁡n\log n
  3. kk stays bounded by a constant
  4. Such codes cannot exist
Show the answer

C. kk stays bounded by a constant

kd2=O(n)kd^2=\order{n} with d2∝nd^2\propto n forces k=O(1)k=\order{1}. The surface code sits at this extreme: k=1k=1, d=nd=\sqrt{n}.

Hypergraph product codes

How do you build a CSS code, which needs HXHZT=0H_XH_Z^T=0, from classical codes that satisfy no orthogonality condition at all? Tillich and Zémor's answer is a product. Take parity-check matrices H1∈F2m1×n1H_1\in\mathbb{F}_2^{m_1\times n_1} and H2∈F2m2×n2H_2\in\mathbb{F}_2^{m_2\times n_2} of classical codes [ni,ki,di][n_i,k_i,d_i], and let kiTk_i^T, diTd_i^T be the dimension and distance of the transposed code ker⁡HiT\ker H_i^T (with diT=∞d_i^T=\infty if ker⁡HiT=0\ker H_i^T=0).

HX=( H1⊗In2 ∣ Im1⊗H2T ),HZ=( In1⊗H2 ∣ H1T⊗Im2 )H_X = \big(\,H_1\otimes I_{n_2}\ \big|\ I_{m_1}\otimes H_2^T\,\big),\qquad H_Z = \big(\,I_{n_1}\otimes H_2\ \big|\ H_1^T\otimes I_{m_2}\,\big)
Qubits are indexed by [n1]×[n2][n_1]\times[n_2] (left block) and [m1]×[m2][m_1]\times[m_2] (right block), so n=n1n2+m1m2n=n_1n_2+m_1m_2.
DerivationThe checks commute
  1. HXHZT=(H1⊗I)(I⊗H2T)+(I⊗H2T)(H1⊗I)H_XH_Z^T = (H_1\otimes I)(I\otimes H_2^T) + (I\otimes H_2^T)(H_1\otimes I)

    Multiply block by block: HZTH_Z^T has blocks In1⊗H2TI_{n_1}\otimes H_2^T (top) and H1⊗Im2H_1\otimes I_{m_2} (bottom).

  2. =H1⊗H2T+H1⊗H2T=0(mod2)= H_1\otimes H_2^T + H_1\otimes H_2^T = 0 \pmod 2

    Mixed-product rule (A⊗B)(C⊗D)=AC⊗BD(A\otimes B)(C\otimes D)=AC\otimes BD. The two terms are equal, so over F2\mathbb{F}_2 they cancel.

DerivationCounting logical qubits with the Künneth formula
  1. View a parity-check matrix as a two-term chain complex A: F2n1→H1F2m1\mathcal{A}:\ \mathbb{F}_2^{n_1}\xrightarrow{H_1}\mathbb{F}_2^{m_1}. Its homology is H1(A)=ker⁡H1H_1(\mathcal{A})=\ker H_1 (dimension k1k_1) and H0(A)=coker⁡H1H_0(\mathcal{A})=\operatorname{coker}H_1 (dimension m1−rank⁡H1=k1Tm_1-\operatorname{rank}H_1=k_1^T).

  2. Let B∗: F2m2→H2TF2n2\mathcal{B}^*:\ \mathbb{F}_2^{m_2}\xrightarrow{H_2^T}\mathbb{F}_2^{n_2} be the transposed complex of H2H_2, with H1(B∗)=ker⁡H2TH_1(\mathcal{B}^*)=\ker H_2^T (dimension k2Tk_2^T) and H0(B∗)=coker⁡H2TH_0(\mathcal{B}^*)=\operatorname{coker}H_2^T (dimension n2−rank⁡H2=k2n_2-\operatorname{rank}H_2=k_2).

  3. F2n1m2 → HZT  F2n1n2⊕F2m1m2 → HX  F2m1n2\mathbb{F}_2^{n_1 m_2}\ \xrightarrow{\ H_Z^T\ }\ \mathbb{F}_2^{n_1n_2}\oplus\mathbb{F}_2^{m_1m_2}\ \xrightarrow{\ H_X\ }\ \mathbb{F}_2^{m_1n_2}

    The tensor-product complex A⊗B∗\mathcal{A}\otimes\mathcal{B}^* is exactly the CSS code: ZZ-checks, qubits and XX-checks in degrees 2, 1 and 0. Logical qubits are its degree-1 homology, k=dim⁡ker⁡HX/im⁡HZTk=\dim\ker H_X/\operatorname{im}H_Z^T.

  4. k=dim⁡H1(A) dim⁡H0(B∗)+dim⁡H0(A) dim⁡H1(B∗)=k1k2+k1Tk2Tk = \dim H_1(\mathcal{A})\,\dim H_0(\mathcal{B}^*) + \dim H_0(\mathcal{A})\,\dim H_1(\mathcal{B}^*) = k_1k_2+k_1^Tk_2^T

    Over a field, the homology of a tensor product is the tensor product of homologies (Künneth formula). □\square

Feed in good classical LDPC codes (rate and distance both linear in nin_i, as random sparse or expander codes provide) and you get [[n,Θ(n),Θ(n)]][[n,\Theta(n),\Theta(\sqrt{n})]]: constant rate, but the distance is stuck at n\sqrt{n}, because the product has logical operators supported on a single row or column of the qubit grid.

Good codes and bivariate bicycle codes

For two decades it was open whether qLDPC codes could have both k=Θ(n)k=\Theta(n) and d=Θ(n)d=\Theta(n), like good classical LDPC codes. Around 2020–21 a burst of constructions (fiber bundle, lifted product and balanced product codes) broke the n\sqrt{n} distance barrier, and then:

Asymptotic goodness does not by itself make a practical code. The bivariate bicycle (BB) codes of Bravyi, Cross, Gambetta, Maslov, Rall and Yoder (2024) target small nn and realistic noise. Let SℓS_\ell be the ℓ×ℓ\ell\times\ell cyclic shift matrix and set x=Sℓ⊗Imx=S_\ell\otimes I_m, y=Iℓ⊗Smy=I_\ell\otimes S_m: commuting matrices with xℓ=ym=Ix^\ell=y^m=I. Choose A=A1+A2+A3A=A_1+A_2+A_3 and B=B1+B2+B3B=B_1+B_2+B_3, each term a power of xx or of yy, and define

HX=(A ∣ B),HZ=(BT ∣ AT),HXHZT=AB+BA=0H_X = (A\,|\,B),\qquad H_Z=(B^T\,|\,A^T),\qquad H_XH_Z^T = AB+BA = 0
AA and BB are polynomials in the commuting xx and yy, so AB=BAAB=BA and the sum vanishes mod 2. Every check has weight 3+3=63+3=6, every qubit lies in 6 checks, and n=2ℓmn=2\ell m.
Predict before you look

For comparison: how many physical qubits would 12 separate rotated surface-code patches of the same distance, d=12d=12, use at 2d2−12d^2-1 qubits each?

Show the answer

3444 qubits

12×(2⋅144−1)=12×287=344412\times(2\cdot144-1)=12\times287=3444, versus 288 for the gross code: about 12×12\times fewer at equal distance. (Bravyi et al. compare at equal logical error rate instead, and quote nearly 3000.)

The catch is connectivity. Each qubit talks to six others: four of these links can be laid out like a torus, but the other two reach across the lattice. The Tanner graph splits into two edge-disjoint planar layers, so a superconducting implementation needs long-range couplers in a second wiring layer, while neutral atoms (by moving atoms) and trapped ions (by shuttling) supply non-local interactions more naturally. Baspin and Krishna (2022) showed quantitatively that beating 2D-local code parameters requires many long-range interactions.

Decoding, logic and the frontier

Matching works only when each error flips at most two checks; qLDPC codes break that. Classical belief propagation (BP) also stumbles, because degeneracy creates many equally likely errors and short cycles confuse message passing. The workhorse is BP+OSD, belief propagation followed by ordered-statistics post-processing (Panteleev & Kalachev; Roffe et al.), which is accurate but costly, since OSD involves Gaussian elimination. Expander-based codes admit linear-time small-set-flip decoders with provable guarantees (Leverrier, Tillich & Zémor, 2015).

Computation is harder still: qLDPC codes rarely have useful transversal gates. Current proposals use code automorphisms, measurements of logical Paulis through auxiliary systems (generalizing lattice surgery; Cohen et al., 2022), and teleportation into surface-code or other ancilla blocks for non-Clifford gates. On the theory side, Gottesman (2014) showed that qLDPC codes of constant rate enable fault tolerance with constant space overhead.

Key takeaways

  • In 2D with local checks kd2=O(n)kd^2=\order{n} (Bravyi–Poulin–Terhal): the surface code's O(d2)\order{d^2} qubits per logical qubit are essentially forced by locality.
  • Hypergraph products turn any two classical codes into a CSS code with k=k1k2+k1Tk2Tk=k_1k_2+k_1^Tk_2^T (Künneth) and d=min⁡(d1,d2,d1T,d2T)d=\min(d_1,d_2,d_1^T,d_2^T); the surface code is the product of two repetition codes.
  • Good qLDPC codes with k,d=Θ(n)k,d=\Theta(n) exist (Panteleev–Kalachev 2021; quantum Tanner codes).
  • Bivariate bicycle codes such as [[144,12,12]][[144,12,12]] promise roughly an order of magnitude fewer qubits than the surface code, at the price of degree-6, partly long-range connectivity and harder decoding and logic.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

The [7,4,3][7,4,3] Hamming code has a full-rank 3×73\times7 parity-check matrix HH. What are the parameters of the hypergraph product of HH with itself?

  1. [[58,16,3]][[58,16,3]]
  2. [[49,16,3]][[49,16,3]]
  3. [[58,8,3]][[58,8,3]]
  4. [[58,16,9]][[58,16,9]]
Show the answer

A. [[58,16,3]][[58,16,3]]

n=7⋅7+3⋅3=58n=7\cdot7+3\cdot3=58. Full rank means kT=3−3=0k^T=3-3=0, so k=4⋅4+0=16k=4\cdot4+0=16, and d=min⁡(3,3,∞,∞)=3d=\min(3,3,\infty,\infty)=3.

Question 2

What does it mean for a qLDPC code family to be good?

  1. It has a threshold above 1%1\%
  2. It can be laid out in 2D with local checks
  3. k=Θ(n)k=\Theta(n) and d=Θ(n)d=\Theta(n), while check weights and qubit degrees stay bounded
  4. It has a transversal TT gate
Show the answer

C. k=Θ(n)k=\Theta(n) and d=Θ(n)d=\Theta(n), while check weights and qubit degrees stay bounded

"Good" is the coding-theory notion: constant rate and linear distance. Bravyi–Poulin–Terhal shows such codes cannot be 2D-local.

Question 3

Why do HX=(A∣B)H_X=(A|B) and HZ=(BT∣AT)H_Z=(B^T|A^T) define a valid CSS code for bivariate bicycle codes?

  1. Because AA and BB are symmetric matrices
  2. Because A=BA=B
  3. Because every check has even weight
  4. Because AA and BB are polynomials in the commuting shifts xx, yy, so HXHZT=AB+BA=2AB=0H_XH_Z^T=AB+BA=2AB=0 mod 2
Show the answer

D. Because AA and BB are polynomials in the commuting shifts xx, yy, so HXHZT=AB+BA=2AB=0H_XH_Z^T=AB+BA=2AB=0 mod 2

HXHZT=(A∣B)(BA)=AB+BAH_XH_Z^T=(A|B)\begin{pmatrix}B\\A\end{pmatrix}=AB+BA. Commuting AA and BB make the two terms equal, and they cancel over F2\mathbb{F}_2.

Question 4

What is the main hardware cost of the gross code compared with the surface code?

  1. It needs a physical error rate of about 10−510^{-5}
  2. Each qubit couples to six others, including long-range links that do not fit a single planar nearest-neighbor layout
  3. It needs no ancilla qubits, so readout must be much faster
  4. It requires qudits instead of qubits
Show the answer

B. Each qubit couples to six others, including long-range links that do not fit a single planar nearest-neighbor layout

The degree-6 Tanner graph has thickness 2: two planar layers, one of which contains long-range edges. Its threshold (about 0.7%0.7\%) is comparable to the surface code's.

Further reading

  • J.-P. Tillich & G. Zémor, "Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength", IEEE Trans. Inf. Theory (2014); arXiv preprint (2009).
  • S. Bravyi, D. Poulin & B. Terhal, "Tradeoffs for reliable quantum information storage in 2D systems", Phys. Rev. Lett. 104, 050503 (2010).
  • P. Panteleev & G. Kalachev, "Asymptotically good quantum and locally testable classical LDPC codes", Proc. STOC (2022); arXiv:2111.03654.
  • S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, P. Rall & T. J. Yoder, "High-threshold and low-overhead fault-tolerant quantum memory", Nature 627, 778 (2024).
  • N. P. Breuckmann & J. N. Eberhardt, "Quantum low-density parity-check codes", PRX Quantum 2, 040101 (2021).