Simple Algorithm
Quantum Computing · Rydberg State · 26 min

Quantum Code Bounds

Quantum Hamming, Singleton and what parameters are possible.

How many physical qubits does it take to protect kk logical qubits against tt errors? Counting arguments, entropy inequalities and linear programming set sharp limits, and some codes meet them exactly. The five-qubit code is the smallest code that corrects an arbitrary single-qubit error, and it is "perfect".

What you’ll learn

  • Derive the quantum Hamming bound for nondegenerate codes and identify perfect codes.
  • Prove the quantum Singleton bound n−k≥2(d−1)n-k\ge2(d-1) with an entropy argument, and relate it to no-cloning.
  • Verify the parameters and the syndrome table of the [[5,1,3]][[5,1,3]] code.
  • Compare asymptotic bounds (Hamming, Singleton, Gilbert–Varshamov) with locality constraints such as the Bravyi–Poulin–Terhal bound.

The quantum Hamming bound

DerivationCounting orthogonal subspaces
  1. Nt=∑j=0t(nj)3jN_t = \sum_{j=0}^{t}\binom{n}{j}3^j

    A code correcting tt errors must correct every Pauli error of weight at most tt; there are (nj)3j\binom nj3^j of weight exactly jj:

  2. Nt⋅2k  ≤  2nN_t\cdot2^k\;\le\;2^n

    If the code is nondegenerate, its KL matrix has full rank on these Paulis, so the NtN_t images EaCE_aC are mutually orthogonal 2k2^k-dimensional subspaces of C2n\mathbb{C}^{2^n}:

  3. kn  ≤  1−h(τ)−τlog⁡23+o(1)\frac kn\;\le\;1-h(\tau)-\tau\log_23+o(1)

    Asymptotically, with t=τnt = \tau n and τ≤34\tau\le\tfrac34, Stirling's formula gives

Predict before you look

According to the quantum Hamming bound, what is the smallest nn for a nondegenerate code with k=1k = 1 that corrects t=1t = 1 arbitrary error?

Show the answer

5

You need 1+3n≤2n−11+3n\le2^{n-1}. At n=4n = 4: 13>813>8. At n=5n = 5: 16≤1616\le16, with equality. A code at n=5n = 5 would therefore be perfect, and the [[5,1,3]][[5,1,3]] code is exactly that.

The quantum Singleton bound

DerivationEntropy proof
  1. ∣Ψ⟩RABC,∣A∣=∣B∣=d−1,∣C∣=n−2(d−1)\ket{\Psi}_{RABC},\qquad \abs{A} = \abs{B} = d-1,\qquad \abs{C} = n-2(d-1)

    Maximally entangle the kk logical qubits with a reference RR, giving a pure state with S(R)=kS(R) = k. Split the nn physical qubits into AA and BB of d−1d-1 qubits each and the remainder CC:

  2. ρRA=ρR⊗ρA,ρRB=ρR⊗ρB\rho_{RA} = \rho_R\otimes\rho_A,\qquad \rho_{RB} = \rho_R\otimes\rho_B

    A distance-dd code corrects the erasure of any d−1d-1 qubits. By the KL conditions the erased qubits, playing the environment, learn nothing about the logical state, so AA is uncorrelated with RR, and likewise BB:

  3. S(R)+S(A)=S(BC)≤S(B)+S(C),S(R)+S(B)=S(AC)≤S(A)+S(C)S(R)+S(A) = S(BC)\le S(B)+S(C),\qquad S(R)+S(B) = S(AC)\le S(A)+S(C)

    Because RABCRABC is pure, S(RA)=S(BC)S(RA) = S(BC) and S(RB)=S(AC)S(RB) = S(AC). Combine with subadditivity of the von Neumann entropy:

  4. 2S(R)≤2S(C)⟹k=S(R)≤S(C)≤∣C∣=n−2(d−1)□2S(R)\le2S(C)\quad\Longrightarrow\quad k = S(R)\le S(C)\le\abs{C} = n-2(d-1)\qquad\square

    Add the two inequalities and cancel S(A)+S(B)S(A)+S(B):

