Quantum error-correcting codes

Lectures by Harriet Pollatsek and Keldon Drudge Notes by Peter Cameron

Draft, December 1998

Abstract These notes are a record of proceedings in the QMW Combinatorics Study Group in November and December 1998. Since we are discrete mathematicians and know little quantum theory, the notes are not strong on the physics background (but we give references to several sources for this). We have tried to compare quantum with classical error correction where possible, and to provide enough information to see what are the workpoints for discrete mathematicians in this area.

1 Background

An exciting recent development on the border of computer science and physics has been the realisation that some important problems can be solved much more efficiently on a quantum computer than on a classical computer. Most notably, Shor [16] gave a randomised algorithm for factorising an integer in polynomial time on a quantum computer. Since factorisation of large integers is the hard problem which underpins public-key encryption systems such as RSA [14, 19], the importance of this result is obvious, and a large amount of research into the possibility of building a quantum computer is going on. (We discuss this in the Appendix.) The efficiency of a quantum computer derives from the fact that a quantum state is the superposition of a number of pure states, all of which evolve according to the laws of physics (the Schrödinger equation); in effect, a quantum computer is highly parallel.

Various schemes for a quantum computer have been proposed. The limitation derives from the fact that a bit of information is stored by a single atom or electron, instead of the large numbers of electrons used in a conventional transistor. Thus, a small nudge from the environment is sufficient to cause decoherence and upset the computation. The most promising way around this problem at present seems to be to build a fault-tolerant computer, by designing quantum error-correction into the computer to preserve the coherence of the data and the integrity of the computation. We hope to explain how error-correction could be done.

2 Bits and qubits

Classically, a single bit of information can take either the value 0 or 1, which we regard as lying in the set ℤ_{2}. By contrast, a quantum state can be a superposition, or linear combination, of these two opposite states, with complex coefficients. Accordingly, a qubit, or quantum bit, lives in a 2dimensional Hilbert space (a vector space over the complex numbers with Hermitian inner product). A state is a 1-dimensional subspace, which we normally represent by a unit vector spanning it. So we take an orthonormal basis of the space to consist of the two vectors e_{0} and e_{1}, corresponding to the values zero and one of the qubit. An arbitrary state of the qubit is represented by αe_{0} + βe_{1}, where |α|^{2} + |β|^{2} = 1.

According to the usual interpretation of quantum mechanics, we cannot observe the state directly. We can make a measurement, corresponding to a Hermitian (self-adjoint) operator on the space. The result of the measurement will be an eigenvalue of the operator. This result is not deterministic; different results will occur with appropriate probabilities. For example, we could measure the qubit in our example. The measurement could correspond to the operator of orthonormal projection onto the space spanned by

e_{1} (in matrix form, [ \begin{matrix}0 & 0 \\ 0 & 1 \end{matrix} ]). The eigenvalues of this operator are 0 and 1,

corresponding to the eigenvectors e_{0} and e_{1}. If the system is in the state αe_{0} + βe_{1}, then we obtain the result 0 with probability |α|^{2}, and the result 1 with probability |β|^{2}. However, the measurement changes the state of the system; after the measurement, the system is in a state spanned by an eigenvector corresponding to the eigenvalue obtained in the measurement. (If we find the value 0 for the qubit, the system will be in the state e_{0}, and information about α and β is lost.)

Again, in the classical case, we can represent n bits by an n-tuple of which each entry is zero or one, that is, an element of V = ℤ_{2}^{n}. Correspondingly, an n-tuple of qubits lives in a complex Hilbert space having an orthonormal basis corresponding to V. We write a typical vector in V as v, and denote by e_{v} the corresponding basis vector of the 2^{n}-dimensional Hilbert space ℂ^{2^{n}}.

Note that the Hilbert space is isomorphic to the tensor product of n copies of the 2-dimensional Hilbert space in which a single qubit lives. If v = (v_{1}, v_{2}, …, v_{n}), where v_{i} ∈ ℤ_{2} = {0, 1} for i = 1, 2, …, n, then

e_{v} = e_{v_{1}} ⊗ e_{v_{2}} ⊗ ⋯ ⊗ e_{v_{n}}.

Why the tensor product? Peter Shor [17] says:

One of the fundamental principles of quantum mechanics is that the joint quantum state space of two systems is the tensor product of their individual state spaces.

The tensor product of two spaces is the ‘universal bilinear product’ of the spaces. If {e_{1}, …, e_{m}} and {f_{1}, …, f_{n}} are bases for the two spaces V and W, then a basis for the tensor product V ⊗ W consists of all symbols e_{i} ⊗ f_{j}, for i = 1, …, m and j = 1, …, n. (Note that dim(V ⊗ W) = dim(V) · dim(W).) For v = ∑_{i=1}^{m} α_{i}e_{i} ∈ V and w = ∑_{j=1}^{n} β_{j}f_{j} ∈ W, we set

v ⊗ w = ∑_{i=1}^{m} ∑_{j=1}^{n} α_{i}β_{j}(e_{i} ⊗ f_{j}).

Note that, in contrast to the case of a direct sum, not every vector in the tensor product can be written as a pure tensor v ⊗ w.

A remark on notation. We do not use Dirac’s bra and ket notation beloved of physicists. However, we do have to keep straight several different vector spaces carrying various forms: we already have an n-dimensional space V over ℤ_{2}, and a 2^{n}-dimensional complex Hilbert space. Shortly we will meet a 2n-dimensional ℤ_{2}-space \overline{E} with a symplectic form! We will use v, a, b for typical vectors of V; its standard basis will be {u_{1}, …, u_{n}} (where u_{i} is a vector with 1 in the ith position and 0 elsewhere), and the usual dot product on V will be denoted by

a · b = ∑_{j=1}^{n} a_{j}b_{j}.

We do not give a special name to the Hilbert space. Its vectors have the form ∑_{v∈V} α_{v}e_{v} where α_{v} ∈ ℂ; the inner product of ∑ α_{v}e_{v} and ∑ β_{v}e_{v} is ∑ \overline{α_{v}}β_{v}.

3 Qubit errors and the error group

The evolution of a quantum system is described by a unitary transformation of the state space. We consider ‘errors’ to a single qubit represented by the following unitary matrices:

X = [ \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ] (bit error)
Z = [ \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} ] (phase error)

The effect of X is to interchange the basis vectors e_{0} and e_{1} (the zero and one states of the qubit). The effect of Z is to change the relative phase of the coefficients α and β of an arbitrary state (the argument of β/α) by 180^{∘}. (The arguments of α and β have no absolute significance, so we could as well use −Z, but the given choice is more convenient.)

Along with X and Z, we also allow the identity I (no error) and the product Y = XZ = −ZX. (It is more usual in quantum mechanics to set Y = iXZ; then X, Y, Z are the standard Pauli spin matrices. Note that X, Z and iXZ are Hermitian (or self-adjoint). However, Y = XZ is unitary, and then everything can be written with real coefficients. A reason to use Y = iXZ is that then Y is conjugate to both X and Z, which means a change of basis transforms any one to any other, and we can regard all three non-trivial errors are equally likely. However, we shall see that the discrete mathematics is the same whether we make this choice or the simpler real choice, so in what follows, we use Y = XZ.)

There is a simple expression for the effect of X and Z on the basis {e_{0}, e_{1}}. We use the convention that (−1)^{0} = 1 and (−1)^{1} = −1, where the exponent is taken from the finite field ℤ_{2}. Then we have, for v ∈ ℤ_{2},

Xe_{v} = e_{v+1}, Ze_{v} = (−1)^{1·v}e_{v}.

Now we can apply these errors ‘coordinatewise’ to n qubits. If u_{j} denotes the jth basis vector for V = ℤ_{2}^{n}, then the errors to the jth qubit act on the 2^{n}-dimensional Hilbert space with basis {e_{v} : v ∈ V } as

X(u_{j}) : e_{v} ↦ e_{v+u_{j}},
Z(u_{j}) : e_{v} ↦ (−1)^{v·u_{j}}e_{v}.

Then we can define X(a), Z(b) for any vectors a, b ∈ V by

X(a) : e_{v} ↦ e_{v+a},
Z(b) : e_{v} ↦ (−1)^{v·b}e_{v}.

Then {X(a) : a ∈ V } and {Z(b) : b ∈ V } are groups of unitary transformations of ℂ^{2^{n}} which are both isomorphic to the additive group of V. Together they generate the group

E = ⟨X(a), Z(b) : a, b ∈ V ⟩ = {±X(a)Z(b) : a, b ∈ V },

a group of order 2 · 2^{n} · 2^{n} = 2^{2n+1}.

We call E the group of allowable errors, or, for short, the error group. It can also be written in the form

E = {±A_{1} ⊗ ⋯ ⊗ A_{n} : A_{j} ∈ {I, X, Y, Z} for j = 1, …, n}.

Why do we only consider these particular errors? A quantum code can correct any one-qubit error if and only if it can correct the errors X(u_{j}), Y (u_{j}) and Z(u_{j}) for all j. Ths is because the matrices I, X, Y, Z span the 4-dimensional space of all 2 × 2 matrices: see [1, 5].

4 Forms and extraspecial 2-groups

