The repetition code: finding an error without looking at the data

The simplest error-correcting code is to repeat a bit three times. Learn how, in the quantum case, to find where an error is without measuring the data, by measuring only parities (the syndrome).

Classical repetition

To send a bit over a noisy channel you can send it three times: 000 for 0 and 111 for 1. The receiver takes the majority; even if one bit flips, the right value is recovered. If each bit flips with probability p, a logical error needs at least two flipped bits and its probability is 3p² − 2p³.

For p = 1% this is about 0.03%: the error drops by a factor of 30. But the code only helps when p is small; with p = 50% repetition would gain nothing.

for p in [0.1, 0.01, 0.001]:
    print(p, f'{3 * p**2 - 2 * p**3:.6f}')
# 0.1 0.028000
# 0.01 0.000298
# 0.001 0.000003

Two obstacles in the quantum case

We cannot copy qubits, and measuring them destroys superposition. The solution: use entanglement instead of copies and measure not the data but only whether the bits are equal to each other. The state a|0⟩ + b|1⟩ is encoded with two CNOTs as a|000⟩ + b|111⟩; this is not a copy but a single state spread over three qubits.

Then the parities q0 ⊕ q1 and q1 ⊕ q2 are written onto two helper (check) qubits. These two bits are called the syndrome. The syndrome says nothing about a and b; it only shows where the error is: 00 means no error, 01 means q0, 11 means q1 and 10 means q2 is flipped. Applying another X to the flipped qubit corrects the error.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

# q0, q1, q2 are data qubits; q3 and q4 are syndrome qubits
for wrong in [None, 0, 1, 2]:
    qc = QuantumCircuit(5)
    qc.cx(0, 1)
    qc.cx(0, 2)                  # encoding: |0⟩ → |000⟩
    if wrong is not None:
        qc.x(wrong)              # a single bit flip
    qc.cx(0, 3)
    qc.cx(1, 3)                  # q3 = q0 ⊕ q1
    qc.cx(1, 4)
    qc.cx(2, 4)                  # q4 = q1 ⊕ q2
    probs = Statevector(qc).probabilities_dict()
    print(wrong, max(probs, key=probs.get)[:2])   # syndrome: q4 q3
# None 00
# 0 01
# 1 11
# 2 10

Its limits

The three-qubit repetition code corrects only bit flips; it offers no protection against phase flips. And if two bits flip at the same time, the syndrome points to the wrong qubit and the “correction” makes the error worse. In the next lesson we will see the code that catches phase flips and Shor’s code that combines the two.

Try it yourself

The syndrome 11 says the error is on q1. Remove the X on q1: the result becomes 00000, so there is no error. Then add an X on q2: the syndrome becomes 10. We found where the error is without ever measuring the values of the data qubits.

Open the circuit in your browser

The circuit playground is in Turkish. Button guide: “1000 kez ölç” = measure 1000 times, “Durum vektörünü göster” = show the state vector, “Bu devrenin Qiskit kodu” = this circuit’s Qiskit code, “Geri al” = undo, “Temizle” = clear. Click a gate in the circuit to remove it.

Key points

The classical repetition code corrects single bit flips by majority vote: logical error 3p² − 2p³.
In the quantum case entanglement replaces copying: a|0⟩ + b|1⟩ → a|000⟩ + b|111⟩.
The syndrome measures only parities, not the data, and shows where the error is.
The repetition code does not correct phase flips and cannot cope with two errors.

Test yourself

Why does the syndrome measurement in the quantum repetition code not destroy the superposition?

Because it measures only whether the qubits are equal (their parity), not the data itself
Because the measurement is very fast
Because the encoded state has been copied

Show the answer

Because it measures only whether the qubits are equal (their parity), not the data itself. The parities q0 ⊕ q1 and q1 ⊕ q2 do not depend on a and b for a|000⟩ + b|111⟩, so the measurement learns nothing about a and b.

← Noise and kinds of errors: why do qubits go wrong? · The phase-flip code and Shor’s nine-qubit code →