Quantum LDPC Codes

A quantum low-density parity-check code is a stabilizer code with a discipline imposed on its checks: every stabilizer generator acts on only a bounded number of qubits, and every physical qubit is touched by only a bounded number of generators. Both bounds are constants — they do not grow as the code gets larger. That single restriction, borrowed wholesale from the classical LDPC codes that carry the world's data over noisy channels, turns out to be the pivot on which practical fault tolerance turns. A bounded-weight check can be measured with a shallow circuit and one ancilla; a bounded-degree qubit means a single fault cannot infect the whole device; a sparse parity-check matrix is exactly what belief-propagation decoders were built to chew through. The surface code is the qLDPC everyone already knows — weight-four checks on a planar grid — and it is the workhorse of today's hardware. But it is profligate: it stores only a handful of logical qubits and its distance grows merely as the square root of the qubit count, so protecting many logical qubits to large distance demands staggering overhead. The great question of the field, open for two decades, was whether one could keep the checks sparse yet store a constant fraction of the qubits as logical information while protecting them to a distance linear in the block length. In 2022 the answer arrived: yes. Asymptotically good qLDPC codes exist. The catch is geometric — the Bravyi–Poulin–Terhal bound proves that no such code can live in any fixed spatial dimension with local checks, so good codes are irreducibly non-local, and the race is now to build the long-range hardware that can host them.

Key takeaways

A quantum LDPC code is a stabilizer code whose every generator has weight w = O(1) and whose every qubit lies in c = O(1) generators, so its parity-check matrix is sparse.
The toric and surface codes are the prototype family, but their rate vanishes (k = O(1)) and their distance grows only as √n — enormous overhead for many protected qubits.
A CSS qLDPC code is a pair of sparse classical codes glued by the orthogonality H_X H_Zᵀ = 0; reading H_X and H_Zᵀ as boundary maps makes the code a chain complex, with logical operators as homology classes.
The hypergraph product turns two classical codes into a constant-rate quantum code, but its distance is capped at Θ(√N) — a barrier only broken in 2022.
Asymptotically good codes achieve k = Θ(n) and d = Θ(n) at once with O(1)-weight checks (Panteleev–Kalachev; Leverrier–Zémor), settling a two-decade question.
The price is locality: the Bravyi–Poulin–Terhal bound k·d^{2/(D-1)} ≤ cn forbids good codes in any fixed dimension, so they demand long-range connectivity.
Key idea: a qLDPC code is a stabilizer code with bounded-weight, bounded-degree checks; encoding the orthogonality H_X H_Zᵀ = 0 as a chain complex lets one build families — by hypergraph, balanced, and lifted products of classical codes — that keep the checks sparse while pushing the rate to Θ(n) and the distance to Θ(n).

The core insight

A quantum LDPC code is a stabilizer code with bounded-weight, bounded-degree checks; encoding the CSS orthogonality H_X H_Zᵀ = 0 as a chain complex lets one build families — via hypergraph, balanced, and lifted products of classical codes — that keep the checks sparse while pushing the rate to Θ(n) and the distance to Θ(n).

Where this lives today

Quantum LDPC codes have crossed from asymptotic theorem to hardware roadmap in the space of a few years. The most visible milestone is IBM's 2024 Nature result on bivariate-bicycle codes, whose flagship gross code ⟦144, 12, 12⟧ stores twelve logical qubits at distance twelve on roughly the qubit budget the surface code would spend on one — an order-of-magnitude overhead reduction that has reshaped IBM's published fault-tolerance timeline. The codes are not free: their weight-six checks demand a few long-range couplers beyond a nearest-neighbour grid, precisely the non-locality the BPT bound insists on, and IBM's proposal folds this into a "two-layer" superconducting layout. Neutral-atom platforms attack the connectivity problem head-on: the 2023 Harvard–MIT–QuEra demonstration of dozens of logical qubits on a reconfigurable array physically shuttles atoms to bring distant qubits into contact, the natural substrate for codes whose Tanner graph reaches across the device. On the software side, decoding is the live frontier — belief propagation alone stalls on the many short cycles of quantum Tanner graphs, so practical decoders bolt on ordered-statistics post-processing (BP+OSD) or use generalized and neural-network decoders, all racing to keep pace with the syndrome stream in real time. Two research directions run hottest: constructing explicit codes with small check weights and genuinely good finite-length parameters (not merely good asymptotics), and codes with the "soundness" that permits single-shot decoding, where one noisy round of syndrome measurement suffices and the Θ(d) repeated-measurement overhead of the surface code disappears. The open question that hangs over all of it is engineering: whether long-range connectivity can be built cheaply enough that the asymptotic promise — a one-to-two order-of-magnitude cut in the qubits needed for fault-tolerant computing — survives contact with a real device.

The physical picture

