Categories: Quantum information.

Repetition code

A repetition code is a simple approach to error correction: to protect a bit xx, make two copies:

00001111\begin{aligned} 0 \to 000 \qquad \quad 1 \to 111 \end{aligned}

If a single-bit error occurs, e.g. 000100000 \to 100, a majority vote resets the minority bit. Clearly, this does not protect against multi-bit errors, but that is usually not necessary.

In quantum computing, where error correction is much more important, repetition codes can also be used, albeit with some complications, as discussed below.

Bit flip code

Suppose that we want to detect errors in the following arbitrary qubit state ψ\Ket{\psi}:

ψ=α0+β1\begin{aligned} \Ket{\psi} = \alpha \Ket{0} + \beta \Ket{1} \end{aligned}

For now, let us limit ourselves to detecting bit flips, where α\alpha and β\beta get switched:

α0+β1Errorβ0 ⁣+ ⁣α1\begin{aligned} \alpha \Ket{0} + \beta \Ket{1} \quad \to \boxed{\mathrm{Error}} \to \quad \beta \Ket{0} \!+\! \alpha \Ket{1} \end{aligned}

One way to defend against this is the quantum version of a classical repetition code:

ψEncoderψ=α000+β111\begin{aligned} \Ket{\psi} \quad \to \boxed{\mathrm{Encoder}} \to \quad \ket{\overline{\psi}} = \alpha \Ket{000} + \beta \Ket{111} \end{aligned}

In other words, a logical 0\Ket{0} (written 0\ket{\overline{0}}) is represented by 3 physical qubits, and vice versa:

00=00011=111\begin{aligned} \boxed{ \Ket{0} \to \ket{\overline{0}} = \Ket{000} \qquad \quad \Ket{1} \to \ket{\overline{1}} = \Ket{111} } \end{aligned}

Such a transformation is easy to achieve with the following sequence of quantum gates:

Bit flip code encoder

So, a little while after encoding the state ψ\Ket{\psi} like that, a bit flip occurs on the 2nd qubit:

ψErrorα010+β101\begin{aligned} \ket{\overline{\psi}} \quad \to \boxed{\mathrm{Error}} \to \quad \alpha \Ket{010} + \beta \Ket{101} \end{aligned}

But now there is a problem: how do we detect this error? We could measure the state, but that would make it collapse, which is probably not what we want.

The trick is to use operators called stabilizers, in this case for example ZZI=Z1Z2I3ZZI = Z_1 \otimes Z_2 \otimes I_3, where II is identity and ZZ is the Pauli-ZZ gate. The 3-qubit basis states are its eigenvectors:

ZZI000=+000ZZI001=+001ZZI010=010ZZI011=011ZZI100=100ZZI101=101ZZI110=+110ZZI111=+111\begin{alignedat}{2} ZZI \Ket{000} &= + \Ket{000} \qquad ZZI \Ket{001} &&= + \Ket{001} \\ ZZI \Ket{010} &= - \Ket{010} \qquad ZZI \Ket{011} &&= - \Ket{011} \\ ZZI \Ket{100} &= - \Ket{100} \qquad ZZI \Ket{101} &&= - \Ket{101} \\ ZZI \Ket{110} &= + \Ket{110} \qquad ZZI \Ket{111} &&= + \Ket{111} \end{alignedat}

We could measure ZZIZZI for ψ\ket{\overline{\psi}}, and if the eigenvalue is 1-1, we know that a bit flip has occurred, whereas if the eigenvalue is +1+1, there is maybe no error (001\Ket{001} and 110\Ket{110} are false negatives).

These false negatives are fixed by including another stabilizer IZZIZZ, with these eigenvectors:

IZZ000=+000IZZ001=001IZZ010=010IZZ011=+011IZZ100=+100IZZ101=101IZZ110=110IZZ111=+111\begin{alignedat}{2} IZZ \Ket{000} &= + \Ket{000} \qquad IZZ \Ket{001} &&= - \Ket{001} \\ IZZ \Ket{010} &= - \Ket{010} \qquad IZZ \Ket{011} &&= + \Ket{011} \\ IZZ \Ket{100} &= + \Ket{100} \qquad IZZ \Ket{101} &&= - \Ket{101} \\ IZZ \Ket{110} &= - \Ket{110} \qquad IZZ \Ket{111} &&= + \Ket{111} \end{alignedat}

In which case 100\Ket{100} and 011\Ket{011} are false negatives. In other words, IZZIZZ cannot detect if the 1st qubit was flipped, while ZZIZZI cannot protect the 3rd qubit. But by using both, we know exactly which qubit was flipped thanks to the eigenvalues:

II +1+1 +1+1
X1X_1 1-1 +1+1
X2X_2 1-1 1-1
X1X_1 +1+1 1-1