The group E is an extraspecial 2-group, with centre ζ(E) = {±I} of order 2. We set \overline{E} = E/ζ(E), an elementary abelian group of order 2^{2n}, This is the third, and most important, vector space with which we have to deal. Before looking at it more closely, we give some details about alternating and quadratic forms on vector spaces over ℤ_{2} and their relation to extraspecial 2-groups.

In this section, V denotes an arbitrary vector space, not the space of n-tuples of bits introduced earlier.

Let V be a vector space over a field F. A quadratic form on F is a function Q : V → F which satisfies the conditions

(a) Q(λx) = λ^{2}Q(x) for all λ ∈ F, x ∈ V.

(b) The function B : V × V → F defined by

Q(x + y) = Q(x) + Q(y) + B(x, y)

is bilinear (that is, linear in each variable).

We express (b) by saying that the form B is obtained from Q by polarisation.

The form B defined in (b) is symmetric, that is, B(x, y) = B(y, x). Now, if the characteristic of F is not 2, then it follows from (a) and (b) that Q(x) = \frac{1}{2}B(x, x) for all x ∈ V, so that Q can be recovered from B: that is, quadratic forms and symmetric bilinear forms carry the same information. Things are very different in characteristic 2, however. We are interested in this case, specifically F = ℤ_{2}. From now on, we assume this.

Now we find that the form B is alternating, that is, B(x, x) = 0 for all x ∈ V. In general, an alternating bilinear form is skew-symmetric, that is, B(y, x) = −B(x, y) for all x, y ∈ V. Of course, in characteristic 2, this just says that B is symmetric.

Clearly, Q cannot be recovered from B. Instead, we see that, if Q_{1} and Q_{2} both polarise to B, then Q = Q_{1} − Q_{2} polarises to the zero form, that is,

Q(x + y) = Q(x) + Q(y).

Also, because λ^{2} = λ for all λ ∈ F, we have

Q(λx) = λQ(x).

Thus, Q is linear. Conversely, two quadratic forms differing by a linear form polarise to the same bilinear form. So each alternating bilinear form corresponds to a coset of the dual space of V in the space of all quadratic forms.

A bilinear form B is said to be non-singular if it has the properties

(a) if B(x, y) = 0 for all y ∈ V then x = 0;

(b) if B(x, y) = 0 for all x ∈ V then y = 0.

If B is skew-symmetric (or symmetric), then each of these conditions implies the other, and we need only assume one. A non-singular alternating bilinear form on V exists if and only if V has even dimension. For any such form, there is a basis {v_{1}, …, v_{n}, w_{1}, …, w_{n}} for V such that

B(v_{i}, v_{j}) = 0 = B(w_{i}, w_{j}) for all i, j,
B(v_{i}, w_{i}) = 1 = −B(w_{i}, v_{i}) for all i,
B(v_{i}, w_{j}) = 0 = B(w_{j}, v_{i}) for i ≠ j.

This is called a symplectic basis. A linear transformation of V which preserves the form B is called symplectic; the symplectic group is the group of all such transformations.

A quadratic form on an m-dimensional vector space is non-singular if it cannot be written as a form in fewer than m variables by any linear change of variables. In the case of an even-dimensional vector space over ℤ_{2}, a quadratic form Q is non-singular if and only if the bilinear form obtained by polarisation is non-singular. It can be shown that, up to symplectic transformation, there are just two types of quadratic forms associated with a given non-singular alternating bilinear form V. In terms of the symplectic basis, they are given by

Q_{1}(x) = α_{1}β_{1} + ⋯ + α_{n}β_{n},
Q_{2}(x) = α_{1}β_{1} + ⋯ + α_{n}β_{n} + α_{n}^{2} + β_{n}^{2},

where

x = ∑(α_{i}u_{i} + β_{i}w_{i}).

Given a subspace U of V, we set

U^{⊥} = {x ∈ V : B(x, u) = 0 for all u ∈ U}.

The non-singularity of B guarantees that

dim(U) + dim(U^{⊥}) = dim V,

but unlike the Euclidean case it is not true in general that V = U ⊕ U^{⊥}, since we may have U ∩ U^{⊥} ≠ {0}. A subspace U of V is said to be totally isotropic if B vanishes identically on U, in other words, if U ≤ U^{⊥}.

A vector x is said to be singular for the quadratic form Q if Q(x) = 0. A subspace U is totally singular if Q vanishes identically on U. By polarising the restriction of Q to U, we see that a totally singular subspace is totally isotropic; but the converse is not true. (Any 1-dimensional subspace is totally isotropic, but the span of a non-singular vector is not totally singular.)

Here is a small example. Take a 2-dimensional vector space over ℤ_{2}, with typical vector (x_{1}, x_{2}). The four quadratic forms 0, x_{1}^{2}, x_{2}^{2} aand x_{1}^{2} + x_{2}^{2} = (x_{1} + x_{2})^{2} are all singular, and are in fact equal to the four linear forms 0, x_{1}, x_{2} and x_{1} + x_{2}. The other four forms x_{1}x_{2}, x_{1}x_{2} + x_{1}^{2} = x_{1}(x_{1} + x_{2}), x_{1}x_{2} + x_{2}^{2} = x_{2}(x_{1} + x_{2}), and x_{1}x_{2} + x_{1}^{2} + x_{2}^{2}, are non-singular, and polarise to the bilinear form x_{1}y_{2} + x_{2}y_{1}. The first three are equivalent under linear change of variable; each has value 0 at three of the four vectors and 1 at the fourth. The last form takes the value 1 at all three non-zero variables.

An extraspecial 2-group is a 2-group whose centre, derived group, and Frattini subgroup all coincide and have order 2. Such a group E has order 2^{2n+1} for some n. If ζ(E) is the centre, then we can identify ζ(E) with the additive group of F = ℤ_{2}, and the factor group \overline{E} (which is elementary abelian of order 2^{2n}) with the additive group of a 2n-dimensional vector space over F.

Now the structure of the group can be defined in terms of the vector space. Commutation (the map (e, f) ↦ [e, f] = e^{−1}f^{−1}ef) is a function from E × E to ζ(E). Observing that [ez, f] = [e, fz] = [e, f] for z ∈ ζ(E), we see that it induces a map from \overline{E} × \overline{E} to F. It is readily checked that this map is a non-singular alternating bilinear form B. (This explains why |\overline{E}| is an even power of 2.)

Moreover, squaring (the map e ↦ e^{2}) is a function from E to ζ(E). Again, (ez)^{2} = e^{2} for z ∈ ζ(E), so it induces a quadratic form Q : \overline{E} → F, which polarises to B.

The vector space \overline{E}, with the bilinear form B and quadratic form Q, determine the structure of the extraspecial group E. From the classification of quadratic forms, we conclude that there are just two extraspecial groups of order 2^{2n+1} for any n (up to isomorphism).

A subgroup S of E is normal in E if and only if it contains ζ(E). For such a subgroup, \overline{S} is a subspace of \overline{E}. If we start with \overline{S} < \overline{E} we could have the corresponding S < E containing ζ(E) or not, but normality of S does not matter in what follows. The following are immediate:

(a) S is abelian if and only if \overline{S} is totally isotropic;

(b) S is elementary abelian if and only if \overline{S} is totally singular.

Consider our example with n = 1. The quadratic form x_{1}x_{2} corresponds to a group generated by two elements of order 2 with product of order 4; this is the dihedral group D_{8}. The form x_{1}x_{2} + x_{1}^{2} + x_{2}^{2} corresponds to a group in which all six non-central elements have order 4; this is the quaternion group Q_{8}. The singular forms correspond to groups which, while having a central subgroup of order 2 with elementary abelian quotient, are not extraspecial; x_{1}^{2} corresponds to C_{2} × C_{4}, and 0 to C_{2} × C_{2} × C_{2}.

5 Error group, continued

In our set-up, the error group

E = {±X(a)Z(b) : a, b ∈ V }

is an extraspecial 2-group of order 2^{2n+1}. Its centre is ζ(E) = {±I}, and \overline{E} = E/ζ(E) is a vector space over F.

We use the notation (a|b) for the element of \overline{E} which is the coset of ζ(E) containing X(a)Z(b). (This coset is {X(a)Z(b), −X(a)Z(b)}.) We use ∗ for the bilinear form on \overline{E} derived from commutation on E. In other words,

[X(a)Z(b), X(a′)Z(b′)] = (−1)^{(a|b)∗(a′|b′)}I.

A short calculation shows that

(a|b) ∗ (a′|b′) = a · b′ − a′ · b,

where · is the dot product on V. (Of course, we can replace the − sign by a + sign since the characteristic is 2.) Thus, two elements e, f ∈ E commute if and only if \overline{e} ∗ \overline{f} = 0.

The quadratic form will be denoted by Q: that is,

(X(a)Z(b))^{2} = (−1)^{Q(a|b)}I.

(If we had made the choice Y = iXZ instead of Y = XZ, we would need to enlarge our group E to include iI. As a consequence, E would have a larger center, ζ(E) = {(i^{ℓ})I : ℓ = 0, 1, 2, 3}. Nonetheless, the factor group E/ζ(E) would be “the same” elementary abelian 2-group of order 2^{2n}, and commutation on E would give the same bilinear form on this version of \overline{E}. However, since it would no longer be true that e^{2} = ±I for all e ∈ E, we would lose the quadratic form on \overline{E}.)