Check your understanding

Which code parameters are impossible?

  1. [[5,1,3]][[5,1,3]]
  2. [[4,2,2]][[4,2,2]]
  3. [[4,1,3]][[4,1,3]]
  4. [[7,1,3]][[7,1,3]]
Show the answer

C. [[4,1,3]][[4,1,3]]

Singleton requires n−k≥2(d−1)n-k\ge2(d-1), and [[4,1,3]][[4,1,3]] has 3<43<4. The others satisfy it: [[5,1,3]][[5,1,3]] and [[4,2,2]][[4,2,2]] with equality, [[7,1,3]][[7,1,3]] with room to spare.

The perfect five-qubit code

The [[5,1,3]][[5,1,3]] code (Laflamme, Miquel, Paz & Zurek 1996; Bennett, DiVincenzo, Smolin & Wootters 1996) saturates both the Hamming and the Singleton bound. Its stabilizer is generated by the cyclic shifts of XZZXIXZZXI:

g1=XZZXI,g2=IXZZX,g3=XIXZZ,g4=ZXIXZ,Xˉ=XXXXX,Zˉ=ZZZZZg_1 = XZZXI,\quad g_2 = IXZZX,\quad g_3 = XIXZZ,\quad g_4 = ZXIXZ,\qquad \bar X = XXXXX,\quad \bar Z = ZZZZZ
Qubit jjXjX_jZjZ_jYjY_j
1000110101011
2100001011101
3110000101110
4011010011111
5001101000111
Syndromes (s1s2s3s4)(s_1s_2s_3s_4), where si=1s_i = 1 if the error anticommutes with gig_i. All 15 are distinct and nonzero; together with "no error" they use all 24=162^4 = 16 syndromes.

Every pair of generators meets XX against ZZ in exactly two positions, so they commute, and Xˉ\bar X, Zˉ\bar Z commute with all of them while anticommuting with each other. No syndrome is left over, which is what perfect means. The code is not CSS, since its generators mix XX and ZZ; the smallest CSS code that encodes one qubit and corrects an arbitrary single error is the 7-qubit Steane code.

The landscape of possible codes

BoundStatementAsymptotic form (δ=d/n\delta = d/n, R=k/nR = k/n)
Quantum Singletonn−k≥2(d−1)n-k\ge2(d-1)R≤1−2δR\le1-2\delta
Quantum Hamming (nondegenerate)2k∑j≤t(nj)3j≤2n2^k\sum_{j\le t}\binom nj3^j\le2^nR≤1−h(δ/2)−δ2log⁡23R\le1-h(\delta/2)-\tfrac\delta2\log_23
Linear programminginequalities on quantum weight enumerators (Rains; Ashikhmin & Litsyn)typically the strongest upper bounds
Quantum Gilbert–Varshamovexistence of random stabilizer codesR≥1−h(δ)−δlog⁡23R\ge1-h(\delta)-\delta\log_23 is achievable
Upper bounds (first three rows) and an existence bound (last row) for qubit codes.

Between the Gilbert–Varshamov existence bound and the upper bounds lies a gap that, as for classical codes, has not been closed. For small nn, exhaustive searches and linear-programming bounds pin down the optimal parameters, which are collected in online code tables. For example, k=1k = 1 and d=5d = 5 need n≥9n\ge9 by Singleton and n≥10n\ge10 by Hamming (for nondegenerate codes), while the smallest code that achieves it has n=11n = 11.

Key takeaways

  • Quantum Hamming: nondegenerate codes need 2k∑j≤t(nj)3j≤2n2^k\sum_{j\le t}\binom nj3^j\le2^n; the [[5,1,3]][[5,1,3]] code meets it with equality and is perfect.
  • Quantum Singleton: n−k≥2(d−1)n-k\ge2(d-1), proven by decoupling plus subadditivity; for k=1k = 1 it is the no-cloning theorem in coding language.
  • Upper bounds (Singleton, Hamming, linear programming) and the Gilbert–Varshamov existence bound bracket the achievable region, and the gap between them is open.
  • Geometric locality imposes stronger limits, kd2=O(n)kd^2 = \order{n} in 2D, which is why qLDPC codes need long-range connectivity.