Where e.g. X3X_3 denotes that the 3rd qubit was flipped. The measurement outcomes on the last three rows are called error syndromes, and are obtained by a syndrome measurement.

Fortunately, we can measure ZZIZZI and IZZIZZ without affecting ψ\ket{\overline{\psi}} itself, by applying CNOT\mathrm{CNOT}s to some ancillary qubits and then measuring those:

Bit flip code decoder

The two measurements, respectively representing ZZIZZI and IZZIZZ, yield 1\Ket{1} if a bit flip definitely occurred, and 0\Ket{0} otherwise. There is no entanglement, so the input is untouched.

Phase flip code

The above system protects us against all single-qubit bit flips. Unfortunately, that is not enough: qubits can also experience a phase flip:

α0+β1Errorα0β1\begin{aligned} \alpha \Ket{0} + \beta \Ket{1} \quad \to \boxed{\mathrm{Error}} \to \quad \alpha \Ket{0} - \beta \Ket{1} \end{aligned}

How to detect that? If we want to protect against phase flips instead of bit flips, we can simply do the same as before, but along the XX-axis intead of the ZZ-axis:

00=+ ⁣+ ⁣+11= ⁣ ⁣\begin{aligned} \boxed{ \Ket{0} \to \ket{\overline{0}} = \Ket{+\!+\!+} \qquad \quad \Ket{1} \to \ket{\overline{1}} = \Ket{-\!-\!-} } \end{aligned}

Such that an arbitrary state ψ\Ket{\psi} is encoded as follows, by the circuit shown below:

ψEncoderψ=α+ ⁣+ ⁣++β ⁣ ⁣\begin{aligned} \Ket{\psi} \quad \to \boxed{\mathrm{Encoder}} \to \quad \ket{\overline{\psi}} = \alpha \Ket{+\!+\!+} + \beta \Ket{-\!-\!-} \end{aligned}

Phase flip code encoder

A phase flip along the ZZ-axis corresponds to a bit flip along the XX-axis +\Ket{+} \to \Ket{-}. In this case, the stabilizers are XXIXXI and IXXIXX, and the error detection circuit is as follows:

Phase flip code decoder

This system protects us against all single-qubit phase flips, but not against bit flips.

Shor code

What kind of repetition code would we need if we want to detect both bit flips and phase flips? The most straightforward option is the Shor code. Starting from a phase flip encoding:

00=+ ⁣+ ⁣+=(0+12)311= ⁣ ⁣=(012)3\begin{aligned} \Ket{0} \to \ket{\overline{0}} &= \Ket{+\!+\!+} = \bigg( \frac{\Ket{0} + \Ket{1}}{\sqrt{2}} \bigg)^{\otimes 3} \\ \Ket{1} \to \ket{\overline{1}} &= \Ket{-\!-\!-} = \bigg( \frac{\Ket{0} - \Ket{1}}{\sqrt{2}} \bigg)^{\otimes 3} \end{aligned}

We add protection against bit flips by using a repetition code for each physical qubit:

0=(000+1112)31=(0001112)3\begin{aligned} \boxed{ \ket{\overline{0}} = \bigg( \frac{\Ket{000} + \Ket{111}}{\sqrt{2}} \bigg)^{\otimes 3} \qquad \quad \ket{\overline{1}} = \bigg( \frac{\Ket{000} - \Ket{111}}{\sqrt{2}} \bigg)^{\otimes 3} } \end{aligned}

This encoding is achieved by the following quantum circuit, which simply consists of the phase flip encoder, followed by 3 copies of the bit flip encoder:

Shor code encoder

We thus use 9 physical qubits to store 1 logical qubit. Fortunately, more efficient schemes exist.

The bit flip stabilizers ZZIZZI and IZZIZZ are applied on a per-block basis, like so:

ZZIIIIIIIIIIZZIIIIIIIIIIZZIIZZIIIIIIIIIIZZIIIIIIIIIIZZ\begin{aligned} ZZI \: III \: III \qquad\quad III \: ZZI \: III \qquad\quad III \: III \: ZZI \\ IZZ \: III \: III \qquad\quad III \: IZZ \: III \qquad\quad III \: III \: IZZ \end{aligned}

Whereas the phase flip stabilizers XXIXXI and IXXIXX are applied to entire blocks at once:

XXXXXXIIIIIIXXXXXX\begin{aligned} XXX \: XXX \: III \qquad \quad III \: XXX \: XXX \end{aligned}


  1. J.S. Neergaard-Nielsen, Quantum information: lectures notes, 2021, unpublished.
  2. S. Aaronson, Introduction to quantum information science: lecture notes, 2018, unpublished.