More on notation. The basis {(u_{j}|0), (0|u_{j}) : j = 1, …, n} is a symplectic basis for \overline{E}. We will reserve the symbol ⊥ for orthogonality in this space (with respect to the form ∗). We also make another use of ⊥, derived from this one. If S is a subgroup of E, then we let S^{⊥} be the centraliser of S in E. (If S′ = C_{E}(S), then \overline{S′} = \overline{S}^{⊥}, so the notation is consistent.)

To avoid confusion with orthogonality in \overline{E}, we use a non-standard symbol for orthogonality of vectors in V. For U ⊆ V we’ll write U^{‡} = {v ∈ V : v·u = 0 for all u ∈ U}.

We will use ⟨…⟩_{V}, ⟨…⟩\overline{E}, ⟨…⟩_{ℂ} for the subspace of V, \overline{E} or ℂ^{2^{n}} respectively, spanned by a set …; and ⟨…⟩ (without adornment) will denote the subgroup generated by . . ..

We are interested in abelian subgroups of E. Note that any set of mutually commuting transformations on the Hilbert space ℂ^{2^{n}} which contains the adjoints of all its elements is simultaneously diagonalisable, and has an orthonormal basis consisting of eigenvectors. Said otherwise, the common eigenspaces of the transformations in the set are mutually orthogonal. Any abelian subgroup of E satisfies this.

We begin with three rather trivial examples before turning to our main illustrative example.

Example 1 Z(V) = {Z(b) : b ∈ V } (the group of phase errors) is abelian; we have \overline{Z(V)} = \{(0|b) : b ∈ V \}. The common eigenspaces are the 2^{n} mutually orthogonal 1-dimensional spaces ⟨e_{v}⟩_{ℂ}, for v ∈ V. (This follows from the equation Z(b)e_{v} = (−1)^{b·v}e_{v}.)

Example 2 X(V) = {X(a) : a ∈ V } (the group of bit errors) is also abelian. Its eigenspaces are less trivial to describe. For any vector b ∈ V, set

z_{b} = ∑_{v∈V}(−1)^{b·v}e_{v}.

Then

X(a)z_{b} = ∑_{v∈V}(−1)^{b·v}e_{v+a}
= ∑_{w∈V}(−1)^{b·(w+a)}e_{w}
= (−1)^{b·a}z_{b},

so z_{b} is a common eigenvector. A short calculation shows that these 2^{n} eigenvectors are mutually orthogonal; this also follows from the fact that any two of them afford different eigenvalues for at least some element of X(V).

Remark As these examples suggest, if S is an abelian subgroup of E for which \overline{S} is a maximal totally singular subspace of \overline{E} (of dimension n), the eigenspaces for S form an orthogonal frame (a family of 2^{n} mutually orthogonal 1-dimensional subspaces) in ℂ^{2^{n}}. For more about the geometry of such frames, and their relation to other topics in coding theory, we refer to [2].

Example 3 Let

S = {Z(b) : b ∈ ⟨u_{4}, …, u_{n}⟩_{V} },

so

S^{⊥} = {±X(a)Z(b) : b ∈ V, a ∈ ⟨u_{1}, u_{2}, u_{3}⟩_{V} }.

Then S has 2^{n−3} orthogonal eigenspaces, each of dimension 2^{3} = 8. A typical one is

Q_{u} = ⟨e_{w+u} : w ∈ ⟨u_{1}, u_{2}, u_{3}⟩_{V} ⟩_{ℂ} ,

where u ∈ ⟨u_{4}, …, u_{n}⟩_{V}. (This works since

Z(b)e_{w+u} = (−1)^{b·(w+u)}e_{w+u} = (−1)^{b·u}e_{w+u}

as b · w = 0.) Notice that Q_{u} corresponds to a character χ_{u} of S, given by

χ_{u}(Z(b)) = (−1)^{b·u}.

Also notice that the bases of the various eigenspaces of S partition the 2^{n} eigenspaces of Z(V) (corresponding to the maximal isotropic subspace containing \overline{S}). The subset of 1-spaces spanning one eigenspace Q_{u} consists of those affording the character χ_{u}: for s ∈ S, s(e_{v}) = χ_{u}(s)e_{v} for v ∈ u + W. (This gives another way to see that the 2^{n−3} eigenspaces of S form an orthogonal decomposition of ℂ^{2^{n}}.)

If we set Q = Q_{0} (corresponding to the trivial or principal character), then we observe the following:

(a) For s ∈ S, q ∈ Q, we have s(q) = q.

(b) For s′ ∈ S^{⊥}, q ∈ Q, we have s′(q) ∈ Q.

(c) Any e ∈ E permutes the eigenspaces Q_{u}; it fixes Q if and only if it lies in S^{⊥}.

(d) There is a one-to-one correspondence between eigenspaces Q_{u} and characters χ_{u} of \overline{S}.

We will see that these four properties are typical.

6 Additive codes

Choose an abelian subgroup S of E. (Equivalently, choose a subspace \overline{S} of \overline{E} for which \overline{S} ≤ \overline{S}^{⊥}.) Let dim(\overline{S}) = n − k. Then S has 2^{n−k} eigenspaces, one for each character of \overline{S}. Each eigenspace has dimension 2^{k}, and they form an orthogonal decomposition of ℂ^{2^{n}}.

Choose Q to be the eigenspace corresponding to the trivial character. Then we have, as in the example above:

(a) For s ≠ −I, q ∈ Q, we have s(q) = q.

(b) For s′ ∈ S^{⊥}, q ∈ Q, we have s′(q) ∈ Q.

(c)Any e ∈ E permutes the eigenspaces of S; it fixes Q if and only if it lies in S^{⊥}; so E/S^{⊥} permutes the eigenspaces regularly.

(d) The eigenspaces of S are in one-to-one correspondence with the characters of \overline{S}: an eigenspace Q′ determines a character χ of S satisfying s(q) = χ(s)q for s ∈ S and q ∈ Q′ with χ(−I) = −1 if −I ∈ S; χ thus defines a character of \overline{S}.

Now Q has dimension 2^{k}, and is isomorphic to the space of k qubits, but the embedding of Q in the larger space ‘smears out’ the k qubits over the space of n qubits. (This is exactly analogous to the situation in classical errorcorrecting codes: there, V = ℤ_{2}^{n} is the space of n bits, and C = {xG : x ∈ ℤ_{2}^{k}} is a k-dimensional linear code, which ‘smears out’ the k bits of x over the space V.) So Q will be our quantum error-correcting code.

In the classical case, a message consists of n bits, that is, it is a vector in V. Errors are also vectors in V: we have ‘received word equals transmitted word plus error’. The zero error has no effect. If we use a code C, then errors in C are undetectable. There will be a set E of so-called correctable errors. They have the property that, if e, f ∈ E with e ≠ f, then e − f ∉ C \ {0}, that is, e − f is not an undetectable error. This means that we can detect the addition of an error to a codeword, and we do not confuse the effects of different errors (as long as they lie in E). The commonest situation is that when C has minimum weight at least d, when E consists of all words of weight at most ⌊(d − 1)/2⌋.

Table 1 compares the situation in the classical and quantum cases.

Classical  Quantum
Message  n bits, in ℤ_{2}^{n} = V  n qubits, in ℂ^{2^{n}}
Error group  V  E
e(z) = z + v  e(z) as before
Code  C ≤ V, dim(C) = k Q ≤ ℂ^{2^{n}}, dim(Q) = 2^{k}
Undetectable C ≤ V S^{⊥} ≤ E

errors

Errors with {0} ≤ C S ≤ S^{⊥}

no effect

Correctable  E ⊆ V  E ⊆ E
errors  e, f ∈ E ⇒  e, f ∈ E ⇒
e − f ∉ C \ {0}  f^{−1}e ∉ S^{⊥} \ S

Table 1: Classical and quantum error correction

Theorem 6.1 (Calderbank et al. [3]) With the notation as above, assume that the minimal q-weight of \overline{S}^{⊥}\\overline{S} is d. Then Q corrects errors in ⌊(d−1)/2⌋ qubits.

Here, the quantum weight, or q-weight, of (a|b) ∈ \overline{E} (or, equivalently, of ±X(a)Z(b) ∈ E) is the number of coordinates j in which either a_{j} ≠ 0 or b_{j} ≠ 0 (in other words, the number of qubits which have suffered a bit error, a phase error, or both.) The theorem asserts that, if E is the set of elements with q-weight at most ⌊(d − 1)/2⌋, then we have e, f ∈ E ⇒ f^{−1}e ∉ S^{⊥} \ S.

Suppose Q is an additive code, i.e. Q is an eigenspace for S ≤ E, and E is the set of correctable errors for Q. Here is how decoding works. Suppose the codeword q ∈ Q is sent, but the received message is z = e(q) for some e ∈ E. If s_{1}, …, s_{n−k} are a set of generators for S, then by calculating s_{j}(z) = χ(s_{j})z for 1 ≤ j ≤ n − k (the syndrome of e) , we can identify the character χ and therefore the eigenspace Q′ containing z. We know Q′ = f(Q) for some f ∈ E, and we decode z to f^{−1}(z) = f^{−1}e(q). (Notice that this decoding step does not require knowing e or q.) In order for this procedure to lead us to the correct state ⟨q⟩_{ℂ} it’s necessary that e(Q) = f(Q) for e, f ∈ E should imply ⟨f^{−1}e(q)⟩_{ℂ} = ⟨q⟩_{ℂ}. But that is exactly our condition on E: f^{−1}e cannot be in S^{⊥} \ S.

