path: root/source/know/concept/repetition-code/index.md

---
title: "Repetition code"
sort_title: "Repetition code"
date: 2021-05-07
categories:
- Quantum information
layout: "concept"
---

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

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

If a single-bit error occurs, e.g. $$000 \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}$$:

$$\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:

$$\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:

$$\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* $$\Ket{0}$$ (written $$\ket{\overline{0}}$$)
is represented by 3 *physical* qubits, and vice versa:

$$\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](/know/concept/quantum-gate/):

<a href="bit-flip-encode.png">
<img src="bit-flip-encode.png" style="width:32%">
</a>

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

$$\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 = Z_1 \otimes Z_2 \otimes I_3$$,
where $$I$$ is identity and $$Z$$ is the Pauli-$$Z$$ gate.
The 3-qubit basis states are its eigenvectors:

$$\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 $$ZZI$$ for $$\ket{\overline{\psi}}$$,
and if the eigenvalue is $$-1$$,
we know that a bit flip has occurred,
whereas if the eigenvalue is $$+1$$,
there is *maybe* no error ($$\Ket{001}$$ and $$\Ket{110}$$ are false negatives).

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

$$\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 $$\Ket{100}$$ and $$\Ket{011}$$ are false negatives.
In other words, $$IZZ$$ cannot detect if the 1st qubit was flipped,
while $$ZZI$$ cannot protect the 3rd qubit.
But by using both, we know exactly which qubit was flipped
thanks to the eigenvalues:

<table style="width:30%;margin:auto;text-align:center;">
    <tr>
        <th>Error</th>
        <th>$$ZZI$$</th>
        <th>$$IZZ$$</th>
    </tr>
    <tr>
        <td>$$I$$</td>
        <td>$$+1$$</td>
        <td>$$+1$$</td>
    </tr>
    <tr>
        <td>$$X_1$$</td>
        <td>$$-1$$</td>
        <td>$$+1$$</td>
    </tr>
    <tr>
        <td>$$X_2$$</td>
        <td>$$-1$$</td>
        <td>$$-1$$</td>
    </tr>
    <tr>
        <td>$$X_1$$</td>
        <td>$$+1$$</td>
        <td>$$-1$$</td>
    </tr>
</table>

Where e.g. $$X_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 $$ZZI$$ and $$IZZ$$
without affecting $$\ket{\overline{\psi}}$$ itself,
by applying $$\mathrm{CNOT}$$s to some ancillary qubits
and then measuring those:

<a href="bit-flip-detect.png">
<img src="bit-flip-detect.png" style="width:62%">
</a>

The two measurements, respectively representing $$ZZI$$ and $$IZZ$$,
yield $$\Ket{1}$$ if a bit flip definitely occurred,
and $$\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**:

$$\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 $$X$$-axis intead of the $$Z$$-axis:

$$\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:

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

<a href="phase-flip-encode.png">
<img src="phase-flip-encode.png" style="width:40%">
</a>

A phase flip along the $$Z$$-axis
corresponds to a bit flip along the $$X$$-axis $$\Ket{+} \to \Ket{-}$$.
In this case, the stabilizers are $$XXI$$ and $$IXX$$,
and the error detection circuit is as follows:

<a href="phase-flip-detect.png">
<img src="phase-flip-detect.png" style="width:70%">
</a>

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:

$$\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:

$$\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:

<a href="shor-code-encode.png">
<img src="shor-code-encode.png" style="width:55%">
</a>

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

The bit flip stabilizers $$ZZI$$ and $$IZZ$$
are applied on a per-block basis, like so:

$$\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 $$XXI$$ and $$IXX$$
are applied to entire blocks at once:

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



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