Draw the code as a bipartite graph. Put one variable node for each physical qubit and one check node for each stabilizer generator, and connect a qubit to a check whenever that generator acts nontrivially on that qubit. This is the Tanner graph, and "low density" is a statement about it: every check node has bounded degree (a generator touches at most w qubits) and every variable node has bounded degree (a qubit sits in at most c generators). Nothing in this graph is allowed to grow as the code scales. The payoff is immediate and physical — a check you can measure by entangling one ancilla with only w data qubits, in a circuit of depth of order w, and a qubit whose local faults can propagate to only a handful of neighbours. The first figure is that graph, with the numbers of the toric code attached so the abstraction has a face.

Figure

The Tanner graph of an LDPC code: qubits are variable nodes and stabilizer generators are check nodes, joined when the generator acts on the qubit. Low density means bounded check weight w and bounded qubit degree c — here w = 4 and c = 3, both O(1) — exactly the sparsity of the toric code ⟦2L², 2, L⟧ with w = 4, c = 4

Now the tension the whole subject is organized around. The surface code is the friendliest qLDPC code imaginable: weight-four checks laid on a two-dimensional grid, every qubit touched by four checks, nearest-neighbour everything. But it pays Θ(d²) physical qubits to protect one logical qubit to distance d, so its rate k/n crashes to zero and its distance climbs only as √n. The 2022 breakthrough says that if you are willing to abandon the grid — to allow checks that reach across the device while still touching only O(1) qubits each — you can store a constant fraction of the qubits as logical information and protect all of them to distance Θ(n) simultaneously. The second figure lays the three regimes on one map and marks the corner that only good codes reach.

Figure

The rate–distance landscape of qLDPC families. Plotting code rate k/n against the distance exponent α in d = Θ(nᵅ): the surface code sits at zero rate and α = 1/2, the hypergraph product lifts the rate to a constant but is still stuck at α = 1/2, and only asymptotically good codes reach the top corner α = 1 at constant rate — the real ⟦144, 12, 12⟧ gross code is a finite realization near it. The Bravyi–Poulin–Terhal bound forbids that corner for any geometrically local code

Why does distance behave so differently from rate? Because in a CSS code the logical operators are cycles that are not boundaries — closed strings of Pauli operators that commute with every check yet cannot be built out of checks. The distance is the length of the shortest such string. In a low-dimensional geometry there simply are not enough independent long cycles to go around: pack in many logical qubits and their non-contractible strings are forced to be short, so rate and distance trade against each other. Breaking the trade-off means engineering a check geometry with the connectivity of an expander graph, where short cuts are scarce and every logical string is forced to be long — and expanders are inherently non-local. That is the whole story in one sentence: good codes are expander codes, and expanders do not fit in a box.

The core equations

A qLDPC code is first of all a stabilizer code, and the low-density property is a constraint on how its generators are written. The two lines below fix the object and the adjective at once.

\mathcal S=\langle g_1,\dots,g_{n-k}\rangle\subset\mathcal P_n,\quad -I\notin\mathcal S;\qquad \max_i|\mathrm{supp}(g_i)|\le w=O(1),\ \ \max_j\deg(q_j)\le c=O(1) \qquad (1)

where: $\mathcal S$ — the abelian stabilizer group; the codespace is its $+1$ eigenspace and encodes $k$ logical qubits; $g_i$ — independent generators drawn from the $n$ -qubit Pauli group $\mathcal P_n$ ; $|\mathrm{supp}(g_i)|$ — the weight of a generator, the number of qubits it touches; $\deg(q_j)$ — the number of generators acting on qubit $j$ ; $w,c$ — the row and column weights of the Tanner graph, held constant as $n\to\infty$ . Reading: the first clause is any stabilizer code; the second — the two bounded weights — is the entire content of "LDPC". Almost every useful qLDPC code is a CSS code, built from two sparse binary matrices whose one compatibility condition guarantees the stabilizers commute. This is the equation the rest of the field is written in.

H_X H_Z^{\mathsf T}=0\pmod 2\quad\Longleftrightarrow\quad \partial_1\partial_2=0,\qquad \partial_2=H_X^{\mathsf T},\ \ \partial_1=H_Z \qquad (2)

where: $H_X$ — the $X$ -type parity-check matrix, its rows the supports of the $X$ -stabilizers; $H_Z$ — the $Z$ -type matrix; the product $H_X H_Z^{\mathsf T}=0$ over $\mathbb F_2$ forces every $X$ -generator to overlap every $Z$ -generator in an even number of qubits; $\partial_1,\partial_2$ — the boundary maps of a length-three chain complex $C_2\to C_1\to C_0$ , with qubits living on the middle space $C_1$ . Reading: the algebraic condition "stabilizers commute" is literally the topological condition "boundary of a boundary is zero", which is why homology governs the code. The number of logical qubits is not counted by hand; it is the dimension of the first homology group of that complex. This is the equation that tells you how much a code stores.