Now, the extra condition that distinct e and f in E should produce independent vectors e(q) and f(q) means that f(Q) = e(Q) implies f = e. We call the code non-degenerate if it satisfies the stronger condition that e, f ∈ E implies f^{−1}e ∉ \overline{S}^{⊥} \ \{0\}. So, in the special case of a non-degenerate code, identifying the eigenspace containing z actually identifies e (rather than just enabling e to be corrected).

Note: Calderbank et al [3] suggest that the dichotomy between nondegenerate and degenerate codes is less useful than one between pure and impure codes: A code is pure if distinct e and f in E give orthogonal images e(q) and f(q) of a codeword q. They remark that for additive codes, the two notions coincide, while in general purity implies non-degeneracy, but not conversely.

7 Main example: an [[8, 3, 4]] code

Following the theorem in the previous section, to obtain an additive code mapping k qubits to n and correcting errors in ⌊(d−1)/2⌋ qubits, we need to find a self-orthogonal (n − k)-dimensional subspace \overline{S} of the 2n-dimensional binary space \overline{E} with \overline{S}^{⊥} \\overline{S} having minimum q-weight d. We call such a code an [[n, k, d]] code. We use the double brackets to distinguish it from a classical [n, k, d] binary code, a k-dimensional subspace of an n-dimensional binary vector space whose non-zero elements have Hamming weight (H-weight) at least d. In this section we construct a specific example of an [[8, 3, 4]] code adapted from [4] and [10].

To begin, we need a 5-dimensional subspace \overline{S} ≤ \overline{S}^{⊥} of the 16-dimensional binary space \overline{E}, and we would like the minimal non-zero q-weight of vectors in \overline{S}^{⊥} to be 4.

Vectors in \overline{E} have the form (a|b) for a, b ∈ V, where V is a binary space of dimension 8. We base our construction of \overline{S} on the [8, 4, 4] extended Hamming code Ĥ_{3}, a self-orthogonal subspace of V obtained by extending the [7, 4, 3] Hamming code H_{3} by adding a parity-check bit to each vector. (Our notation reflects the fact that [2^{r} − 1, 2^{r} − 1 − r, 3] Hamming codes H_{r} exist for r ≥ 3. There is further discussion of Hamming codes in Section 10.)

We construct H_{3} by specifying a 3 × 7 parity-check matrix H—recall the code is the null space of its parity-check matrix. The columns of H will consist of all possible non-zero vectors in ℤ_{2}^{3} ≃ GF(8). We do this by choosing a generator α = α^{3} + 1 of the multiplicative group of GF(8), and letting the columns of H be α^{6}, …, α, 1, (where xα^{2} + yα + z is written as the column [x, y, z]^{⊤}) giving

H = [ \begin{matrix}1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{matrix} ]

This construction of H makes it easy to see that H_{3} is a cyclic code: if v = (v_{1}, …, v_{7}) is in H_{3}, so is its cyclic shift v′ = (v_{7}, v_{1}, …, v_{6}). From H we easily obtain a generator matrix G for H_{3}—recall a code is the row space of its generator matrix.

G_{0} = [ \begin{matrix}1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{matrix} ]

Since the vector \overline{1} = (1, 1, 1, 1, 1, 1, 1) is in H_{3}, we get another generator matrix G_{1} by adding \overline{1} to each row of G_{0}.

G_{1} = [ \begin{matrix}0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 \end{matrix} ]

We obtain the [8, 3, 4] extended Hamming code Ĥ_{3} by adding a parity check bit to the front of each vector in H_{3} so that the resulting vector has even H-weight. The minimum H-weight of nonzero vectors in H_{3} is 3, and the minimum H-weight is 4 for Ĥ_{3}. Moreover, Ĥ_{3} = Ĥ_{3}^{‡}.

Finally, we’re ready to describe a 5 × 16 generator matrix for \overline{S}. Let a be the last row of G_{1} and b be its first. Let a_{1} be the extension of a and b_{1} be the extension of b, two vectors in Ĥ_{3}. Next a_{2} is the extension of the cyclic shift a′, and b_{2} is the extension of b′. Similarly a_{3} and b_{3} are extensions of a′′ and b′′. We take a_{4} = b_{5} to be the 8-tuple \overline{1} and a_{5} = b_{4} to be the 8-tuple \overline{0}. The 5 × 16 matrix G^{(0)} has for its rows the vectors (a_{1}|b_{1}), …, (a_{5}|b_{5}).

G^{(0)} = [ \begin{matrix}0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & | & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & | & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & | & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & | & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & | & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} ]

The rows of G^{(0)} are linearly independent, so its rowspace \overline{S} is of dimension 5. Because Ĥ_{3} = Ĥ_{3}^{‡}, we see that (a_{i}|b_{i})∗(a_{j}|b_{j}) = a_{i} ·b_{j} +a_{j} ·b_{i} = 0 for i, j = 1, …, 5, so \overline{S} ≤ \overline{S}^{⊥}. The dimension of \overline{S}^{⊥} is 16 − 5 = 11, and so \overline{S}^{⊥} = \overline{S} ⊕ T for T of dimension 6. We can choose a basis \{(a_{j}|\overline{0}), (\overline{0}|b_{j}) : j = 1, 2, 3\} for T, and from this we can see that the minimum q-weight of \overline{S}^{⊥} is 4.

Our code Q is the +1 eigenspace of the subgroup S < E acting on the 2^{8}-dimensional complex vector space C^{2} ⊗ … ⊗ C^{2}. The subspace Q is of complex dimension 2^{3}; Q thus maps 3 qubits to 8 qubits and corrects errors in E that affect 1 qubit.

Finding a basis for Q. We would like a basis for Q consisting of vectors of the form γ ∑_{v∈V} α_{v}e_{v}, where the coefficients α_{v} ∈ {0, +1, −1} and we make q_{w} a unit vector by a suitable choice of the (real) scalar γ. Every additive code Q has such a basis. The construction of the basis depends on choosing generators for \overline{S} of the form (a_{1}|b_{1}), … (a_{n−k}|b_{n−k}) with a_{1}, …, a_{m} linearly independent and a_{m+1} = … = a_{n−k} = \overline{0} (which we can always do). Then, the fact that \overline{S} is totally isotropic implies that

⟨b_{m+1}, …, b_{n−k}⟩_{V}^{‡} = ⟨a_{1}, …, a_{m}⟩_{V} ⊕ W

for some W ≤ V of dimension n − (n − k − m) − m = k. (If n − k = m, then V = ⟨a_{1}, …, a_{m}⟩_{V} ⊕ W.) If we write s_{j} = X(a_{j})Z(b_{j}) ∈ S, then the desired basis for Q is {q_{w} : w ∈ W }, where

q_{w} = \frac{1}{\sqrt{2^{m}}} ∑_{s∈⟨s_{1},...,s_{m}⟩} s(e_{w}).

Notice that there are |W | = 2^{k} vectors q_{w}, agreeing with dim Q = 2^{k}.

First we show that the q_{w} are linearly independent—in fact, they are orthogonal. If we write A = ⟨a_{1}, …, a_{m}⟩_{V}, then

q_{w} = \frac{1}{\sqrt{2^{4}}} ∑_{a∈A} ±e_{w+a}

where our notation reflects the fact that the generator s_{j} = X(a_{j})Z(b_{j}) takes e_{w} to ±e_{w+a_{j}}. Because A ∩ W = \{\overline{0}\}, w ≠ w′ implies w + a ≠ w′ + a′ for all a, a′ ∈ A, so each q_{w} has for its summands a different subset of the orthonormal basis {e_{v}}, and q_{w} and q_{w′} are orthogonal whenever w ≠ w′.

Now we show that each q_{w} ∈ Q by checking that s_{j}(q_{w}) = q_{w} for each generator s_{j} of S. This is immediate from the definition of q_{w} for j = 1, …, m. For m < j ≤ n − k notice that w ∈ ⟨b_{m+1}, …, b_{n−k}⟩_{V}^{‡} implies s_{j}(e_{w}) = Z(b_{j})e_{w} = e_{w}. Now use the fact that ss_{j} = s_{j}s for s ∈ ⟨s_{1}, …, s_{m}⟩.

In our specific case we have m = 4 and we may write

q_{w} = \frac{1}{\sqrt{2^{4}}} ∑_{s∈⟨s_{1},...,s_{4}⟩} s(e_{w})

where ⟨b_{5}⟩_{V}^{‡} = ⟨a_{1}, …, a_{4}⟩_{V} ⊕ W with W of dimension 3.

8 Efficient encoding

Our encoding task is to take a pure k-qubit state e_{(c_{1},...,c_{k})} to q_{w} ∈ Q, where w = ∑ c_{j}w_{j} for some basis {w_{1}, …, w_{k}} of W, a complement of A = ⟨a_{1}, …, a_{m}⟩_{V} in ⟨b_{m+1}, …, b_{n−k}⟩_{V}^{‡}. We will follow Cleve and Gottesman [6] to build a quantum circuit to accomplish this encoding.