Check yourself

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

Question 1

Which code saturates both the quantum Hamming bound and the quantum Singleton bound?

  1. [[7,1,3]][[7,1,3]]
  2. [[9,1,3]][[9,1,3]]
  3. [[5,1,3]][[5,1,3]]
  4. [[4,2,2]][[4,2,2]]
Show the answer

C. [[5,1,3]][[5,1,3]]

Hamming: (1+15)⋅2=25(1+15)\cdot2 = 2^5, equality. Singleton: 5−1=2(3−1)5-1 = 2(3-1), equality.

Question 2

For k=1k = 1 and d=5d = 5, which lower bound on nn is stronger for nondegenerate codes?

  1. Singleton: n≥9n\ge9
  2. Hamming: n≥10n\ge10
  3. Both give n≥11n\ge11
  4. Neither bound applies to d=5d = 5
Show the answer

B. Hamming: n≥10n\ge10

Singleton: n−1≥8n-1\ge8, so n≥9n\ge9. Hamming with t=2t = 2: 2(1+3n+9(n2))≤2n2\big(1+3n+9\binom n2\big)\le2^n fails at n=9n = 9 (704>512704>512) and holds at n=10n = 10 (872≤1024872\le1024).

Question 3

In the entropy proof of the Singleton bound, why is ρRA=ρR⊗ρA\rho_{RA} = \rho_R\otimes\rho_A for any set AA of d−1d-1 qubits?

  1. Because ρA\rho_A is maximally mixed
  2. Because the erasure of AA is correctable, so by the KL conditions AA carries no information about the logical state
  3. Because RR never interacts with the physical qubits
  4. Because of the subadditivity of entropy
Show the answer

B. Because the erasure of AA is correctable, so by the KL conditions AA carries no information about the logical state

Correctability of an erasure means the erased subsystem, acting as the environment, learns nothing: its state and its correlations with the reference are independent of the encoded information. That is decoupling, I(R:A)=0I(R{:}A) = 0.

Question 4

Why can a 2D surface code on nn physical qubits have distance at most of order n\sqrt n?

  1. Because the surface code is not a stabilizer code
  2. Because of the quantum Hamming bound
  3. Because every 2D geometrically local stabilizer code has d=O(n)d = \order{\sqrt n} (Bravyi–Terhal), and more generally kd2=O(n)kd^2 = \order{n}
  4. Because of the quantum Singleton bound
Show the answer

C. Because every 2D geometrically local stabilizer code has d=O(n)d = \order{\sqrt n} (Bravyi–Terhal), and more generally kd2=O(n)kd^2 = \order{n}

Locality, not counting, is the binding constraint. In 2D a logical operator can always be "cleaned" into a strip of constant width across the lattice, so its weight, and hence dd, is at most O(L)=O(n)\order{L} = \order{\sqrt n}.

Further reading

  • A. Ekert & C. Macchiavello, "Quantum error correction for communication", Physical Review Letters 77, 2585 (1996).
  • E. Knill & R. Laflamme, "Theory of quantum error-correcting codes", Physical Review A 55, 900 (1997).
  • R. Laflamme, C. Miquel, J. P. Paz & W. H. Zurek, "Perfect quantum error correcting code", Physical Review Letters 77, 198 (1996).
  • D. Gottesman, Stabilizer Codes and Quantum Error Correction, PhD thesis, Caltech (1997), arXiv:quant-ph/9705052.
  • S. Bravyi, D. Poulin & B. Terhal, "Tradeoffs for reliable quantum information storage in 2D systems", Physical Review Letters 104, 050503 (2010).