# Quantum repetition code for bit-flips#

We are now in a position to introduce quantum codes. Our goal is to understand how a set of qubits transmitted through a noisy channel can be protected from any errors they experience. The process is similar to classical codes in that we will take the state of $k$ qubits and encode it into the state of $n$ qubits. However, our task will be complicated by the fact that the operations on qubits are not just bit-flips but any possible interaction with the environment, such as phase-flips or more general rotations. Fortunately, we will discover that this possibility of infinite types of errors will not be too large a hindrance and we can construct good codes.

## Setup#

Suppose that Alice has a quantum transmission channel to Bob that is noisy. Let's assume for starters that the noisy channel applies, with probability $p$, the quantum bit-flip operator $X$ to each qubits that pass through it. We will dicuss channels with different errors later on.

Alice wants to transmit to Bob the quantum one-qubit state $\ket{\psi} = \alpha\ket{0} + \beta\ket{1}$. If she sends the state as is, there is a probability $(1-p)$ that Bob receives the state $\ket{\psi}$ and probability $p$ that Bob receives the state $\ket{\tilde\psi} = X\ket{\psi} = \beta\ket{0} + \alpha\ket{1}$. Moreover, Bob has no way of knowing whether an error occured or not.

To magnify the chances of successful communication, Alice and Bob can employ a code very similar to the classical repetition code.

## Encoding#

In the quantum version of the repetition code, Alice takes the unencoded qubit and encodes it into the state of three qubits in a repetitive manner. This is best seen by first noting the transformation on the basis states, \begin{align} \ket{0} \to \ket{\bar{0}} = \ket{000}, \\ \ket{1} \to \ket{\bar{1}} = \ket{111}. \end{align} Then, we can realize that the qubit in state $\ket{\psi}$ is encoded as $$\ket{\psi}\ket{00} = (\alpha\ket{0} + \beta\ket{1})\ket{00} \to \ket{\bar\psi} = \alpha\ket{000} + \beta\ket{111},$$ where the $\ket{00}$ are ancilla qubits.

We will call the original qubit the unencoded logical qubit, the three qubits the physical qubits, and their combined state $\ket{\bar\psi}$ the encoded logical qubit.

The encoding transformation can be done using the quantum circuit, which takes the unencoded logical qubit and two ancillas in state $\ket{\psi}\ket{00}$, to the encoded logical qubit in state $\ket{\bar\psi}$.

import stac
enc_circ = stac.Circuit()
enc_circ.append('CX', 0, 1)
enc_circ.append('CX', 0, 2)
enc_circ.draw()

Determine the encoding of the $\ket{+}$ state and $\ket{-}$ state.

Determine logical gate operations $\bar{X}$ and $\bar{Z}$ for the three-qubit repetition code. These are operations that act on the logical basis $\set{\ket{\bar{0}}, \ket{\bar{1}}}$, in the normal way, i.e. \begin{align} \bar{X}\ket{\bar{0}} &= \ket{\bar{1}}, \quad \bar{X}\ket{\bar{1}} = \ket{\bar{0}}, \\ \bar{Z}\ket{\bar{0}} &= \ket{\bar{0}}, \quad \bar{Z}\ket{\bar{1}} = -\ket{\bar{1}}. \end{align} They can be constructed by some combination of operations on the three physical qubits. You will discover that there are possibly multiple ways of doing so.

### Errors on the state#

Alice sends the three physical qubits through the noisy channel. Each of them will have probability $p$ of being flipped. If the second qubit is flipped, then Bob receives the state $X_2\ket{\bar\psi} = \ket{\tilde\psi} = \alpha\ket{010} + \beta\ket{101}$. In total there, are eight possiblities for the error, with the probabilities similar to the classical case.

Error Probability
$I$ $(1-p)^3$
$X_0$ $p(1-p)^2$
$X_1$ $p(1-p)^2$
$X_2$ $p(1-p)^2$
$X_0X_1$ $?$
$X_0X_2$ $?$
$X_1X_2$ $?$
$X_0X_1X_2$ $p^3$

Question: Fill the ? in the table above.

Determine the impact of each error on the input basis states.

Let input state be $\ket{000}$

Error Output state
$I$ $\ket{000}$
$X_0$ $\ket{100}$
$X_1$ $?$
$X_2$ $?$
$X_0X_1$ $?$
$X_0X_2$ $?$
$X_1X_2$ $?$
$X_0X_1X_2$ $?$

Let input state be $\ket{111}$

Error Output state
$I$ $\ket{111}$
$X_0$ $\ket{011}$
$X_1$ $?$
$X_2$ $?$
$X_0X_1$ $?$
$X_0X_2$ $?$
$X_1X_2$ $?$
$X_0X_1X_2$ $?$