As Shor says, a quantum circuit is built out of “logical quantum wires,” each corresponding to one of the n qubits, and quantum gates, each acting on one or two wires [17]. A quantum gate is a unitary transformation, since these correspond to the possible physical transformations of a quantum system. Shor assumes that each gate acts on either one or two wires; that is, each maps 1 qubit to 1 qubit or 2 qubits to 2 and acts as the identity on the remaining qubits. The Cleve and Gottesman encoding circuit is of this kind, and it is “efficient” because it uses at most (n − k)n gates.

1-qubit gates We will use the 1-qubit gates X, Z and Y = XZ along with another denoted H, described below. In terms of our basis e_{0}, e_{1} for ℂ^{2}, H is defined by

H(e_{0}) = (1/\sqrt{2})(e_{0} + e_{1}) and
H(e_{1}) = (1/\sqrt{2})(e_{0} − e_{1}).

It’s easy to check that H is unitary and H^{2} = I_{2}.

We don’t need these facts here, but notice

• HXH = Z;

• if H_{n} = H ⊗ … ⊗ H is the transformation on ℂ^{2^{n}} obtained by applying H to each of the n qubits, then H_{n}X(V)H_{n} = Z(V); • the basis vectors z_{b} = ∑_{v∈V} (−1)^{b·v}e_{v} of example 2 in §5 are images of

our standard basis vectors e_{b} under \sqrt{2^{n}}H_{n}; and

• the matrices with respect to our standard bases of \sqrt{2}H and of \sqrt{2^{n}}H_{n} are each Hadamard matrices, namely r × r matrices M with entries in {0, +1, −1} satisfying MM^{t} = rI.

2-qubit gates The gates X, Y, Z and H become 2-qubit gates if they are controlled by a second qubit. The controlled version of X is particularly important, as we explain below, and it has its own name: CNOT for controlled not. Here is a circuit diagram for CNOT.

controller x — • — x
|
target  y — ⊕ — x + y

In other words, CNOT takes the basis vector e_{(x,y)} of ℂ^{4} to e_{(x,x+y)}. It is clearly a unitary transformation. The name controlled not is because the target bit y is negated (or not) according as the controller equals 1 or 0. CNOT is indeed just the controlled version of X: the CNOT circuit above takes e_{(x,y)} to (I ⊗ X^{x})e_{(x,y)}, applying X or not according to the value of the controller.

We use similar representations for circuits describing our other 2-qubit gates. Here is a circuit for the controlled version of Z:

controller x — • —
|
target  y — Z —

This circuit takes e_{(x,y)} to (I ⊗ Z^{x})e_{(x,y)}.

It’s actually possible to use CNOT as the only 2-qubit gate. Shor says that “CNOT together with all quantum one-bit gates forms a universal set” for any quantum circuit whose gates act on n qubits for some fixed n [17]. For a very simple example, since Y = HXH, the controlled version of Y using CNOT and 1-qubit gates is (H ⊗ I)∘CNOT ∘(H ⊗ I). But working exclusively with CNOT does increase the number of 1-qubit gates required for the circuit. In what follows, we make free use of controlled versions of all of the 1-qubit gates.

The 2-qubit gates, in particular CNOT, are intrinsically global: there is no way to describe them by restricting attention to a single qubit. Because they accept as input the tensor product of superpositions (linear combinations) of e_{0} and e_{1}, they are the gates that makes the computation quantum rather than classical. (Compare the discussion of Deutsch’s problem in the next section.)

The following description is specific to our particular [[8, 3, 4]] example, but the generalization to any additive [[n, k, d]] code is natural.

The input to our quantum encoding circuit will be 8 qubits prepared in the state e_{v} with v = (c_{1}, c_{2}, c_{3}, 0, 0, 0, 0, 0). (We prepare a qubit in a given state by measuring it and obtaining the required value for the measurement.) The output will be q_{w}. We will accomplish this in two steps.

Step 1:

e_{(c_{1},c_{2},c_{3})} ⊗ e_{(0,0,0,0,0)} → e_{(c_{1},c_{2},c_{3})} ⊗ e_{0} ⊗ \frac{1}{\sqrt{2^{4}}} ∑_{(d_{1},d_{2},d_{3},d_{4})∈ℤ_{2}^{4}} e_{(d_{1},d_{2},d_{3},d_{4})}

Step 2:

e_{(c_{1},c_{2},c_{3})}⊗e_{0}⊗e_{(d_{1},d_{2},d_{3},d_{4})} → s_{1}^{d_{1}}s_{2}^{d_{2}}s_{3}^{d_{3}}s_{4}^{d_{4}}X(w_{1})^{c_{1}}X(w_{2})^{c_{2}}X(w_{3})^{c_{3}}e_{(0,0,0,0,0,0,0,0)}

Notice that X(w_{1})^{c_{1}}X(w_{2})^{c_{2}}X(w_{3})^{c_{3}}e_{(0,0,0,0,0,0,0,0)} = e_{w} for w = c_{1}w_{1} + c_{2}w_{2} + c_{3}w_{3}. The transformations X(w_{1}), X(w_{2}), X(w_{3}) are called seed generators. They’re not elements of S, but they provide the “seeds” e_{w} for the basis vectors q_{w} of Q. Equivalently, we sometimes call the vectors (w_{1}|\overline{0}), (w_{2}|\overline{0}), (w_{3}|\overline{0}) ∈ \overline{E} seed generators.

The circuit for Step 1 is

\begin{matrix}c_{1} & — & — & — \\ c_{2} & — & — & — \\ c_{3} & — & — & — \\ 0 & — & — & — \\ 0 & — & H & — \\ 0 & — & H & — \\ 0 & — & H & — \\ 0 & — & H & — \end{matrix}

The reason this circuit works is that

\frac{1}{\sqrt{2^{4}}} ∑_{d∈ℤ_{2}^{4}} e_{d} = \frac{1}{\sqrt{2^{4}}} (e_{0} + e_{1}) ⊗ (e_{0} + e_{1}) ⊗ (e_{0} + e_{1}) ⊗ (e_{0} + e_{1})
= (H ⊗ H ⊗ H ⊗ H)(e_{0} ⊗ e_{0} ⊗ e_{0} ⊗ e_{0})

Step 2 requires more work. We begin by describing how to modify the generator matrix G^{(0)} for \overline{S} in order first to define a basis w_{1}, w_{2}, w_{3} for the complement of ⟨a_{1}, a_{2}, a_{3}, a_{4}⟩_{V} in ⟨b_{5}⟩_{V}^{‡} and second to facillitate the construction of the circuit accomplishing Step 2.

Recall that

G^{(0)} = [ \begin{matrix}0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & | & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & | & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & | & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & | & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & | & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} ]

By doing row operations^{1} on G^{(0)}, we get a new generator matrix

1Row(2) to (2)+(3)+(4), (3) to (3)+(4), (4) to (1)+(2)+(4), and then permute rows

G^{(1)} = [ \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & | & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & | & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & | & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & | & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & | & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \end{matrix} ]

of the form

[ \begin{matrix}0 & 0 & 0 & | & B_{1} & I_{n−k−m} & D_{1} \\ A_{1} & A_{2} & I_{m} & | & E_{1} & E_{2} & F \end{matrix} ]

where in our case n = 8, n − k = 5 is the dimension of \overline{S}, and m = 4 is the number of linearly independent a_{j} among the generators (a_{1}|b_{1}), …, (a_{5}|b_{5}) of \overline{S}. The columns of G^{(1)} are blocked k, n − k − m, m on each side; that is A_{1} and B_{1} each have k columns, A_{2} and E_{2} each have n − k − m columns, and D_{1} and F each have m columns.

We can take as the “seed” generators for the basis of Q the rows of

G^{seed} = [ I_{k} B_{1}^{T} 0 | 0 0 0 ]
= [ \begin{matrix}1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & | & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & | & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & | & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ]

(If n − k = m, then we take G^{seed} = [ I_{k} 0 | 0 0 ] .)

Step 2 of the encoding is described by the columns of

G^{aug} = [ (G^{seed})^{T} (G^{(1)})^{T} ] = [ \begin{matrix}G^{bit} \\ G^{ph} \end{matrix} ]

In our case

G^{bit} = [ \begin{matrix}1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ] G^{ph} = [ \begin{matrix}0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \end{matrix} ]

The columns of G^{bit} are the vectors w_{1}, w_{2}, w_{3}, a_{5}, a_{1}, a_{2}, a_{3}, a_{4} which determine the bit changes our circuit must accomplish. The non-zero columns of G^{ph} are b_{5}, b_{1}, b_{2}, b_{3}, b_{4}, which determine the phase changes it must perform.

The circuit that describes just the bit changes is

c_{1} − • − − − − − ⊕ − − − ⊕ − ⊕ −
| | | |
c_{2} − − − • − − − ⊕ − ⊕ − ⊕ − − −
| | | | | |
c_{3} − − − − − • − − − ⊕ − ⊕ − ⊕ −
| | | | | | |
0 − ⊕ − ⊕ − ⊕ − ⊕ − ⊕ − − − ⊕ −
| | | |
d_{1} − − − − − − − • − − − − − − −
| | |
d_{2} − − − − − − − − − • − − − − −
|  |
d_{3} − − − − − − − − − − − • − − −
|
d_{4} − − − − − − − − − − − − − • −

