Quantum codes from classical
We would like to use the insights gained from our study of classical codes to help us build quantum codes.
Let’s start with a classical [n,k,d] code (such as the Hamming [7,4,3]), with parity-check matrix H and generator G.
Each row r of H is a binary string x_r=x_{r,1}x_{r,2}\ldots x_{r,n}, where x_{i,j} is the (i,j)-th element of H.
For 1\leqslant r\leqslant n, we define a stabiliser generator
G_r
\coloneqq X_{x_r}
\coloneqq \otimes_{j=1}^n X^{x_{r,j}}.
For example, in the case of the Hamming [7,4,3] code, we have
H
= \begin{bmatrix}
\begin{array}{cccc|ccc}
1 & 1 & 0 & 1 & 1 & 0 & 0
\\1 & 0 & 1 & 1 & 0 & 1 & 0
\\0 & 1 & 1 & 1 & 0 & 0 & 1
\end{array}
\end{bmatrix}.
so the three rows define three generators
\begin{aligned}
G_1
&= X_{1101100}
= XX\mathbf{1}XX\mathbf{1}\mathbf{1}
\\G_2
&= X_{1011010}
= X\mathbf{1}XX\mathbf{1}X\mathbf{1}
\\G_3
&= X_{0111001}
= \mathbf{1}XXX\mathbf{1}\mathbf{1}X.
\end{aligned}
Now consider a state |\psi\rangle that is stabilised by these generators, i.e. such that
G_r|\psi\rangle
= |\psi\rangle.
What happens if a Z error occurs on a particular qubit: what measurement results do we get when we measure the stabilisers?
Well, writing Z_j to mean a Z error on the j-th qubit, as usual,
\begin{aligned}
G_r Z_j|\psi\rangle
&= (-1)^{x_{r,j}} G_r|\psi\rangle
\\&= (-1)^{x_{r,j}} |\psi\rangle.
\end{aligned}
So the measurement outcome directly corresponds to the (r,j)-th entry x_{r,j} of the parity check matrix.
Generally, if this Z_j error occurs, then measuring for all rows r will give measurement outcomes that directly correspond to the j-th column of the parity check matrix.
This is just the same lookup table as in the classical case: this codespace is a distance d error correcting code for single Z errors.
Using the Hamming [7,4,3] code as an example again, we get the following table of error syndromes, where we write \pm to mean \pm1:
| none |
+ |
+ |
+ |
| Z_1 |
- |
- |
+ |
| Z_2 |
- |
+ |
- |
| Z_3 |
+ |
- |
- |
| Z_4 |
- |
- |
- |
| Z_5 |
- |
+ |
+ |
| Z_6 |
+ |
- |
+ |
| Z_7 |
+ |
+ |
- |
So if we measure the three stabilisers and get the measurement sequence (-1,1,1) then the corresponding bit string (1,0,0) in the Hamming [7,4,3] code tells us that there was an error on p_1, i.e. a Z_5 error.
We have used a classical code to help us correct for Z errors in the quantum case.
If we take a second classical code, with parameters [n,k',d'] and parity-check matrix H', and use it to define Z-type stabilisers G'_r=Z_{x_r} then we will have a distance d' protection against X errors.
However, we cannot simply pick the two classical codes arbitrary: if the scheme is the work, then the X-type and Z-type stabilisers must actually be stabilisers, i.e. they must commute.
The challenge in creating quantum error-correction codes often lies in finding good commuting sets of stabilisers.
How can we tell if this happens?
Well, if x is a row of H, and z a row of H', then the we need the number of positions i\in\{1,\ldots,n\} such that x_i=z_i=1 to be even, as these are the ones that will give operators that individually anticommute (XZ=-ZX).
In notation, this is the same as asking that
x\cdot z
\equiv 0\ \mathrm{mod}\ 2.
This is the same as saying that z, which is a row of H', must be a codeword of the first code: by definition of the parity-check matrix H, we need that Hz=0.
Applying this reasoning to all rows z, we see that we need
H\cdot {H'}^T
= 0
or, in other words,
\operatorname{range}({H'}^T)
\subseteq\ker(H).
But we know that \operatorname{range}(G)=\ker(H), and so this is equivalent to asking for
\operatorname{range}({H'}^T)
\subseteq\operatorname{range}(G).
We can figure out some key properties of combining an [n,k,d] code (G,H) for X-stabilisers and an [n,k',d'] code (G',H') for Z-stabilisers without too much difficult.
Since our first code encodes k bits, the generator G has k rows, and the parity-check matrix H has n-k rows.
Thus there are n-k of the X-type generators, and n-k' of the Z-type generators; in total there are 2n-(k+k') generators.
Since each generator halves the dimension, the dimension of the Hilbert space defined by the stabilisers is
2^{n-2n+k+k'}
= 2^{k+k'-n}
i.e. it encodes k+k'-n qubits.
The combined code has a distance k against Z errors, and k' against X errors; since the two types of errors are correctly independently, the total distance is simply \min(d,d').
In summary then, we have created an
[[n, k+k'-n, \min(d,d')]]
quantum error-correction code, and its decoding is well understood based on the classical decoding methods applied independently for X errors and Z errors.
This general construction of quantum error correcting codes is known as the CSS construction, for its originators Robert Calderbank, Peter Shor, and Andrew Steane.
Given an [n,k_1,d_1] code C_1=(G_1,H_1) and an [n,k_2,d_2] code C_2=(G_2,H_2) such that \operatorname{range}(H_2^T)\subseteq\operatorname{range}(G_1), the CSS code \operatorname{CSS}(C_1,C_2) constructed as above is an [[n,k_1+k_2-n,\min(d_1,d_2)]] code.
As always, one needs to be careful of conventions.
Many sources define a code to be the codespace \operatorname{range}{G} itself instead of the pair (G,H), and usually also replace C_2 with {C_2}^\perp in the statement of the CSS construction.
Before moving on, let’s look at the remaining details of applying the CSS construction to the Hamming [7,4,3] code.
Let C_1=C_2=(G,H) be the Hamming [7,4,3] code with G and H as in Section 14.1.
To apply the CSS construction, we need to check that \operatorname{range}(H_2^T)\subseteq\operatorname{range}(G_1).
Since C_1=C_2, this is simply asking that the Hamming [7,4,3] code be weakly self-dual, i.e. that
\operatorname{range}(H^T)
\subseteq\operatorname{range}(G)
which can be checked to be true by hand.
This means that we can use the Hamming [7,4,3] code to define both our X-type and Z-type generators: using the notation of Section 7.2, the group of generators is generated by
\begin{array}{c|ccccccc|}
+ & X & X & \mathbf{1}& X & X & \mathbf{1}& \mathbf{1}
\\+ & X & \mathbf{1}& X & X & \mathbf{1}& X & \mathbf{1}
\\+ & \mathbf{1}& X & X & X & \mathbf{1}& \mathbf{1}& X
\\+ & Z & Z & \mathbf{1}& Z & Z & \mathbf{1}& \mathbf{1}
\\+ & Z & \mathbf{1}& Z & Z & \mathbf{1}& Z & \mathbf{1}
\\+ & \mathbf{1}& Z & Z & Z & \mathbf{1}& \mathbf{1}& Z
\end{array}
The result is a [[7,1,3]] code, generally attributed to and thus known as the Steane code, or simply the seven-qubit code, that encodes one logical qubit across seven physical ones, and that is able to correct for any single-qubit Pauli error.
We can visualise the Steane code using its Tanner graph, as in Figure 14.4, but we will return to a proper in-depth study of this code in Section 14.9.
Not all quantum codes arise from combining classical ones like this, and even for those that do, working with the generator and parity-check matrices can often be cumbersome.
Indeed, a truly quantum code will not have a single one of each, since this is not sufficient to deal with the purely quantum phenomena of superposition.
For example, as the Tanner graph in Figure 14.4 shows, we have two parity check matrices in the case of CSS codes.
When working with truly quantum codes, the stabiliser formalism really becomes much more useful — our next aim is to justify this with some examples and explanation.
![The Tanner graph of the Steane code. You can think of this graph as taking two copies of the Hamming [7,4,3] code Tanner graph and gluing them together at all of the data nodes. For any CSS code there are two types of “parity checks”: one for detecting X errors (solid lines), and one for Z errors (dashed lines).](qubit_guide_files/figure-html/tanner-graph-713-1.png)