Do different errors result in the same output state?

As in the classical case, the code can only correctly recover the state if only zero or one error occurs and fails otherwise. Simiarly, as in the classical case, if $p$ is sufficiently small, then two or three errors are very unlikely to occur.

## Decoding#

There are three parts to decoding

1. Identifying which error has occured.
2. Correcting the corrupted codeword.
3. Turning the corrected codeword back into message (this part is also called decoding).

### Detecting the error#

Assuming that only errors from the set $\st{E} = \set{I,X_1,X_2,X_3}$ occur, Bob has to (a) identify which of these errors has occurred and (b) then correct for it. His task is more difficult than in the classical case because he can't measure the received state as this would destroy the superposition, and he would gain very little information about $\alpha$ and $\beta$ which is what Alice is really trying to transmit to Bob.

Instead the correct strategy for Bob to pursue is to do a partial measurement that only determines whether one of the qubits is different from the other two. This is the replacement of the majority voting algorithm in the classical case, but quite similar. This type of measurement does not probe the value of $\alpha$ or $\beta$ and therefore the superposition is maintained. Specifically Bob compares the value of the first two qubits, and compares the value of the last two qubits. If there is a difference, then he will know which error occured. The following circuit accomplishes this task, in which two ancilla qubits are required.

synd_circ = stac.Circuit()
synd_circ.append('CX', 0, 3)
synd_circ.append('CX', 1, 3)
synd_circ.append('TICK')
synd_circ.append('CX', 1, 4)
synd_circ.append('CX', 2, 4)
synd_circ.append('TICK')
synd_circ.append('M', 3)
synd_circ.append('M', 4)
synd_circ.draw()

This circuit has three parts. In the first part, the values of the first and second qubits are added to the first ancilla qubit. This is done by $CX$ gates, which if you recall, in the computational basis, add the value of the control qubit to the target qubit, $$CX_{01}\ket{a}\ket{b} = \ket{a}\ket{a \oplus b}.$$

If the first two qubits have the same value, then either none of the $CX$ gates will trigger or both will, and so the value of the ancilla will not change. This can be seen from the calculation, \begin{align} CX_{03}CX_{13} (\alpha\ket{000} + \beta\ket{111})\ket{00} &= \alpha CX_{03}CX_{13}\ket{000}\ket{00} + \beta CX_{03}CX_{13}\ket{111}\ket{00}, \\ &= \alpha \ket{000}\ket{00} + \beta \ket{111}\ket{0+1+1,0}, \\ &= \alpha \ket{000}\ket{00} + \beta \ket{111}\ket{00}. \end{align} Here, the $CX$ gates don't trigger for the first term in the superposition, but do trigger for the second term, which we have made explicit.

If the first two qubits are different, then only one of the $CX$ gates will trigger. For instance, \begin{align} CX_{14}CX_{24}(\alpha\ket{010} + \beta\ket{101})\ket{00} &= \alpha CX_{14}CX_{24}\ket{010}\ket{00} + \beta CX_{14}CX_{24}\ket{101}\ket{00}, \\ &= \alpha \ket{010}\ket{0+1,0} + \beta \ket{101}\ket{0+1,0}, \\ &= \alpha \ket{010}\ket{10} + \beta \ket{101}\ket{10}. \end{align} Hence, the value of the ancilla has flipped.

The same story plays out for the second part of the circuit except for the second and third qubits. Subsequently, the two ancilla are measured. The measurement results are called the syndrome, and they contain information, which can be used to infer which error has occured. This is summarized in the following table. | Syndrome | Inferred error | |:---------:|:--------------:| | $00$ | $I$ | | $01$ | $X_3$ | | $10$ | $X_1$ | | $11$ | $X_2$ |

We say inferred error, because this is the error Bob assumes, but there is small chance of a two or three qubit error, so there is difference between the actual error and the inferred error.

Question: Above, we have shown how row 1 and row 4 of the table are obtained. Work out the other two rows by hand.

### Correcting the error#

Once, Bob has inferred an error, he can fix the corrupted codeword by applying the inverse of the error. In this case, the error operators are self-inverse, so he just has to apply them again to fix the corrupted codeword, eg. if he thinks error $X_1$ has occured, he applied $X_1$ to the corrupted state to fix it.

### Decoding#

Finally, Bob can undo the encoding operation to recover the one-qubit state Alice meant to send. Since, the encoding operation was self-inverse, Bob just has to pass $\ket{\bar\psi}$ through it to recover $\ket{\psi}$.

### A note on probability of success#