This circuit takes e_{(c_{1},c_{2},c_{3},0,d_{1},d_{2},d_{3},d_{4})} to e_{v} where v = (c_{1}+d_{1}+d_{3}+d_{4}, c_{2}+ d_{1} + d_{2} + d_{3}, c_{3} + d_{2} + d_{3} + d_{4}, c_{1} + c_{2} + c_{3} + d_{1} + d_{2} + d_{4}, d_{1}, d_{2}, d_{3}, d_{4}) as it should.

If now we put in the phase changes as well (keeping in mind that Y = XZ), we get

c_{1} − • − − − − − ⊕ − − − ⊕ − ⊕ −
| | | |
c_{2} − − − • − − − Y − ⊕ − Y − − −
| | | | | |
c_{3} − − − − − • − − − Y − ⊕ − Y −
| | | | | | |
0 − ⊕ − ⊕ − ⊕ − Y − Y − − − ⊕ −
| | | |
d_{1} − − − − − − − • − Z − Z − − −
| | | |
d_{2} − − − − − − − − − • − Z − Z −
| | | |
d_{3} − Z − − − − − Z − Z − • − Z −
|  |
d_{4} − Z − − − − − Z − − − − − • −

To see that this is correct, think of applying s_{4} = X(a_{4})Z(b_{4}) last in our definition of q_{w} (harmless, since the s_{j} commute). The input to s_{4}, after s_{1}, s_{2} and s_{3} have had whatever effect they might (depending on d_{1}, d_{2} and d_{3}), will be of the form e_{r} with r = (r_{1}, r_{2}, r_{3}, r_{4}, d_{1}, d_{2}, d_{3}, d_{4}), where the values of the r_{j} could be anything, but the last four coordinates are determined. Now Z(b_{4})^{d_{4}}e_{r} = (−1)^{d_{4}(b_{4}·r)}e_{r}. The dot product b_{4} · r = r_{3} + d_{2} + d_{3} + d_{4}, so only the 3rd, 6th, 7th, and 8th “wires,” carrying the values of r_{3}, d_{2}, d_{3} and d_{4} respectively, are relevant to the calculation, and they are each controlled by d_{4}. Isolating just this portion of the circuit,we see that the 3rd wire contributes (−1)^{d_{4}r_{3}} to the phase change. Similarly, the 6th contributes (−1)^{d_{4}d_{2}}, the 7th contributes (−1)^{d_{4}d_{3}}, and the 8th contributes (−1)^{d_{4}d_{4}}.

For the grand finale, we put in step one of the encoding, writing R = HZ, to get

c_{1} − • − − − − − ⊕ − − − ⊕ − ⊕ −
| | | |
c_{2} − − − • − − − Y − ⊕ − Y − − −
| | | | | |
c_{3} − − − − − • − − − Y − ⊕ − Y −
| | | | | | |
0 − ⊕ − ⊕ − ⊕ − Y − Y − − − ⊕ −
| | | |
d_{1} − H − − − − − • − Z − Z − − −
| | | |
d_{2} − H − − − − − − − • − Z − Z −
| | | |
d_{3} − R − − − − − Z − Z − • − Z −
|  |
d_{4} − R − − − − − Z − − − − − • −

In our specific example, the number of 1-qubit gates is 4 and the number of 2-qubit gates is 23. In general, the number of 1-qubit gates is m ≤ n − k and the number of 2-qubit gates is bounded by (n − k − m)k + (n − 1)m ≤ (n − 1)(n − k), so the total number of gates is bounded by n(n − k). The bound on the number of 2-qubit gates is obtained by observing that there are at most (n − k − m) targets controlled by each of c_{1}, …, c_{k}, contributing at most (n − k − m)k gates. And there are at most (n − 1) targets controlled by each of d_{1}, …, d_{m}, contributing at most (n − 1)m gates.

9 Deutsch’s problem

Imagine having a “quantum black box,” a function

f : {0, 1} → {0, 1}.

We would like to know not the local values f(0) and f(1) but whether or not f has the global property of being constant. Can we decide this without running the black box twice? This is Deutsch’s problem.

If we use a classical computer, the answer is no. But if we can use a quantum computer, the answer is yes, using Deutsch’s algorithm.

The heart of Deutsch’s algorithm is a 2-qubit gate reminiscent of CNOT. We define a function

U_{f} : ℂ^{2} ⊗ ℂ^{2} → ℂ^{2} ⊗ ℂ^{2}

on basis vectors by U_{f}(e_{x} ⊗ e_{y}) = e_{x} ⊗ e_{y+f(x)}. It’s clear that U_{f} is a unitary transformation. As noted earlier, because this is a quantum computer, the input to U_{f} can be a tensor product of superpositions of e_{0} and e_{1}.

Deutsch’s algorithm to solve his problem is described by the following circuit.

e_{0} — H — • — H — measure
|
e_{1} — H — U_{f} —  —  —

This circuit calculates

[P_{0} ∘ (H ⊗ I) ∘ U_{f} ∘ (H ⊗ H)](e_{0} ⊗ e_{1}),

where P_{0}(e_{x} ⊗ e_{y}) = e_{x}.

The result of the circuit before measuring is

±e_{0} ⊗ (1/\sqrt{2})(e_{0} − e_{1}) if f is constant, and
±e_{1} ⊗ (1/\sqrt{2})(e_{0} − e_{1}) otherwise

So, after measuring we find that we obtain the result ±e_{0} if f is constant, and ±e_{1} otherwise. Note that running the circuit once is all that is required, which means calculating f only once suffices.

This small example captures the idea behind quantum parallelism: applying U_{f} once to the tensor product of superpositions (e_{0} + e_{1}) ⊗ (e_{0} − e_{1}) generates a state

[(−1)^{f(0)}e_{0} + (−1)^{f(1)}e_{1}] ⊗ (e_{0} − e_{1})

that encodes global propeties of f.

10 Hamming codes

We are going to construct an infinite family of codes which correct one qubit error. These codes, which have the parameters [[n, n − 2m, 3]], where n = (4^{m} − 1)/3, are the quantum analogue of Hamming codes. We begin with a short account of classical Hamming codes (which, incidentally, were first constructed as factorial designs in statistics by Fisher [8, 9]).

Let q be a prime power, and m a positive integer. The vector space GF(q)^{m} contains q^{m} −1 non-zero vectors, which fall into n = (q^{m} −1)/(q −1) one-dimensional subspaces. These subspaces are the points of the projective space PG(m − 1, q). Equivalently, a set of non-zero vectors which is maximal with respect to the property that none of its elements is a scalar multiple of another has size n, containing one vector from each one-dimensional subspace. Let H be the m × n matrix whose columns are the n vectors in such a set, and let C be the code with parity check matrix H: that is,

C = {v ∈ GF(q)^{n} : vH^{⊤} = 0}.

Note that different choice of the n vectors, or writing the vectors in a different order, gives an equivalent code. (Two codes are said to be equivalent if one is obtained from the other by permuting the coordinates and multiplying the entries in each coordinate by a non-zero scalar.) The code C is the Hamming code of length n and dimension n − m over GF(q), written H_{m}(q). Since any two columns of H are linearly independent, we see that the Hamming code has minimum weight 3.

The code we actually require, however, is the dual Hamming code D_{m}(q), the code which has H as its generator matrix: this is the row space of H, given by

D_{m}(q) = {xH : x ∈ GF(q)^{m}}.

On the vector space GF(q)^{n}, we have the standard inner product, given by

v · w = ∑_{j=1}^{n} v_{j}w_{j}.

In addition, if the field order q is a square, say q = r^{2}, then there is a field automorphism α ↦ \overline{α} = α^{r} of order 2. In this case, there is also a Hermitian inner product on GF(q)^{n}, given by

v ∘ w = ∑_{j=1}^{n} \overline{v_{j}}w_{j}.

A code C is self-orthogonal (with respect to an inner product) if the inner product vanishes identically on C, that is, if C ≤ C^{⊥} (with respect to the inner product).

Theorem 10.1 If q = 4, m ≥ 2, then D_{m}(q) is self-orthogonal with respect to the Hermitian inner product on GF(q)^{n}.

Proof The field GF(4) can be written as \{0, 1, ω, \overline{ω}\} where \overline{ω} = ω^{2} = 1 + ω. Note that the cube of every non-zero element is equal to 1, since the multiplicative group has order 3.

The columns of the matrix H form a set S of n vectors, one in each onedimensional subspace of V = GF(4)^{m}. Now any codeword of C = D_{m}(q) is obtained by taking a linear form f on V = GF(4)^{m} and writing down its values on the elements of S. (For the rows of H are obtained in this way from the forms f_{1}, …, f_{m}, where f_{i}(α_{1}, …, α_{m}) = α_{i}. These forms are a basis for the dual space V′ of V, so any element of V′ is a linear combination of them, and the procedure produces the corresponding linear combination of the rows.)

Now let the codeword v be obtained from the form f. Then

v ∘ v = ∑_{s∈S} \overline{f(s)}f(s) = ∑_{s∈S} f(s)^{3}.

