PadhaikoAll subjects

Quantum Error and Correction

Quantum Computing (ENCT 328)

Open in the Padhaiko app

6.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:

  1. No-Cloning Theorem: An unknown state cannot be copied into . Quantum Error Correction (QEC) instead entangles one logical qubit across multiple physical qubits ().
  2. 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 .
  3. 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 :

Syndrome Table for the 3-Qubit Bit-Flip Code
ErrorCorrupted State Eigenvalue EigenvalueSyndrome Recovery
None ()
(Qubit 1)
(Qubit 2)
(Qubit 3)

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:


6.2 Simple quantum error detection

Definition

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):

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 :

Measuring only the ancilla extracts the error syndrome while keeping completely unmeasured.

Simple Error-Detecting Codes and the Quantum Hamming Bound

  1. 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 ().
  2. 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.
  3. 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).

Definition

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:

How Shor's Code Corrects Arbitrary Continuous Errors

  1. Bit-Flip Correction (): If strikes qubit inside Block , the two -parity checks in Block pinpoint qubit and restores it.
  2. 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.
  3. Combined Error (): Triggers both the intra-block -parity syndrome and the inter-block -parity syndrome; applying and corrects both errors simultaneously.
  4. 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.

Definition

The Rotated Surface Code Architecture

The surface code arranges qubits on a 2D checkerboard grid containing two distinct qubit roles:

In the rotated surface code of code distance (odd integer ):

Logical Operators, Decoding, and Threshold Theorem

AspectShor's 9-Qubit Code2D Surface Code
Parameters (fixed distance ) (scalable distance )
Stabilizer WeightWeight- () and Weight- ()Strictly local Weight- (bulk) and Weight- (boundary)
Hardware ConnectivityRequires non-local 6-qubit interactions2D nearest-neighbor planar grid only
Fault-Tolerant ThresholdLower ( without concatenation overhead)High ( physical gate error threshold)

Worked Examples

Example 6.1

6.1

A logical qubit in state is encoded using the 3-qubit bit-flip code.

  1. Write the encoded state and the corrupted state if a bit-flip error occurs on qubit 2.
  2. Determine the eigenvalues of stabilizers and for and identify the syndrome and recovery operator.
  3. 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 ().

Answer:
  1. Encoded: ; Corrupted: .
  2. Eigenvalues: and (syndrome ); recovery gate is .
  3. Logical failure probability: ().
Example 6.2

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.

Answer:
  • 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 .
Example 6.3

6.3

Consider a rotated surface code protecting a single logical qubit.

  1. 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.
  2. 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 .

Answer:
  1. For : data qubits, ancilla qubits, physical qubits total, correcting up to arbitrary errors.
  2. Logical error rates: vs. (a exponential suppression).

Practice Exercises

Practice Exercises — Quantum Error and Correction

Question 1

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.

Answer:

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).

Question 2

Consider the 3-qubit phase-flip code with logical basis states and , protecting . Suppose a phase-flip error occurs on qubit 1.

  1. Write the corrupted state .
  2. 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 .

Answer:
  1. Corrupted state: .
  2. Eigenvalues: , ; recovery gate: .
Question 3

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).

Answer:

For , violates the Quantum Hamming Bound. For , satisfies it with equality, proving is the minimum.

Question 4

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.

Answer:

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).

Question 5

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:

  1. 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.
  2. Scalable Distance: Increasing lattice size scales protection continuously without redesigning gate geometry.
  3. High Threshold (): Tolerates realistic superconducting gate errors ().

Qubit Count and Error Capacity for :

  • Data qubits:
  • Ancilla qubits:
  • Total physical qubits:
  • Correctable errors:
Answer:

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.

← Quantum Hardware and NISQ EraQuantum Annealing, Optimization Algorithms →