Quantum Error and Correction
Open in the Padhaiko app6.1 Bit-flip and phase-flip errors
Classical error correction protects a bit by duplicating it (, ) and taking a majority vote. Protecting quantum information is fundamentally harder due to three quantum obstacles:
- No-Cloning Theorem: An unknown state cannot be copied into . Quantum Error Correction (QEC) instead entangles one logical qubit across multiple physical qubits ().
- Wavefunction Collapse: Measuring individual data qubits directly collapses superposition and destroys the amplitudes . QEC must measure multi-qubit parity syndromes via ancilla qubits without learning or .
- Continuous Error Spectrum: Quantum errors can be arbitrary continuous rotations or decoherence channels, not just discrete flips. Remarkably, measuring discrete syndromes discretizes any continuous error onto a finite basis of Pauli errors .
The 3-Qubit Bit-Flip Code ( Error)
A bit-flip error applies the Pauli- operator with probability (). To protect against single bit-flips, we encode one logical qubit into three physical qubits using two gates:
To detect which qubit flipped without disturbing and , we measure the two parity stabilizer observables and :
| Error | Corrupted State | Eigenvalue | Eigenvalue | Syndrome | Recovery |
|---|---|---|---|---|---|
| None () | |||||
| (Qubit 1) | |||||
| (Qubit 2) | |||||
| (Qubit 3) |
- Success Probability: Correctable whenever or physical bit-flips occur. Failure occurs only when or qubits flip independently:
Whenever , (error suppression!).
The 3-Qubit Phase-Flip Code ( Error)
A phase-flip error applies the Pauli- operator with probability , mapping . Classical computers have no phase-flip error.
Because and , a phase-flip in the basis is identical to a bit-flip in the Hadamard basis (, ). Applying after the bit-flip encoder gives the 3-qubit phase-flip code:
- Measuring the parity stabilizers and diagnoses single errors () with the exact same 4 syndromes, corrected by applying .
6.2 Simple quantum error detection
Stabilizer Syndrome Extraction and Code Distance
A quantum error-detecting or error-correcting code denoted encodes logical qubits into physical qubits with code distance (the minimum weight of a non-trivial Pauli operator mapping one valid codeword to another):
- Error Detection Capacity: Detects up to arbitrary single-qubit errors.
- Error Correction Capacity: Unambiguously corrects up to errors.
Ancilla Syndrome Extraction: To measure a parity stabilizer without collapsing the logical superposition , an ancilla qubit initialized to acts as target for two gates controlled by qubits and :
- If qubits and have even parity ( or ), the ancilla flips twice and stays (eigenvalue , syndrome ).
- If qubits and have odd parity ( or ), the ancilla flips once to (eigenvalue , syndrome ).
Measuring only the ancilla extracts the error syndrome while keeping completely unmeasured.
Simple Error-Detecting Codes and the Quantum Hamming Bound
- 2-Qubit Bit-Flip Detection Code ( for errors only): Encoding allows measuring . A single or error flips the parity to , detecting that an error occurred, but cannot distinguish from , so it cannot correct the error ().
- The Error-Detecting Code: Encodes logical qubits in physical qubits using two stabilizers and . Any single-qubit , , or error anticommutes with at least one stabilizer and is flagged for post-selection/discard.
- Quantum Hamming Bound: For a non-degenerate code correcting any single-qubit error ( errors of type plus no-error state ), orthogonal subspaces require:
For : gives (impossible), whereas gives , achieved by Laflamme's perfect code.
6.3 Shor’s 9-qubit code
In 1995, Peter Shor proved that fault-tolerant quantum storage is possible by constructing the Shor code—the first code capable of correcting arbitrary single-qubit errors (, , , and continuous superpositions thereof).
Shor's 9-Qubit Concatenated Code
Shor's code concatenates the 3-qubit phase-flip code (outer layer) with three independent 3-qubit bit-flip codes (inner layer):
The qubits are partitioned into three 3-qubit blocks: Block 1 , Block 2 , and Block 3 . Its codespace is stabilized by independent stabilizer generators:
- Six Bit-Flip Stabilizers (within blocks):
- Two Phase-Flip Stabilizers (between blocks):
How Shor's Code Corrects Arbitrary Continuous Errors
- Bit-Flip Correction (): If strikes qubit inside Block , the two -parity checks in Block pinpoint qubit and restores it.
- Phase-Flip Correction (): Any inside Block flips for that entire block. The two weight-6 stabilizers detect which block's phase flipped, and applying (on any qubit of that block) restores the phase.
- Combined Error (): Triggers both the intra-block -parity syndrome and the inter-block -parity syndrome; applying and corrects both errors simultaneously.
- Error Discretization: Any arbitrary single-qubit error operator on qubit expands in the Pauli basis as . Measuring the stabilizer syndromes collapses the state into a definite Pauli error branch , which is then reversed deterministically.
6.4 Surface code overview
While Shor's 9-qubit code requires long-range weight-6 stabilizer measurements (), physical 2D hardware (such as superconducting transmon arrays) restricts gates to nearest-neighbor couplings. The Surface Code solves this by placing all stabilizer checks on a local 2D planar lattice.
The Rotated Surface Code Architecture
The surface code arranges qubits on a 2D checkerboard grid containing two distinct qubit roles:
- Data Qubits: Store the encoded logical quantum information.
- Measure (Syndrome) Ancilla Qubits: Interleaved among data qubits and coupled solely to at most immediate nearest-neighbor data qubits:
- -Stabilizers (Plaquettes / Stars): Measure around adjacent data qubits to detect (phase-flip) errors.
- -Stabilizers (Vertices / Plaquettes): Measure around adjacent data qubits to detect (bit-flip) errors.
In the rotated surface code of code distance (odd integer ):
- Data qubits:
- Ancilla syndrome qubits:
- Total physical qubits per logical qubit:
- Correctable errors: Up to arbitrary single-qubit errors.
Logical Operators, Decoding, and Threshold Theorem
- Topological Logical Operators: A logical bit-flip is a chain of single-qubit gates stretching across the lattice from top boundary to bottom boundary, while logical is a perpendicular chain of gates stretching from left boundary to right boundary. Because they cross at an odd number of data qubits, as required for a logical qubit, and no local noise chain shorter than can cause an undetected logical error.
- Classical Decoding (MWPM): Errors create pairs of violated stabilizers ("syndrome defects") at the endpoints of error chains. Classical decoders such as Minimum-Weight Perfect Matching (MWPM) pair nearby defects to infer the most likely correction chain.
- High Error Threshold (): Because stabilizers are local weight-4 checks, the surface code achieves a fault-tolerant error threshold of roughly ()—among the highest known. Whenever physical gate error , increasing the code distance suppresses the logical error rate exponentially:
| Aspect | Shor's 9-Qubit Code | 2D Surface Code |
|---|---|---|
| Parameters | (fixed distance ) | (scalable distance ) |
| Stabilizer Weight | Weight- () and Weight- () | Strictly local Weight- (bulk) and Weight- (boundary) |
| Hardware Connectivity | Requires non-local 6-qubit interactions | 2D nearest-neighbor planar grid only |
| Fault-Tolerant Threshold | Lower ( without concatenation overhead) | High ( physical gate error threshold) |
Worked Examples
6.1
A logical qubit in state is encoded using the 3-qubit bit-flip code.
- Write the encoded state and the corrupted state if a bit-flip error occurs on qubit 2.
- Determine the eigenvalues of stabilizers and for and identify the syndrome and recovery operator.
- If each physical qubit experiences an independent bit-flip probability , calculate the uncorrectable logical error probability .
Encoding and Bit-Flip Error : Mapping and :
Applying flips the middle qubit of both basis states:
Evaluating Stabilizer Eigenvalues: Recall and :
- Applying :
- On :
- On : Thus (eigenvalue , syndrome bit ).
- Applying :
- On :
- On : Thus (eigenvalue , syndrome bit ).
Syndrome uniquely identifies error , so applying recovery gate restores without altering or .
Logical Failure Probability (): Failure occurs when or qubits flip:
The logical error rate () is nearly smaller than the physical error rate ().
- Encoded: ; Corrupted: .
- Eigenvalues: and (syndrome ); recovery gate is .
- Logical failure probability: ().
6.2
In Shor's 9-qubit code, suppose a combined bit-and-phase error occurs on physical qubit (inside Block 2: qubits ). Determine the eigenvalues ( or ) of all stabilizer generators, and show how the recovery circuit restores the logical state.
Checking the Six Bit-Flip Stabilizers ():
- Block 1 (): Act on qubits commute with eigenvalues .
- Block 2 (): Both and share qubit with , and both anticommute eigenvalues .
- Block 3 (): Act on qubits eigenvalues .
From the -stabilizer syndromes alone, the decoder identifies a bit-flip on qubit ().
Checking the Two Phase-Flip Stabilizers ():
- : Shares qubit with , and eigenvalue .
- : Also shares qubit with eigenvalue .
Seeing on tells the decoder that a phase flip occurred in Block 2 (which intersects both weight-6 checks).
Applying Recovery Operators: The decoder applies (for the bit-flip syndrome) followed by (or any in Block 2, e.g. ):
Because is an unobservable global phase, the original logical state is restored identically.
- Bit-flip stabilizers: Block 1 , Block 2 , Block 3 diagnoses .
- Phase-flip stabilizers: and diagnoses phase flip in Block 2 ().
- Recovery: Applying restores up to an irrelevant global phase .
6.3
Consider a rotated surface code protecting a single logical qubit.
- For distance , calculate the number of data qubits, syndrome ancilla qubits, and total physical qubits required, as well as the maximum number of arbitrary single-qubit errors it can correct.
- Using the empirical logical error scaling formula with physical error rate and threshold , compare the logical error rate at and .
Qubit Counts and Error-Correction Capacity (): For the rotated surface code :
- Data qubits:
- Syndrome ancilla qubits:
- Total physical qubits:
- Correctable single-qubit errors:
Comparing Logical Error Rates ( vs. ): With :
- For : exponent is :
- For : exponent is :
Increasing the distance from to (from to physical qubits) reduces the logical error rate by a factor of .
- For : data qubits, ancilla qubits, physical qubits total, correcting up to arbitrary errors.
- Logical error rates: vs. (a exponential suppression).
Practice Exercises
Practice Exercises — Quantum Error and Correction
Explain why classical repetition error correction (, reading all three bits and taking a majority vote) cannot be directly applied to quantum states. Describe how quantum error correction overcomes each obstacle.
Obstacle 1 — No-Cloning Theorem: Classically, an arbitrary bit can be copied freely (). Quantum mechanically, the No-Cloning Theorem forbids any unitary operator from mapping . QEC overcomes this by entangling logical basis states across multiple qubits: .
Obstacle 2 — Measurement Collapse: Reading individual physical qubits collapses the superposition and destroys the relative phase and amplitudes . QEC overcomes this by measuring multi-qubit parity stabilizers (such as and ) via ancilla qubits, revealing which error occurred without learning whether the qubit is or .
Obstacle 3 — Continuous Errors: Quantum noise induces continuous rotations rather than discrete flips. QEC overcomes this because projective syndrome measurement discretizes any continuous error superposition into a single discrete Pauli error that can be inverted cleanly.
Classical repetition fails due to (1) No-Cloning (overcome by entangled encoding), (2) Measurement Collapse (overcome by ancilla parity-syndrome measurement), and (3) Continuous Errors (overcome by syndrome-induced error discretization into discrete Pauli operators).
Consider the 3-qubit phase-flip code with logical basis states and , protecting . Suppose a phase-flip error occurs on qubit 1.
- Write the corrupted state .
- Compute the eigenvalues of the phase-flip stabilizers and , and state the recovery operation.
Corrupted State After : Recall that and . Applying to :
Evaluating and Eigenvalues: Recall and :
- For :
- On :
- On : Hence yields eigenvalue (syndrome bit ).
- For :
- On :
- On : Hence yields eigenvalue (syndrome bit ).
Syndrome uniquely identifies a phase-flip on qubit 1, so applying restores .
- Corrupted state: .
- Eigenvalues: , ; recovery gate: .
Using the Quantum Hamming Bound for a non-degenerate quantum error-correcting code encoding logical qubit and correcting any single-qubit error ( or ), prove mathematically that physical qubits is insufficient and that is the minimum possible number of physical qubits.
Formulating the Bound for : Each single-qubit error ( for ) plus the no-error identity accounts for distinct error cases. Because a non-degenerate code requires orthogonal -dimensional subspaces for every correctable error inside the -dimensional Hilbert space:
Testing and :
- :
- :
- :
- : (violates bound!)
- : (equality holds!)
Thus, is the strict minimum (achieved by the code).
For , violates the Quantum Hamming Bound. For , satisfies it with equality, proving is the minimum.
In Shor's 9-qubit code, explain why two different phase-flip errors and (occurring on qubits 1 and 2 of the same block) produce the exact same syndrome, and why correcting with still perfectly repairs a error.
Syndrome Equivalence Within Block 1: In Block 1, the logical codewords use the GHZ-like state . Applying either or (or ) flips the sign of while leaving unchanged:
Because and act identically on the Block 1 codespace ( is a stabilizer of Block 1 with eigenvalue ), both errors produce the exact same syndrome (, ).
Degeneracy and Equivalence of Recovery: If occurred and the decoder applies , the net operator on the state is . Since stabilizes :
This property—where distinct physical errors act identically on the codespace—is called quantum degeneracy and allows Shor's 9-qubit code to compress phase errors onto blocks rather than individual qubits.
Because is a stabilizer of Block 1, and have the exact same action on and yield identical syndromes. Applying after leaves (an example of quantum degeneracy).
Why is the 2D Surface Code favored over Shor's 9-qubit code for large-scale superconducting quantum processors? For a distance- rotated surface code , how many total physical qubits (data + ancilla) are required per logical qubit, and how many arbitrary single-qubit errors can it correct?
Advantages of the Surface Code:
- 2D Nearest-Neighbor Locality: All stabilizer checks ( and ) involve only immediate adjacent neighbors on a 2D planar chip, avoiding Shor's non-local weight-6 gates.
- Scalable Distance: Increasing lattice size scales protection continuously without redesigning gate geometry.
- High Threshold (): Tolerates realistic superconducting gate errors ().
Qubit Count and Error Capacity for :
- Data qubits:
- Ancilla qubits:
- Total physical qubits:
- Correctable errors:
The Surface Code uses only 2D nearest-neighbor weight-4 checks, scales cleanly with , and has a high error threshold. A distance- rotated surface code uses physical qubits ( data + ancilla) and corrects up to arbitrary errors.