Now f(s) = 0 if and only if s lies in a (m − 1)-dimensional subspace of GF(4)^{m} (the kernel of f). For the (4^{m} − 1)/3 − (4^{m−1} − 1)/3 = 4^{m−1} vectors s not in ker(f), we have f(s)^{3} = 1. Since there are an even number of such vectors, and the characteristic is 2, we have v ∘ v = 0 for all v ∈ C.

Now take any v, w ∈ C. Then, for any α ∈ GF(4), we have

0 = (v + αw) ∘ (v + αw) = (α + \overline{α})v ∘ w.

Choosing α = ω, we have α + \overline{α} ≠ 0, so v ∘ w = 0. Thus C is self-orthogonal.

Example Take m = 2. Then a generator matrix for D_{2}(4) is

[ \begin{matrix}0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & ω & \overline{ω} \end{matrix} ] ,

and the self-orthogonality is easily checked.

Remark A similar proof (left as an exercise) shows that the codes D_{m}(2) (for m ≥ 3) and D_{m}(3) (for m ≥ 2) are self-orthogonal with respect to the standard inner product on GF(q)^{n}, where q = 2, 3.

The argument fails for other field orders. Indeed, we have only defined the Hamming codes up to equivalence; and multiplying a coordinate by an arbitrary non-zero scalar preserves self-orthogonality only in the three cases q = 2, 3 (with the standard inner product) or q = 4 (with the Hermitian inner product). For multiplication of v_{i} by α has the effect of multiplying the contribution of the ith coordinate to the inner product by α^{2} (for the usual inner product) or α^{r+1} (for the Hermitian inner product, where q = r^{2}). Now the only fields where this factor is 1 for all choices of α are those given.

It can be shown, using the theory of cyclic codes, that a suitable choice of ‘dual Hamming code’ can be made from the equivalence class of such codes so that it is self-orthogonal (with respect to the appropriate inner product) in all cases except q = 2, m = 2. We refer the reader to MacWilliams and Sloane [12] for details.

The Hamming code H_{m}(q) has minimum weight 3, since it is 1-error-correcting (any two columns of its parity check matrix are linearly independent). The dual code D_{m}(q) has minimum weight q^{m−1}, since its non-zero words are defined by non-zero elements of V′, each of which vanishes on (q^{m} − 1)/(q − 1) − (q^{m−1} − 1)/(q − 1) = q^{m−1} one-dimensional subspaces of V.

11 Quantum Hamming codes

Recall that we are trying to construct a totally isotropic subspace \overline{S} of \overline{E} (a 2n-dimensional vector space over ℤ_{2} = GF(2)) such that \overline{S}^{⊥} \ \overline{S} has large q-weight, and dim(\overline{S}) = n − k.

First we construct yet another vector space. This is an n-dimensional vector space over the field F = GF(4). Since ω and \overline{ω} form a basis for F as vector space over GF(2), we can write any vector in this space in the form ωa + \overline{ω}b, where a and b are vectors of length n over GF(2). In other words, a, b ∈ V. Now the map ϕ : \overline{E} → F^{n} defined by

ϕ((a|b)) = ωa + \overline{ω}b

is a bijection, and is an isomorphism of GF(2)-vector spaces (if we regard F^{n} as a GF(2)-space by restricting scalars). Since ωa_{j} + \overline{ω}b_{j} ≠ 0 if and only if either a_{j} ≠ 0 or b_{j} ≠ 0, we have a very important property of ϕ: the q-weight of a vector (a|b) ∈ \overline{E} is equal to the Hamming weight of its image ϕ((a|b)) = ωa + \overline{ω}b ∈ F^{n}.

As in the last section, let ∘ be the Hermitian inner product on F^{n}. There is a trace map Tr from F to GF(2) defined by

Tr(α) = α + \overline{α},

so that Tr(0) = Tr(1) = 0 and Tr(ω) = Tr(\overline{ω}) = 1. The trace map is linear over GF(2). Now the map (x, y) ↦ Tr(x ∘ y) takes pairs of vectors in F^{n} to GF(2). We have:

Tr((ωa + \overline{ω}b) ∘ (ωa′ + \overline{ω}b′)) = a · b′ + a′ · b = (a|b) ∗ (a′|b′).

The proof of this fact is just calculation. Using the fact that the Hermitian inner product is linear in the first variable and semilinear in the second, and the fact that a ∘ b = a · b for a, b ∈ GF(2)^{n}, we have

(ωa + \overline{ω}b) ∘ (ωa′ + \overline{ω}b′) = a · a′ + \overline{ω}a · b′ + ωb · a′ + b · b′.

Taking the trace now gives the result (using the linearity of trace and the fact that Tr(1) = 0 and Tr(ω) = Tr(\overline{ω}) = 1).

Next we show that a subspace of F^{n} is totally isotropic (with respect to ∘) if and only if the corresponding subspace of \overline{E} is totally isotropic (with respect to ∗). The forward implication is clear. So suppose that W ≤ F^{n} is the image under ϕ of a totally isotropic subspace of \overline{E}. This means that Tr(x ∘ y) = 0 for all x, y ∈ W. Take x, y ∈ W, and let x ∘ y = α. Then Tr(α) = 0, and

Tr(ωα) = Tr((ωx) ∘ y) = 0

(since ωx ∈ W); it follows that α = 0.

To summarise: the space F^{n}, on restriction of scalars, becomes isomorphic to \overline{E}, by a map ϕ taking q-weight to Hamming weight; and a subspace of F^{n} is the image of a totally isotropic subspace of \overline{E} (with respect to ∗) if and only if it is totally isotropic (with respect to ∘). Of course, not every totally isotropic subspace of \overline{E} corresponds to a subspace of W. (The image under ϕ of a subspace of \overline{E} is a GF(2)-subspace but not necessarily a GF(4)- subspace.)

So, in order to construct a quantum error-correcting code, we need a subspace C of F^{n} such that C^{⊥} \ C has large minimum Hamming-weight (where C^{⊥} is defined by the Hermitian inner product ∘).

From the last section, we know that C = D_{m}(4) fills the bill. It has length n = (4^{m} − 1)/3, dimension m over GF(4) (hence 2m over GF(2)), satisfies C ≤ C^{⊥}, and [assuming something suitable inserted in the previous section] C^{⊥} \C has minimum H-weight 3. So we have a [[n, n−2m, 3]] quantum code. Indeed, for the corresponding \overline{S} = ϕ^{−1}(C) ≤ \overline{E}, \overline{S}^{⊥} \ \{0\} has minimum qweight 3, so the code is non-degenerate, in the sense defined at the end of Section 6.

Example Continuing our example in the last section, the subspace \overline{S} is spanned by the rows of the matrix

[ \begin{matrix}0 & 1 & 1 & 1 & 1 & | & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & | & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & | & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & | & 1 & 0 & 1 & 1 & 0 \end{matrix} ] .

(We have replaced each row x of the generator matrix of D_{2}(4) by the two rows ωx and \overline{ω}x and then applied the inverse of ϕ.) Then \overline{S}^{⊥} is spanned by \overline{S} and the two additional rows

[ \begin{matrix}0 & 0 & 1 & 1 & 0 & | & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & | & 0 & 0 & 1 & 0 & 1 \end{matrix} ] .

If Q is a non-degenerate [[n, k, d]] code and t = ⌊(d−1)/2⌋, then counting independent vectors in ℂ^{N} (N = 2^{n}) gives dimQ·|E| = 2^{k}[1+3(n choose 1)+ … + 3^{t}(n choose t)] ≤ 2^{n} [sorry, don’t find how to do binomial coeffs]. The example of the [[n, n − 2m, e]] code with n = (4^{m} − 1)/3 gives equality, so it saturates the quantum bound.

Appendix: Cryptography and factorisation

In this appendix we give a brief review of the concept of public-key cryptography, the RSA system (its most popular realisation), and the relevance a fast quantum algorithm for factorising large integers would have for this system. No attempts at rigorous definitions of complexity classes or proofs of the assertions will be given.

In any cryptosystem, the plaintext to be transmitted is encrypted by some algorithm depending on additional data called the key, to produce ciphertext. The recipient uses another algorithm to recover the plaintext from the ciphertext and key. The simplest example is the one-time pad, the only provably secure cipher system. The plaintext is first encoded as a string of bits of length n, say a_{1}a_{2} … a_{n}. The key consists of a string b_{1}b_{2} … b_{n} of n random bits, produced by some physical randomising process such as tossing coins. The encryption algorithm is bitwise addition; so the ciphertext is c_{1}c_{2} … c_{n}, where c_{i} = a_{i} + b_{i} (addition mod 2). The decryption algorithm in this case is identical to the encryption algorithm: add the key bitwise (since c_{i} + b_{i} = a_{i}). The ciphertext is itself a random string of bits, so an interceptor without knowledge of the key is unable to gain any information. (The security of this system was proved by Shannon [15].)

Note that both the sender and the recipient must have the key, which must be kept secret from the interceptor. The key must either be shared on a previous occasion, or conveyed by a channel which is known to be secure.

