A quantum error-correcting code is a carefully chosen subspace C of the Hilbert space of the computer such that single-qubit errors (and perhaps errors on multiple qubits) acting on any state in C will produce distinguishable states. For instance, suppose E is some operator, such as a single bit flip. If E |psi> is orthogonal to |psi> for any |psi> in C, then we can always make some measurement which will tell us if current state has the form |psi> or the form E |psi>. This measurement will therefore tell us whether or not the error E has occurred.
In order to be able to correct the state, we actually need to not only distiguish error E from no error, but also from any other error F. Otherwise, we might try to correct error E when actually error F occurred, and now we have two errors instead of one. We can formalize this in a sufficient condition for an error-correcting code:
< i | EF | j > = 0.
If this condition is satisfied for all possible distinct errors E and F and all basis states |i> and |j> (also i equal to j) for C, then C is an error-correcting code. The possibilities for E and F should include the identity (no error).
One way to ensure that this condition is true is to pick C so that it lies in the +1-eigenspace of some operator M. Then if EF anticommutes with M, EF will take states from the +1-eigenspace of M to the -1-eigenspace of M, which is orthogonal to the +1-eigenspace:
< i | EF | j > = < i | EF M | j >
= - < i | M EF | j >
= - < i | EF | j > = 0.
It is convenient to pick M to be the tensor product of Pauli spin matrices, because then other products of Pauli matrices will always either commute or anticommute with M. By choosing C to be in the +1-eigenspace of enough M's, we can make sure that EF will anticommute with one of the M's for any pair of E and F.
We are not completely free to choose the M's however we like. We want C to be in the +1-eigenspace of all the M's. For this to be possible, the M's must commute with each other. In addition, if C is in the +1-eigenspace of M1 and M2, then it is also in the +1-eigenspace of M1 M2. Therefore, the set S of tensor products of Pauli matrices for which C is in the +1-eigenspace is an Abelian group. In fact, it will always have order 2n-k, where n is the number of qubits in the full Hilbert space and k is the number of qubits encoded by C. S is called the stabilizer of the code.
Not all codes can be described by a stabilizer. However, the vast majority of known quantum codes can be. In addition, stabilizer codes have more structure than non-stabilizer codes, which makes them easier to find and easier to work with than non-stabilizer codes. For instance, to figure out what error has occurred, we only have to measure the n-k generators of the stabilizer and do some classical processing. Stabilizer codes are related to classical codes over the finite field GF(4), so many classical results can be directly applied to them. Also, any stabilizer code can be used to perform fault-tolerant computation.
As I final example, below I give the generators for the stabilizer of the five-qubit code. This is the smallest possible quantum code to correct one general error.
| X | Z | Z | X | I |
| I | X | Z | Z | X |
| X | I | X | Z | Z |
| Z | X | I | X | Z |
You can check for yourself that any two-qubit product of Pauli matrices will anticommute with at least one of these four operators.
Back to Daniel Gottesman's home page
July 24, 1998