k=n-\mathrm{rank}(H_X)-\mathrm{rank}(H_Z)=\dim\big(\ker H_X/\,\mathrm{im}\,H_Z^{\mathsf T}\big)=\dim H_1 \qquad (3)

where: $\ker H_X$ — the cycles, operators commuting with all $X$ -checks; $\mathrm{im}\,H_Z^{\mathsf T}$ — the boundaries, the $Z$ -stabilizers themselves; $H_1=\ker/\mathrm{im}$ — the first homology group; $k$ — its dimension over $\mathbb F_2$ . Reading: logical degrees of freedom are cycles that are not boundaries; the $X$ - and $Z$ -logical spaces both have dimension $k$ , so one homology dimension already counts them — there is no factor of two. The distance is the same idea sharpened to a length: the weight of the lightest logical operator, i.e. the shortest nontrivial cycle. This is the equation that tells you how well a code protects.

d=\min\big\{\,|v|:\ v\in(\ker H_X\setminus\mathrm{im}\,H_Z^{\mathsf T})\ \cup\ (\ker H_Z\setminus\mathrm{im}\,H_X^{\mathsf T})\,\big\} \qquad (4)

where: $|v|$ — the Hamming weight of the binary support vector $v$ ; $\setminus\,\mathrm{im}$ — the demand that $v$ be a genuine logical operator, a cycle that is not a boundary. Reading: any error lighter than $d$ is either detectable or harmless; the code fails only when a fault chain closes into a nontrivial cycle of weight at least $d$ . The hypergraph product is the workhorse construction: feed in two classical parity-check matrices and out comes a CSS qLDPC code whose parameters are fixed by theirs. This is the equation that builds constant-rate families.

[[N,K,D]]=[[\,n_1n_2+m_1m_2,\ \ k_1k_2+k_1^{\mathsf T}k_2^{\mathsf T},\ \ \min(d_1,d_2,d_1^{\mathsf T},d_2^{\mathsf T})\,]] \qquad (5)

where: $n_i,m_i,k_i,d_i$ — the block length, check count, dimension, and distance of the classical code with parity-check matrix $H_i$ (an $m_i\times n_i$ matrix); $k_i^{\mathsf T},d_i^{\mathsf T}$ — the dimension and distance of the transpose code $\ker H_i^{\mathsf T}$ . Reading: if the $H_i$ are sparse the product's checks stay bounded, and if the classical rates are constant so is the quantum rate — but the distance can never beat the smaller input distance, which caps $D$ at $\Theta(\sqrt N)$ . The Bravyi–Poulin–Terhal bound is the no-go theorem that shapes the whole enterprise: locality in a fixed number of dimensions caps how much a code can store and protect at once. This is the equation that forces good codes to be non-local.

k\,d^{2/(D-1)}\ \le\ c\,n \qquad (6)

where: $D$ — the number of Euclidean spatial dimensions in which the checks act locally (within bounded-radius balls); $c$ — a constant fixed by the dimension and local geometry; $n,k,d$ — the usual code parameters. Reading: in $D=2$ this reads $k\,d^2\le cn$ , saturated by the surface code; substituting the good-code target $k=d=\Theta(n)$ gives $\Theta(n^{1+2/(D-1)})\gg n$ for every fixed $D$ , an outright contradiction — good codes cannot be geometrically local. Finally, the goal itself: the defining parameters of an asymptotically good qLDPC code, proven to exist in 2022.

k=\Theta(n),\qquad d=\Theta(n),\qquad w=O(1) \qquad (7)

where: $\Theta(n)$ — linear scaling, so a constant fraction of the qubits is logical and the distance grows in proportion to the block length; $w$ — the bounded check weight that keeps the LDPC property intact. Reading: all three at once is the achievement; any two were easy (the surface code has two of them; a dense random code has the other pair), but constant rate, linear distance, and bounded weight together was the twenty-year prize.

Derivation AWhy the CSS orthogonality condition makes a chain complex

The goal is to show, edge by edge, that the single matrix equation H_X H_Zᵀ = 0 is exactly equivalent to the physical requirement that all the code's X-type and Z-type stabilizers commute, and then to recognize that this equation is nothing but the defining relation of a chain complex, ∂₁∂₂ = 0. This is the bridge that lets every tool of homology — cycles, boundaries, homology groups, the whole apparatus that classifies "holes" in a space — be imported wholesale to classify the logical operators and the distance of a quantum code. We work over the binary field 𝔽₂, where a stabilizer generator is specified by the set of qubits it acts on.

Step 1. Fix the pointwise algebra. On a single qubit a the Pauli operators anticommute, XₐZₐ = −ZₐXₐ, while operators on distinct qubits commute. Why: every sign that can appear when two Pauli products are exchanged must come from a qubit where one carries an X and the other a Z.