Public-key cryptography was invented by Diffie and Hellman [7] in 1975. (In fact, the same idea had been invented six years earlier by James Ellis, an employee of GCHQ, who was unable to publish it because of his employment: see [18].) The idea is that the encryption algorithm and the key are made public, but the decryption is so demanding of computational resources that this knowledge is of no use to the interceptor. However, the recipient (who publishes the key) has some additional information, the secret key, which makes the decryption much easier.

More formally, let M be the set of plaintext messages, C the set of ciphertext messages, and K the set of keys. An encryption system consists of a pair of functions, encryption e : M × K → C, and decryption d : C × K → M, such that d(e(m, k), k) = m for all m ∈ M and k ∈ K. A public-key system also has a set S of secret keys, and an inverse pair of functions p : S → K and q : K → S such that

• computation of e(m, k) and p(s) are easy;

• computation of d(c, k) and q(k) are difficult;

• if q(k) is known, then computation of d(c, k) is easy (in other words, computation of d(c, p(s)) is easy).

Each user i of the system selects an element s_{i} ∈ S, computes k_{i} = p(s_{i}), and publishes the result. If user j wants to send a message m to user i, she looks up k_{i} in the public directory, computes c = e(m, k_{i}), and transmits this ciphertext. Now i computes d(m, q(s_{i})) = d(m, k_{i}) = m. An interceptor knows c and k_{i} but is faced with the difficult tasks of either computing d(m, k_{i}) directly or computing s_{i} = q(k_{i}).

The RSA system works as follows. Each secret key consists of a pair p, q of large prime numbers (of hundreds of bits), and an integer a coprime to (p − 1)(q − 1). From this, by Euclid’s algorithm, one computes b such that ab ≡ 1 (mod (p − 1)(q − 1)). Now the public key is the pair (N, a), where N = pq. The encryption algorithm takes the message m, which is encoded as an integer less than N, and computes the ciphertext c = m^{a} mod N. The possessor of the secret key can decrypt this by raising it to the power b mod N, since

c^{b} = m^{ab} ≡ m^{1} = m mod N.

(We use the fact that ϕ(N) = (p − 1)(q − 1), and Fermat’s Little Theorem asserting that m^{ϕ(N)} ≡ 1 (mod N).

Of the interceptor’s two strategies, the second (calculating the secret key) involves factorising N, so that b can also be calculated. It can be shown (we omit the details) that the first strategy (decrypting using the public key) is also equivalent to factorising N. An intermediate strategy would be to find b such that m^{ab} ≡ m (mod N) for all m. This amounts to finding u such that m^{u} ≡ 1 (mod N), for then b can be found by the Euclidean algorithm. But the smallest such u is the least common multiple of (p − 1) and (q − 1); knowledge of this determines (p − 1)(q − 1) and hence p and q.

So the security of the method depends on the assumption that factorising large numbers is a hard problem.

The factorisation problem has been studied for centuries, but the best known ‘classical’ algorithm for it has fractional exponential complexity.

As we mentioned, Shor [17] found a probabilistic algorithm which runs in quantum polynomial time. It depends on the following observation. Suppose that we have computed the order of x mod N, the smallest number t such that x^{t} ≡ 1 (mod N). Suppose that t is even, say t = 2r. Then N divides x^{t} − 1 = (x^{r} − 1)(x^{r} + 1). If x^{r} is not congruent to −1 mod N, then both x^{r} − 1 and x^{r} + 1 have factors in common with N. We can find the g.c.d.s of the pairs (N, x^{r} − 1) and (N, x^{r} + 1) by Euclid’s algorithm; then we know two different factors of N, and hence the complete factorisation in the RSA case.

The basic idea of quantum computation is to exploit the inherent parallelism of quantum systems. Suppose, for example, that we want to compute 2^{n} values f(0), f(1), …, f(2^{n} − 1) of a function simultaneously. We represent the integer i by the binary vector v ∈ V = ℤ_{2}^{n} which is its expression in base 2. Now, if n qubit registers are available, we can load them with a superposition of the states e_{v}, for v ∈ V, as follows: first load each register with 0 (so that we have state e_{0}); then apply the Hadamard transforma-

tion with matrix (1/\sqrt{2}) [ \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} ] (corresponding to a 45^{∘} rotation of the

2-dimensional Hilbert space) to each qubit. The resulting state is

\frac{1}{\sqrt{2^{n}}} ∑_{v∈V} e_{v}.

Now suppose that some quantum computation replaces e_{v} by a state representing f(i), where v represents the integer i. Then, by the linearity of the Schrödinger equation, the same computation replaces the above superposition by a superposition of the values f(i) for i = 0, …, 2^{n} − 1. In the factorisation algorithm, we take f(i) = x^{i} (mod N), where 2^{n} ≥ N and x is some chosen integer coprime to N.

The last stage involves finding the period of f from the above superposition, which is done by use of the discrete Fourier transform. The Fourier transform of f is concentrated on multiples of the period, so an observation of the result will with high probability give a small multiple of the period.

Let us take as an example the current objective of quantum computing, the factorisation of 15. We take x = 2. Suppose that we have 8 qubit registers arranged in two banks of four, so that states of the system have the form

∑_{v,w∈V} a_{vw}(v ⊗ w)

in the space ℂ^{2^{4}} ⊗ ℂ^{2^{4}}. For convenience we write e_{i} in place of e_{v}, where i is the integer in the range [0, 15] whose base 2 representation is v. We begin with the state e_{0} ⊗ e_{0} (that is, all registers contain zero). Then by applying a Hadamard transform to each of the first four qubits, we obtain (up to normalisation) (∑_{i∈[0,15]} e_{i})⊗e_{0}. The crucial part of the computation replaces e_{i} ⊗ e_{0} with e_{i} ⊗ e_{2^{i} mod 15}. Apart from normalisation, the state is now

(e_{0} + e_{4} + e_{8} + e_{12}) ⊗ e_{1} + (e_{1} + e_{5} + e_{9} + e_{13}) ⊗ e_{2} + · · · .

We extract the period 4 from the first four registers by a discrete Fourier transform. Now we know that 15 divides (2^{4} − 1) = (2^{2} − 1)(2^{2} + 1) = 3 · 5, so the two factors of 15 are (15, 3) = 3 and (15, 5) = 5.

See Shor [16, 17] for further details.

Physical constraints limit the size of any quantum computer of a type so far proposed to at most about 30 qubits, and also place severe limitations on the number of computational steps which can be carried out. The way round this is to design a fault-tolerant computer, in which errors introduced by the gates and buses are corrected faster than new errors are introduced. This is theoretically possible only if the reliability of the components is above a certain threshold. This threshold has not yet been achieved.

For further reading on quantum computation, see the forthcoming book of Lo et al. [11].

References

[1] C. H. Bennett and P. W. Shor, Quantum information theory, IEEE Trans. Inform. Theory (1998).

[2] A. R. Calderbank, P. J. Cameron, W. M. Kantor and J. J. Seidel, ℤ_{4}- Kerdock codes, orthogonal spreads, and extremal Euclidean line systems, Proc. London Math. Soc. (3) 75 (1997), 436–480.

[3] A. R. Calderbank, E. M. Rains, P. W. Shor and N. J. A. Sloane, Quantum error correction via codes over GF(4), IEEE Trans. Inform. Theory, 44 (1998), 1369–1387.

[4] A. R. Calderbank, E. M. Rains, P. W. Shor and N. J. A. Sloane, Quantum error correction and orthogonal geometry, Phys. Rev. Lett., 78 (1997), 405–409.

[5] A. R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist, Phys. Rev. A 54 (1995), 1098–1106.

[6] R. Cleve and D. Gottesman, Efficient computations of encodings for quantum error correction, Phys. Rev. A, 56 (1997) 76–82.

[7] W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory 22 (1976), 644–654.

[8] R. A. Fisher, The theory of confounding in factorial experiments in relation to the theory of groups, Ann. Eugenics 11 (1942), 341–353.

[9] R. A. Fisher, A system of confounding for factors with more than two alternatives, giving completely orthogonal cubes and higher powers, Ann. Eugenics 12 (1945), 2283–290.

[10] D. Gottesman, Class of quantum error-correcting codes saturating the quantum Hamming bound, Phys. Rev. A, 54 (1996), 1862–1868.

[11] H.-K. Lo, S. Popescu and T. P. Spiller (eds.), Introduction to Quantum Computation, in press.

[12] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Publishing Co., Amsterdam, 1977.

[13] J. Preskill, Lecture notes for Physics 229 at Caltech,

http://theory.caltech.edu/~preskill/ph229.

[14] R. L. Rivest, A. Shamir and L. Adelman, A method of obtaining digital signatures and public-key cryptosystems, Comm. Assoc. Comput. Mach. 21 (1978), 120–126.

[15] C. E. Shannon, Communication theory of secrecy systems, Bell Systems Tech. J. 28 (1949), 657–715.

[16] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Computing 26 (1997), 1484–1509.

[17] P. W. Shor, Quantum Computing, ICM 1998 lecture,

http://www.research.att.com/~shor/papers/ICM.ps.

[18] P. Wayner, British document outlines early encryption discovery, New York Times, 24 December 1997.

[19] D. Welsh, Codes and Cryptography, Oxford University Press, Oxford, 1988.

[20] W. H. Zurek, Decoherence and the transition from quantum to classical, Physics Today 44 (1991), 36–44.