We don't have to repeat our analysis of the probability of success as it is exactly the same as in the classical case.

Question: Consider the 5-qubit repetition code, in which the coding operates in a similar fashion as the 3-qubit one we have discussed, but with five qubits instead of three. Can this larger code possibly correct errors in which two qubits are flipped?

## A linear algebraic analysis of the quantum repetition code (optional)#

One way of understanding why the code works is by understanding the vector spaces we have dealt with above.

First, there was the $2$-dimensional Hilbert space of the unencoded logical qubit. This was mapped to a $2$-dimensional subspace of the $2^3$-dimensional Hilbert space of the three physical qubits, the latter of which is called the codespace, and the former the quantum code. Errors move the encoded state into other $2$-dimensional subspaces of the codespace. For instance, the quantum code had a basis $\set{\ket{000},\ket{111}}$. The error $X_2$ moved the state to a subspace with basis $\set{\ket{010},\ket{101}}$. We can tabulate all these movements as follows.

Error Subspace basis
$I$ $\set{\ket{000},\ket{111}}$
$X_1$ $\set{\ket{100},\ket{011}}$
$X_2$ $\set{\ket{010},\ket{101}}$
$X_3$ $\set{\ket{001},\ket{110}}$

From this analysis we can see why the code works to correct bit-flip errors. Each error doesn't fundamentally destroy the state, it only moves it to a different subspace. The process of error-detection is to determine which subspace we are in, which does not distort the actual state. The process of error-correction moves us back to the original quantum code subspace. We will use this notion of subspaces again when we formally define quantum error-correction.

Question: Recall that a vector subspace is characterized by a projector $\Pi = \sum_i \ket{\psi_i}\bra{\psi_i}$, where $\set{\ket{\psi_i}}_i$ is a basis for the subspace. Show that $\Pi^2 = \Pi$.

Question: Determine the projector onto the code for the three-qubit code.

### Correcting $X$ rotation errors#

The code we have created can correct errors besides simple $X$ errors. The unitary, $$R_x^{(i)}(\theta) = \cos\theta I - \iu \sin\theta X^{(i)},$$ is the rotation about the $X$ axis on the Bloch sphere for the $i$-th qubit. Suppose, the encoded state $\ket{\bar\psi}$ is effected by this unitary during its passage through the communication channel between Alice and Bob. We now show that the error detection and correction procedures we have described above deal with this error, and Bob has to do nothing extra to correct for such an error.

To see this we calculate the corrupted codeword state, $$\ket{\tilde\psi} = R_x^{(i)}(\theta)\ket{\bar\psi} = \cos\theta\ket{\bar\psi} - \iu \sin\theta X^{(i)}\ket{\bar\psi}.$$ When, we run this state through the error-detection circuit (in which we append two ancillas to the state), we obtain before the measurement step, the state \begin{align} (\cos\theta\ket{\bar\psi} - \iu \sin\theta X^{(i)}\ket{\bar\psi})\ket{00} \to \cos\theta\ket{\bar\psi}\ket{00} - \iu \sin\theta X^{(i)}\ket{\bar\psi}\ket{s}, \end{align} where $\ket{s}$ is the syndrome associated with $X^{(i)}$. When we measure the ancilla, either the measurement result is $00$ (with probability $|\cos\theta|^2$) and the corrupted codeword state collapses to $\ket{\bar\psi}$, or the measurement result is $s$ (with probability $|\sin\theta|^2$) and the corrupted codeword state collapses to $X^{(i)}\ket{\bar\psi}$. In either case, the subsequent error-correction procedure will correct the state.

What we see here is that linearity of quantum mechanics and the collapse mechanism on measurement allows us to correct errors which are a linear combination of errors in $E$. This is an incredibly powerful result, and we will prove it more generally later on.

### Phase-flip errors#

Quantum bit-flip errors are only one kind of errors. quantum systems in interacting with the environment can suffer from other types of error. One such possibility is phase-flip errors, i.e. where the qubits can be acted upon by the $Z$ operator. This code fails to identify phase-flip errors and therefore cannot correct them either.

To see this note that the action of, say, $Z_1$ on the logical state is $$Z_1\ket{\bar\psi} = Z_1(\alpha\ket{000} + \beta\ket{111}) = \alpha\ket{000} - \beta\ket{111}.$$ This state is identical to a different state Alice might have sent, so there is no way that Bob can determine that an error has occured. In the subspace picture discussed above single-qubit $Z$ errors keep the state within the code. This makes it impossible, both here and generally, for the error to be detected. A well-designed code ensures that every possible error moves the state out of the code and into some other subspace of the codespace.