Step 2. Write the two generators from rows of the matrices, gᵢˣ = ∏ₐ Xₐ over the qubits with (H_X)ᵢₐ = 1, and gⱼᶻ = ∏_b Z_b over the qubits with (H_Z)ⱼb = 1. Exchanging them picks up one factor of −1 for each qubit in both supports, so gᵢˣ gⱼᶻ = (−1)^{Σₐ (H_X)ᵢₐ (H_Z)ⱼₐ} gⱼᶻ gᵢˣ. Why: the exponent is a mod-2 dot product of an X-row with a Z-row — precisely the (i,j) entry of the matrix product H_X H_Zᵀ.

Step 3. Demand commutation for every pair of generators. The requirement (H_X H_Zᵀ)ᵢⱼ = 0 (mod 2) for all i, j is the single matrix statement H_X H_Zᵀ = 0 over 𝔽₂. Why: an abelian stabilizer group is not optional — non-commuting "generators" have no common +1 eigenspace, so this equation is the price of admission for any CSS code.

Step 4. Read it as topology. Set the boundary maps ∂₂ = H_Xᵀ and ∂₁ = H_Z, so a length-three complex C₂ → C₁ → C₀ has qubits on C₁. Then ∂₁∂₂ = H_Z H_Xᵀ = (H_X H_Zᵀ)ᵀ = 0, the chain-complex axiom "the boundary of a boundary is zero". Why: with this identification the Z-logical operators are ker H_X modulo the boundaries im H_Zᵀ — the first homology H₁ — and the code distance is the shortest nontrivial cycle, so the entire code is a physical instance of a homology group. *Verified: H_X H_Zᵀ = 0 ⇔ all X- and Z-stabilizers commute (even overlap), and ∂₁∂₂ = 0 with ∂₂ = H_Xᵀ, ∂₁ = H_Z; k = dim H₁ gives k = 2 for the toric code, matching Nielsen & Chuang Ch. 10 and Wilde Ch. 10.*

Go deeper · Derivation B · 2 minThe hypergraph product: a sparse quantum code from two classical ones

Derivation BThe hypergraph product: a sparse quantum code from two classical ones

The goal is to build a CSS qLDPC code out of any two classical codes and to read off why the construction delivers constant rate with bounded-weight checks — yet cannot, by itself, break the √N distance barrier. The mechanism is a tensor product of chain complexes: each classical code is a two-term complex 𝔽₂^{mᵢ} ← 𝔽₂^{nᵢ}, and their tensor product is a three-term complex whose middle space carries the qubits, automatically satisfying the CSS condition. This is the Tillich–Zémor construction, the first to give constant-rate quantum LDPC codes and the template every later product generalizes.

Step 1. Tensor the two complexes. From H₁ (an m₁×n₁ matrix) and H₂ (an m₂×n₂ matrix) form the boundary maps ∂₂ = (H₁⊗I, I⊗H₂ᵀ)ᵀ and ∂₁ = (I⊗H₂, H₁ᵀ⊗I). A direct computation gives ∂₁∂₂ = H₁⊗H₂ − H₁⊗H₂ = 0 over 𝔽₂. Why: the CSS orthogonality H_X H_Zᵀ = 0 is inherited for free from the tensor structure, so any two classical matrices — good or bad — produce a valid quantum code.

Step 2. Read off the size. Qubits live on the two middle tensor factors, N = n₁n₂ + m₁m₂, and the checks H_X = ∂₁, H_Z = ∂₂ᵀ are sparse whenever H₁ and H₂ are, since a tensor product of sparse matrices with an identity stays sparse. Why: the LDPC property is preserved automatically — the quantum check weight is roughly the sum of the two classical row weights, still O(1).

Step 3. Get constant rate. The logical count works out to K = k₁k₂ + k₁ᵀk₂ᵀ; taking two classical codes with kᵢ/nᵢ = Θ(1) and mᵢ = Θ(nᵢ) gives K/N = Θ(1). Why: choosing good classical codes hands you a quantum code storing a constant fraction of its qubits — the property the surface code fatally lacks.

Step 4. Hit the ceiling. The distance is D = min(d₁, d₂, d₁ᵀ, d₂ᵀ). With n₁ ∼ n₂ ∼ m the block length is N ∼ m² while the distance is at best ∼ m, so D = Θ(√N). Why: the product cannot manufacture cycles longer than the shortest input cycle, so √N is a hard wall — beating it required the expander-based balanced and lifted products that entangle the two factors far more tightly. *Verified: ∂₁∂₂ = 0 by cancellation; N = n₁n₂ + m₁m₂, K = k₁k₂ + k₁ᵀk₂ᵀ, D = min(dᵢ, dᵢᵀ); the ring repetition code (n = m = L, k = kᵀ = 1, d = dᵀ = L) reproduces the toric code ⟦2L², 2, L⟧, matching Tillich–Zémor (2009).*

Go deeper · Derivation C · 2 minWhy locality forbids good codes — the Bravyi–Poulin–Terhal bound

