Quantum Code Bounds
Quantum Hamming, Singleton and what parameters are possible.
How many physical qubits does it take to protect logical qubits against 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 with an entropy argument, and relate it to no-cloning.
- Verify the parameters and the syndrome table of the code.
- Compare asymptotic bounds (Hamming, Singleton, Gilbert–Varshamov) with locality constraints such as the Bravyi–Poulin–Terhal bound.
The quantum Hamming bound
A code correcting errors must correct every Pauli error of weight at most ; there are of weight exactly :
If the code is nondegenerate, its KL matrix has full rank on these Paulis, so the images are mutually orthogonal -dimensional subspaces of :
Asymptotically, with and , Stirling's formula gives
According to the quantum Hamming bound, what is the smallest for a nondegenerate code with that corrects arbitrary error?
Show the answer
5
You need . At : . At : , with equality. A code at would therefore be perfect, and the code is exactly that.
The quantum Singleton bound
Maximally entangle the logical qubits with a reference , giving a pure state with . Split the physical qubits into and of qubits each and the remainder :
A distance- code corrects the erasure of any qubits. By the KL conditions the erased qubits, playing the environment, learn nothing about the logical state, so is uncorrelated with , and likewise :
Because is pure, and . Combine with subadditivity of the von Neumann entropy:
Add the two inequalities and cancel :
Which code parameters are impossible?
Show the answer
C.
Singleton requires , and has . The others satisfy it: and with equality, with room to spare.
The perfect five-qubit code
The 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 :
| Qubit | |||
|---|---|---|---|
| 1 | 0001 | 1010 | 1011 |
| 2 | 1000 | 0101 | 1101 |
| 3 | 1100 | 0010 | 1110 |
| 4 | 0110 | 1001 | 1111 |
| 5 | 0011 | 0100 | 0111 |
Every pair of generators meets against in exactly two positions, so they commute, and , 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 and ; 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
| Bound | Statement | Asymptotic form (, ) |
|---|---|---|
| Quantum Singleton | ||
| Quantum Hamming (nondegenerate) | ||
| Linear programming | inequalities on quantum weight enumerators (Rains; Ashikhmin & Litsyn) | typically the strongest upper bounds |
| Quantum Gilbert–Varshamov | existence of random stabilizer codes | is achievable |
Between the Gilbert–Varshamov existence bound and the upper bounds lies a gap that, as for classical codes, has not been closed. For small , exhaustive searches and linear-programming bounds pin down the optimal parameters, which are collected in online code tables. For example, and need by Singleton and by Hamming (for nondegenerate codes), while the smallest code that achieves it has .
Key takeaways
- Quantum Hamming: nondegenerate codes need ; the code meets it with equality and is perfect.
- Quantum Singleton: , proven by decoupling plus subadditivity; for 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, 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.
Which code saturates both the quantum Hamming bound and the quantum Singleton bound?
Show the answer
C.
Hamming: , equality. Singleton: , equality.
For and , which lower bound on is stronger for nondegenerate codes?
- Singleton:
- Hamming:
- Both give
- Neither bound applies to
Show the answer
B. Hamming:
Singleton: , so . Hamming with : fails at () and holds at ().
In the entropy proof of the Singleton bound, why is for any set of qubits?
- Because is maximally mixed
- Because the erasure of is correctable, so by the KL conditions carries no information about the logical state
- Because never interacts with the physical qubits
- Because of the subadditivity of entropy
Show the answer
B. Because the erasure of is correctable, so by the KL conditions 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, .
Why can a 2D surface code on physical qubits have distance at most of order ?
- Because the surface code is not a stabilizer code
- Because of the quantum Hamming bound
- Because every 2D geometrically local stabilizer code has (Bravyi–Terhal), and more generally
- Because of the quantum Singleton bound
Show the answer
C. Because every 2D geometrically local stabilizer code has (Bravyi–Terhal), and more generally
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 , is at most .
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).