Quantum Error Correction Basics
Protecting information you are not allowed to look at.
Error correction looks impossible for qubits: you cannot copy them, you cannot look at them, and their errors form a continuum. In this lesson you build, gate by gate, the codes that get around all three obstacles, ending with Shor's nine-qubit code, which corrects any error on a single qubit.
What you’ll learn
- Encode a qubit into the three-qubit bit-flip and phase-flip codes and decode their syndrome tables.
- Extract syndromes with ancillas without disturbing the encoded superposition.
- Derive the logical error rate and the break-even point .
- Explain how Shor's code corrects arbitrary single-qubit errors, and why correcting and is enough (discretization of errors).
The bit-flip code
Encode into three qubits with two CNOTs from the data qubit onto two fresh qubits in :
A bit flip moves the state out of the code space into one of three orthogonal subspaces, one per qubit. The parity operators and have every code state as a eigenstate, and each single flip anticommutes with a different subset of them. Their eigenvalues form the syndrome:
| Error | State after the error | Correction | ||
|---|---|---|---|---|
| none | none | |||
With independent flips of probability , decoding fails exactly when at least two qubits flip:
The code helps iff . For the factor is negative, so this requires :
For small , : errors are suppressed quadratically. At , .
For the three-qubit bit-flip code with independent flips at , what is the logical error rate, in %?
Show the answer
0.725 %
, i.e. 0.725%: about seven times better than the unencoded 5%.
Measuring the syndrome without measuring the data
Measuring is a two-qubit measurement. In a circuit you copy the parity onto an ancilla with two CNOTs and measure the ancilla instead. Why doesn't that collapse the encoded superposition?
Suppose occurred. Add ancillas (for ) and (for ), both in :
CNOTs from qubits 1 and 2 onto , and from qubits 2 and 3 onto , write the parities into the ancillas. Both branches have the same parities:
The ancillas end up in a product state with the data. Measuring them gives with certainty and reveals nothing about or . Applying finishes the job.
Phase flips: the same code in the Hadamard basis
A error commutes with and , so the bit-flip code is blind to it. But : in the basis a phase flip is a bit flip, since . So encode in that basis:
Every statement about the bit-flip code transfers by conjugating with . The syndromes and locate a single error, which is undone by applying . Measuring uses the same ancilla circuit sandwiched between Hadamards on the data qubits.
In the phase-flip code, a error hits qubit 3. What do the checks and report?
Show the answer
C.
anticommutes with (they meet on qubit 3, against ) and commutes with (no overlap). It is the same pattern as in the bit-flip code.
Shor's nine-qubit code and the discretization of errors
Concatenate the two codes: protect each qubit of the phase-flip code with its own bit-flip code (Shor 1995).
| Checks | Operators | What they detect |
|---|---|---|
| Inner (bit-flip) | one error in any block of three | |
| Outer (phase-flip) | one sign flip among the three blocks |
A error hits qubit 5 (in the middle block) of Shor's code. Which checks report ?
- and
- Only
- No check: is undetectable
- Both outer checks, and
Show the answer
D. Both outer checks, and
anticommutes with every check that contains , i.e. both outer checks, and commutes with all the -type checks. The pattern on the outer checks points to the middle block, and applying to any of its qubits (, or ) undoes the error.
Notice the last point: , and act identically on the code space, because and are checks and act trivially on code states. The decoder need not know which of them happened. Codes in which distinct errors have the same effect are called degenerate, a purely quantum phenomenon.
Any operator acting on qubit is a linear combination of Paulis:
Acting on a code state, it produces a superposition of four standard error branches:
In Shor's code the four branches have different syndromes, so they lie in mutually orthogonal subspaces. Measuring the syndrome projects onto one branch, say with probability , and the correction then restores exactly:
By linearity the same holds for every Kraus operator of any single-qubit noise channel and for coherent rotations: becomes "no error" with probability and a full with probability . A code that corrects a discrete set of errors corrects every linear combination of them.
Key takeaways
- The bit-flip code corrects one error using the parities and ; its logical error rate beats whenever .
- Syndromes are extracted with CNOTs onto ancillas. Every code state has the same parities, so the ancillas factor out and the superposition survives.
- Conjugating by Hadamards gives the phase-flip code for errors; Shor's code concatenates the two and corrects an arbitrary single-qubit error.
- Syndrome measurement discretizes errors: correcting , , , on each qubit corrects every linear combination, including small coherent rotations.
- Quantum codes can be degenerate: different errors may act identically on the code space.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
In the bit-flip code the syndrome is , . Which correction do you apply?
- None
Show the answer
C.
Only qubit 3 belongs to but not to , so a flip there changes exactly the second parity.
Why can't the phase-flip code correct a single error?
- Because errors are too rare to matter
- Because commutes with both checks, yet acts on the code space as a logical (it flips the sign of )
- Because errors take the state out of the qubits' Hilbert space
- Because measuring collapses the encoded state
Show the answer
B. Because commutes with both checks, yet acts on the code space as a logical (it flips the sign of )
, so while : an undetectable logical phase flip. The phase-flip code just swaps which kind of error is invisible.
A small coherent error acts on a qubit encoded in the bit-flip code, and then the syndrome is measured. What happens?
- The code fails, because only discrete errors can be corrected
- A residual rotation of order is left over
- With probability the syndrome is trivial and the state is restored exactly; otherwise is detected and corrected
- The syndrome measurement amplifies the error into a logical flip
Show the answer
C. With probability the syndrome is trivial and the state is restored exactly; otherwise is detected and corrected
. The two branches have different syndromes, so the measurement collapses onto one of them, and both outcomes are fully recoverable.
Which of these multi-qubit errors does Shor's code correct?
Show the answer
C.
and sit in different blocks, and each inner bit-flip code fixes its own single flip independently.
Go deeper
- The Knill–Laflamme Conditions · Exactly when a code can correct a set of errors.
- CSS Codes & the Steane Code · Quantum codes from pairs of classical codes.
- Quantum Code Bounds · Quantum Hamming, Singleton and what parameters are possible.
Further reading
- P. W. Shor, "Scheme for reducing decoherence in quantum computer memory", Physical Review A 52, R2493 (1995).
- A. M. Steane, "Error correcting codes in quantum theory", Physical Review Letters 77, 793 (1996).
- M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §10.1–10.3 (Cambridge, 10th anniv. ed., 2010).
- S. J. Devitt, W. J. Munro & K. Nemoto, "Quantum error correction for beginners", Reports on Progress in Physics 76, 076001 (2013).