Derivation CWhy locality forbids good codes — the Bravyi–Poulin–Terhal bound

The goal is to see why a qLDPC code whose checks all act within bounded-radius balls of D-dimensional space must obey k·d^{2/(D-1)} ≤ cn, and therefore why the good-code target k = d = Θ(n) is flatly impossible under geometric locality. The argument rests on a "cleaning lemma": in a locally checked code, a logical operator can always be pushed off any region of space that is itself too small to support a logical operator, so logical operators must be geometrically spread — and there is only so much room. This is the theorem that turns the search for good codes into a search for non-local hardware.

Step 1. Localize the checks. Suppose every stabilizer generator acts only on qubits lying within a ball of bounded radius in ℝ^D, with bounded qubit density. Then a region R of linear size ℓ contains Θ(ℓ^D) qubits and its checks couple it to the outside only through a surface of Θ(ℓ^{D-1}) qubits. Why: locality means information about a region leaks out only through its boundary, a surface one dimension smaller than the bulk.

Step 2. Apply the cleaning lemma. If a region R supports no nontrivial logical operator, any logical operator can be deformed (multiplied by stabilizers) until its support avoids R entirely. Partitioning space into slabs and cleaning logicals off them bounds how thin a logical operator's support can be. Why: a logical operator cannot hide in a small patch, so it must stretch across the device, and its minimum weight is tied to the geometry it is forced to cover.

Step 3. Count. Balancing the number of independent logical operators k against the surface area available to keep their supports disjoint yields k·d^{2/(D-1)} = O(n). In D = 2 this is k·d² = O(n); in D = 3, k·d = O(n). Why: the surface code with k = O(1), d = Θ(√n) saturates the D = 2 form exactly, confirming it is optimal among 2D-local codes — you cannot do better in the plane.

Step 4. Rule out good codes. Substitute k = Θ(n) and d = Θ(n): the left side becomes Θ(n^{1+2/(D-1)}), which exceeds O(n) for every fixed D. Why: no finite-dimensional local layout can host a good qLDPC code — the connectivity must reach across the machine, which is exactly why atom-shuttling and photonic-link architectures are the hardware of interest. *Verified: k·d^{2/(D-1)} ≤ cn saturated by the surface code (k d² = n at D = 2); good codes give Θ(n^{1+2/(D-1)}) ≫ n for all fixed D, matching Bravyi–Poulin–Terhal, PRL 104, 050503 (2010).*

Limiting cases

The qLDPC family is best understood by where its members land in the rate–distance–locality space, and by what the bounds force:

Case	Result	Meaning
Surface / toric code	⟦n, O(1), Θ(√n)⟧, w = 4	Geometrically 2D-local, weight-4 checks; rate vanishes, distance sub-linear. Saturates the BPT bound at D = 2: k d² = O(n) with k = O(1).
Hypergraph product	⟦n, Θ(n), Θ(√n)⟧, w = O(1)	First constant-rate qLDPC family with bounded checks; distance still only √n. Built from the product of two classical codes (Tillich–Zémor).
Good qLDPC codes	⟦n, Θ(n), Θ(n)⟧, w = O(1)	Constant rate and linear distance together with bounded-weight checks; necessarily non-local (Panteleev–Kalachev; Leverrier–Zémor, 2022).
BPT bound in D dimensions	k·d^{2/(D-1)} ≤ cn	For local checks in D Euclidean dimensions; forces a rate–distance trade-off, so good codes exist only with long-range connectivity.
Single generator, w → n	dense check	A weight-Θ(n) check needs a depth-Θ(n) extraction circuit and lets one fault corrupt Θ(n) qubits — no threshold. Sparsity is what makes fault tolerance possible at all.

Common trapA sparse parity-check matrix already gives you a good code

It does not — and this is the single most common conflation in the subject. Low check weight is necessary for a code to be useful (it keeps syndrome extraction shallow and fault propagation bounded) but it is nowhere near sufficient. A perfectly sparse stabilizer matrix can define a code with distance as small as 2, offering essentially no protection; sparsity constrains the cost of the checks, not the quality of the code. Two further traps ride along with this one. First, "good" parameters (k, d = Θ(n)) and "geometrically local" are not merely different — they are mutually exclusive, by the BPT bound, so a code cannot be both a good code and a 2D-local one. The surface code (local, √n distance, vanishing rate) and the 2022 good codes (non-local, linear distance, constant rate) sit at opposite ends of the family and should never be pictured as the same kind of object with different numbers. Second, "distance d" is a worst-case guarantee about the lightest logical error, not a promise about typical noise — the operational protection a code delivers under real noise is set by its decoder and threshold, and a large-distance code with a weak decoder can underperform a smaller one with a strong decoder. Sparse, good, local, and decodable are four separate properties; assume none of them from the others.

Worked examples

1 · The hypergraph product of a repetition code rebuilds the toric code (fully worked)

Take the classical ring repetition code on L bits: its parity-check matrix H is the L×L circulant with rows xᵢ + x_{i+1} (indices mod L). Form the hypergraph product of this code with itself and compute the full quantum code parameters ⟦N, K, D⟧ for L = 4. Verify that you recover the toric code.

Step 1. Characterize the classical code. The circulant H has L rows and L columns; its kernel is the set of vectors constant around the ring, {all-0, all-1}, so k₁ = 1, and the lightest nonzero codeword is the all-ones vector of weight L, so d₁ = L. The transpose Hᵀ is the same kind of circulant, so the transpose code has k₁ᵀ = 1 and d₁ᵀ = L. Thus n₁ = m₁ = L, k₁ = k₁ᵀ = 1, d₁ = d₁ᵀ = L.

Step 2. Apply the hypergraph-product size formula (equation 5). The qubit count is N = n₁n₂ + m₁m₂ = L·L + L·L = 2L². For L = 4 this is N = 2·16 = 32 qubits.

Step 3. Count logical qubits. K = k₁k₂ + k₁ᵀk₂ᵀ = 1·1 + 1·1 = 2, independent of L — exactly the two non-contractible cycles of the torus.

Step 4. Read off the distance and assemble. D = min(d₁, d₂, d₁ᵀ, d₂ᵀ) = min(L, L, L, L) = L = 4. The product is therefore ⟦2L², 2, L⟧ = ⟦32, 2, 4⟧, precisely the toric code on a 4×4 lattice — its 32 edge-qubits, 2 logical qubits, and distance 4. The rate is k/N = 2/32 = 0.0625, and it corrects any error of weight up to t = ⌊(d−1)/2⌋ = ⌊3/2⌋ = 1. The hypergraph product of the ring repetition code with itself is the toric code ⟦2L², 2, L⟧; the abstract machinery reproduces the canonical topological code exactly.

2 · Why the ⟦144, 12, 12⟧ gross code beats the surface code — and must be non-local

IBM's bivariate-bicycle "gross code" has parameters ⟦144, 12, 12⟧ and weight-6 checks. Compare its qubit budget to surface-code patches storing the same 12 logical qubits at the same distance 12, and use the BPT bound to argue the gross code cannot be strictly 2D-local.

Step 1. The gross code's data cost. It stores k = 12 logical qubits at distance d = 12 on n = 144 data qubits, a rate of 12/144 = 1/12 ≈ 0.083. Syndrome extraction adds a comparable number of ancillas, so the full memory is on the order of ≈ 288 physical qubits for 12 distance-12 logical qubits.

Step 2. The surface-code cost for the same job. A single surface-code patch at distance d needs about 2d² physical qubits; at d = 12 that is 2·144 = 288 qubits per logical qubit. Storing 12 of them independently costs roughly 12·288 = ≈ 3456 qubits, before any routing overhead. The gross code delivers the same protection at close to one order of magnitude fewer qubits — the promise of constant rate made concrete.

Step 3. Check the BPT constraint. Plug the gross code into the D = 2 bound k·d² ≤ c·n: the left side is 12·12² = 12·144 = 1728, while c·n with c ∼ 1 is of order 144. Since 1728 ≫ 144, the code cannot satisfy the 2D-local bound with a small constant — it violates strict planar locality by more than an order of magnitude.

Step 4. Interpret. The gross code lives on a torus but its weight-6 checks include couplings that reach beyond nearest neighbours; that modest non-locality is exactly what lets it evade the k·d² ≤ cn ceiling that pins the surface code. The overhead saving and the non-locality are two sides of one coin: you cannot get constant-rate protection in the plane, so any low-overhead qLDPC memory must buy long-range connectivity to pay for it.

Physics of the portrait

Quantum LDPC codes were not the work of a lone genius but of a lineage — classical coding theory reaching into quantum information, then bending back to answer a question the physicists had left open for twenty years. One mathematician sits at two of its decisive turns.

Origins · 2 minGilles Zémor and how this was discovered

Gilles Zémor

coding theorist, Université de Bordeaux · hypergraph-product and good quantum LDPC codes

Gilles Zémor is a French mathematician and coding theorist whose career traces the very arc of this subject. Trained in the classical theory of error-correcting codes — where his name attaches to expander-based constructions and to the Barg–Zémor family of asymptotically good codes decodable in linear time — he brought the machinery of sparse graphs and expansion to the quantum setting at the moment it was most needed. With Jean-Pierre Tillich he introduced the hypergraph product in 2009, the construction that first proved constant-rate quantum LDPC codes with growing distance could exist at all, and that remains the template from which nearly every later family is generalized; it is the direct ancestor of the balanced products, fibre-bundle codes, and lifted products that followed. The hypergraph product had one stubborn limitation — its distance was stuck at the square root of the block length — and closing that gap became the central open problem of quantum coding for over a decade. In 2022 Zémor helped close it: with Anthony Leverrier he constructed quantum Tanner codes, one of the handful of essentially simultaneous constructions (alongside Panteleev and Kalachev, and Dinur, Hsieh, Lin, and Vidick) that finally produced asymptotically good quantum LDPC codes — constant rate, linear distance, and bounded-weight checks, all at once. What makes the story unusually clean is that the same person, wielding the same idea of graph expansion, appears at both the founding and the resolution: the hypergraph product opened the door, and quantum Tanner codes walked through it. Zémor works at the Institut de Mathématiques de Bordeaux, and his thread through the field is a reminder that the deepest advances in quantum error correction have come from taking classical coding theory completely seriously.

History

1962

— Gallager introduces classical low-density parity-check codes in his doctoral work

1997

— Kitaev's toric code gives the first quantum LDPC code, local and topological

2009

— Tillich and Zémor's hypergraph product yields the first constant-rate quantum LDPC codes

2022

— Panteleev–Kalachev and Leverrier–Zémor construct asymptotically good quantum LDPC codes

2024

— IBM's bivariate-bicycle gross code ⟦144, 12, 12⟧ demonstrates low-overhead memory

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniv. ed. (2010), Ch. 10 · Preskill, Lecture Notes for Physics 219, Ch. 7 (quantum error correction) and Ch. 9 · Watrous, The Theory of Quantum Information (2018) · Kitaev, Shen & Vyalyi, Classical and Quantum Computation (2002), Ch. 15 · Wilde, Quantum Information Theory, 2nd ed. (2017), Ch. 10 · Bravyi, Poulin & Terhal, Tradeoffs for reliable quantum information storage in 2D systems, Phys. Rev. Lett. 104, 050503 (2010) · Tillich & Zémor, Quantum LDPC codes with positive rate and minimum distance proportional to √n, IEEE Trans. Inf. Theory 60, 1193 (2014) · Panteleev & Kalachev, Asymptotically good quantum and locally testable classical LDPC codes, STOC 2022 · Leverrier & Zémor, Quantum Tanner codes, FOCS 2022 · Bravyi et al., High-threshold and low-overhead fault-tolerant quantum memory, Nature 627, 778 (2024).

Provenance. A verifier should confirm: (i) H_X H_Zᵀ = 0 ⇔ all X- and Z-stabilizers commute, equivalent to ∂₁∂₂ = 0 with ∂₂ = H_Xᵀ, ∂₁ = H_Z (Derivation 1; Nielsen & Chuang Ch. 10, Wilde Ch. 10); (ii) k = n − rank(H_X) − rank(H_Z) = dim H₁, giving k = 2 for the toric code — a single homology dimension, not a sum (Eq. 3); (iii) the hypergraph-product parameters N = n₁n₂ + m₁m₂, K = k₁k₂ + k₁ᵀk₂ᵀ, D = min(dᵢ, dᵢᵀ), with the ring repetition code reproducing ⟦2L², 2, L⟧ (Derivation 2, Worked Example 1; Tillich–Zémor 2014); (iv) the BPT bound k·d^{2/(D-1)} ≤ cn, saturated by the surface code and violated by k = d = Θ(n) (Derivation 3; Bravyi–Poulin–Terhal 2010); (v) existence of good qLDPC codes with k, d = Θ(n) and O(1) weight (Panteleev–Kalachev, Leverrier–Zémor, 2022); (vi) the gross code ⟦144, 12, 12⟧ overhead numbers (Worked Example 2; Bravyi et al. 2024). All parameters quoted are standard published or textbook values.

Prerequisites. Stabilizer Formalism · CSS Codes · Code Distance and Logical Operators · Syndrome Measurement and Decoding · Pauli Group and Clifford Group. Leads to. Quantum Hamming and Singleton Bounds · Syndrome Measurement and Decoding.

Ask the tutor: Want to walk through building an explicit hypergraph-product code from two small classical codes, or see exactly how the BPT cleaning argument forces a good code off the two-dimensional grid?

What does "low density" actually buy you, physically?

Three things, all downstream of one fact: a bounded-weight check is cheap and safe to measure. First, extraction circuits stay shallow — a weight-w stabilizer is read by entangling one ancilla with only w data qubits, a depth of order w, independent of code size. Second, fault propagation stays contained — a single ancilla fault during that measurement can spread to at most w data qubits, so no lone error can corrupt a macroscopic chunk of the device; this bounded spread is exactly what keeps the fault-tolerance threshold positive. Third, decoding stays tractable — a sparse Tanner graph is what belief propagation was invented to handle, so syndromes can be turned into corrections in near-linear time. Take any of these away by letting the check weight grow, and fault tolerance collapses: unbounded weight means deep circuits, one fault infecting Θ(n) qubits, and no threshold at all.

Is the surface code a quantum LDPC code?

Yes — it is the most famous one. Its stabilizers are weight-four star and plaquette operators, and each qubit sits in exactly four checks, so both the row weight and column weight of its Tanner graph are the constant 4: textbook LDPC. What the surface code is not is a good qLDPC code. It stores only O(1) logical qubits per patch and its distance grows merely as √n, so its rate collapses to zero as it scales and its distance is sub-linear. It is the extreme "local, low-rate" corner of the qLDPC family, and it earns its place in hardware not by efficiency but by its beautiful two-dimensional, nearest-neighbour layout. The new good codes trade that geometric friendliness for constant rate and linear distance. So every surface code is a qLDPC code, but almost no qLDPC code of interest is a surface code.

What does "asymptotically good" mean, and why was it so hard?

"Good" is a precise coding-theory term: a family of codes is good if, as the block length n grows, both the rate k/n and the relative distance d/n stay bounded away from zero — constant rate and linear distance together. For quantum LDPC codes you demand a third property, bounded check weight, so all three must hold at once. The difficulty was that every known construction sacrificed one. The surface code had bounded weight and locality but vanishing rate. The hypergraph product recovered constant rate but its distance stalled at √n. Random dense codes had good rate and distance but wildly unbounded weight. For roughly twenty years no one could get constant rate, linear distance, and O(1) weight simultaneously, and many suspected it was impossible. The 2022 constructions — built on expander graphs and their high-dimensional analogues — finally proved it possible, one of the landmark results of the field.

Why must a good code necessarily be non-local?

Because of the Bravyi–Poulin–Terhal bound, k·d^{2/(D-1)} ≤ cn, which holds for any code whose checks act within bounded regions of D-dimensional space. It comes from a "cleaning" argument: in a locally checked code a logical operator can always be pushed off any small region, so logical operators must spread across the device, and geometry limits how many can coexist. Substitute the good-code target k = d = Θ(n) and the left side blows up to Θ(n^{1+2/(D-1)}), which dwarfs the allowed O(n) for every fixed dimension D. There is no way to satisfy the inequality with local checks, so a good code's Tanner graph must contain edges that reach arbitrarily far across the machine. This is not a technicality — it is why the hardware effort has pivoted toward atom-shuttling arrays and photonically linked modules that can realize long-range connectivity.

How do you actually decode a quantum LDPC code?

The starting point is belief propagation, the message-passing algorithm that makes classical LDPC codes decodable in near-linear time on their sparse Tanner graphs. Applied naively to quantum codes it stumbles, because CSS Tanner graphs are riddled with short cycles and degenerate errors (many distinct errors with the same syndrome), which trap the message passing. Practical decoders repair this in two main ways. The most common is BP+OSD: run belief propagation to get soft information, then apply ordered-statistics decoding as a post-processing step that solves a small linear system to pick a consistent correction. Alternatives include generalized belief propagation, which reasons about clusters of variables, and machine-learned decoders trained on the code's noise. For special structured codes — the surface code above all — dedicated matching decoders like minimum-weight perfect matching are faster still. The overarching challenge is speed: the decoder must keep up with a syndrome stream arriving every measurement cycle, which is an active engineering race.

Are quantum LDPC codes practical yet, or still theoretical?

They have crossed into engineering. The 2022 good-code proofs were asymptotic, but the concrete finite-length codes that matter for near-term hardware — bivariate-bicycle codes, lifted-product instances — arrived alongside them, and IBM's 2024 gross code ⟦144, 12, 12⟧ is a fully specified memory promising roughly a tenfold overhead reduction over the surface code. What remains genuinely open is the hardware. These codes need long-range connectivity that today's fixed-grid superconducting chips do not natively provide; IBM's route is a layered layout with a few long couplers, while neutral-atom arrays offer reconfigurable connectivity by physically moving atoms. Decoders fast enough for real-time operation are still being optimized. So the honest answer is: the codes are ready and the overhead savings are real on paper, but demonstrating a large, fault-tolerant qLDPC memory on hardware is a frontier being crossed right now rather than a solved problem.

What is the difference between the hypergraph, balanced, and lifted products?

They are a ladder of increasingly powerful ways to glue classical codes into quantum ones, each fixing a limitation of the last. The hypergraph product (Tillich–Zémor) takes the tensor product of two classical chain complexes; it is simple and gives constant rate, but its distance is stuck at √N because the tensor product cannot manufacture cycles longer than the inputs'. The balanced product refines this by quotienting the tensor product by the action of a group shared between the two factors, which entangles them more tightly and can push the distance well past √N. The lifted product (Panteleev–Kalachev) is the balanced product specialized to codes built over group algebras — you "lift" small base matrices by a group to get large, highly structured, still-sparse codes, and this is one of the routes to genuinely good parameters. Each step trades a little simplicity for more distance; the good codes of 2022 live at the top of this ladder, or on the closely related quantum Tanner code construction.