Good quantum error-correcting codes exist.

A. R. Calderbank and Peter W. Shor

AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ 07974

(Submitted September 12, 1995)

arXiv:quant-ph/9512032v2 16 Apr 1996

Abstract

A quantum error-correcting code is defined to be a unitary mapping (encod-

ing) of k qubits (2-state quantum systems) into a subspace of the quantum

state space of n qubits such that if any t of the qubits undergo arbitrary

decoherence, not necessarily independently, the resulting n qubits can be

used to faithfully reconstruct the original quantum state of the k encoded

qubits. Quantum error-correcting codes are shown to exist with asymp-

totic rate k/n = 1 − 2H2 (2t/n) where H2 (p) is the binary entropy function

−p log2 p − (1 − p) log2 (1 − p). Upper bounds on this asymptotic rate are

given.
PACS numbers: [Link]

Typeset using REVTEX

1
 I. INTRODUCTION

With the realization that computers that use the interference and superposition principles

of quantum mechanics might be able to solve certain problems, including prime factorization,
exponentially faster than classical computers [1], interest has been growing in the feasibility
of these quantum computers, and several methods for building quantum gates and quantum
computers have been proposed [2,3]. One of the most cogent arguments against the feasi-

bility of quantum computation appears to be the difficulty of eliminating error caused by

inaccuracy and decoherence [4]. Whereas the best experimental implementations of quan-
tum gates accomplished so far have less than 90% accuracy [5], the accuracy required for
factorization of numbers large enough to be difficult on conventional computers appears to
be closer to one part in billions. We hope that the techniques investigated in this paper can

eventually be extended so as to reduce this quantity by several orders of magnitude.

In the storage and transmission of digital data, errors can be corrected by using error-
correcting codes [6]. In digital computation, errors can be corrected by using redundancy;
in fact, it has been shown that fairly unreliable gates could be assembled to form a reliable

computer [7]. It has widely been assumed that the quantum no-cloning theorem [8] makes
error correction impossible in quantum communication and computation because redun-
dancy cannot be obtained by duplicating quantum bits. This argument was shown to be in
error for quantum communication in Ref. [9], where a code was given that mapped one qubit

(two-state quantum system) into nine qubits so that the original qubit could be recovered
perfectly even after arbitrary decoherence of any one of these nine qubits. This gives a
1
quantum code on 9 qubits with rate 9
that protects against one error. Here we show the
existence of better quantum error-correcting codes, having higher information transmission
rates and better error-correction capacity. Specifically, we show the existence of quantum

error-correcting codes encoding k qubits into n qubits that correct t errors and have asymp-
totic rate 1 − 2H2 (2t/n) as n → ∞. These codes work not by duplicating the quantum state
of the encoded k qubits, but by spreading it out over all n qubits so that if t or fewer of

2
these qubits are measured, no information about the quantum state of the encoded bits is
revealed and, in fact, the quantum state can be perfectly recovered from the remaining n − t
qubits.

Suppose that we have a coherent quantum state of k qubits that we wish to store using
a physical quantum system which is subject to some decoherence process. For example,
during computation on the quantum computer proposed by Cirac and Zoller [3], we would
need to store quantum information in entangled electronic states of ions held in an ion

trap. The decoherence time of the quantum state of k entangled qubits is in general 1/k
of the decoherence time of one qubit (this makes the optimistic assumption that coherence
between different qubits is as stable as coherence of a single qubit). Thus, one might expect
that the best way to store the state of k entangled qubits is to store them in k physical

qubits. Our results show that if we use quantum error-correcting codes, it is possible to
store the k qubits in n > k qubits so that the decoherence time for the encoded quantum
state is a small constant fraction of the decoherence time of one qubit. These results thus
show that some measurable non-local properties of entangled systems are much more stable

under decoherence than is the entire entangled system.

Physical quantum channels will be unlikely to leave n − t qubits perfectly untouched
and subject the remaining t qubits to decoherence. To analyze the behavior of our error-
correcting code for physical quantum channels, we must make some assumptions about the
decoherence process. In Section VI, we will show that our error correction method performs

well if the decoherence of different qubits occurs independently, i.e., if each of the qubits
is coupled to a separate environment. Our error-correction method will actually work for
more general channels, as it can tolerate coupled decoherence behavior among small groups
of qubits.

The lower bound of 1−2H2 (2t/n) shown in our paper should be compared with theoretical
upper bounds of

h  q i
1
min 1 − H2 (2t/3n), H2 2
+ (1 − t/n)t/n

3
for t/n < 12 , and 0 for t/n ≥ 12 . These are obtained from bounds on the quantum information
capacity of a quantum channel, which we derive in Section VI from results of Refs. [10,11].
These bounds are plotted in Fig. 1 in Section VI.

II. DEFINITIONS

Our constructions of quantum error-correcting codes rely heavily on the properties of

classical error-correcting codes. We will thus first briefly review certain definitions and

properties related to binary linear error-correcting codes. We only consider vectors and
codes over F2 , the field of two elements, so we have 1 + 1 = 0. A binary vector v ∈ F2 with
d 1’s is said to have Hamming weight d, denoted by wt(v) = d. The Hamming distance
dH (v, w) between two binary vectors v and w is wt(v + w). The support of a vector v,
denoted by supp(v), is the set of coordinates of v where the corresponding entry is not 0,

that is, supp(v) = {i : vi 6= 0}. Suppose that S is a set of coordinates. Then v|S denotes
the projection of v onto S, i.e., the vector that agrees with v on the coordinates in S and
is 0 on the remaining coordinates. For a binary vector E we use v|E to mean v|supp(E) . We
also use e  E to mean that supp(e) ⊆ supp(E).

A code C of length n is a set of binary vectors of length n, called codewords. In a linear

code the codewords are those vectors in a subspace of Fn2 (the n-dimensional vector space
over the field F2 on two elements). The minimum distance d = d(C) of a binary code C is
the minimum distance between two distinct codewords. If C is linear then this minimum

distance is just the minimum Hamming weight of a nonzero codeword.

A linear code with length n, dimension k, and minimum distance d is called an [n, k, d]
code. For a code C with minimum distance d, any binary vector in Fn2 is within Hamming
distance t = ⌊ d−1
2
⌋ of at most one codeword; thus, a code with minimum distance d can
correct t errors made in the bits of a codeword; such a code is thus said to be a t error-

correcting code. The rate R of a linear code of length n is dim(C)/n; this is the ratio of the
information content of a codeword to the information content of an arbitrary string of length

4
n. The dual code C ⊥ of a code C is the set of vectors of perpendicular to all codewords, that
is, C ⊥ = {v ∈ Fn2 : v · c = 0 ∀c ∈ C}. From linear algebra, dim(C) + dim(C ⊥ ) = n.
In this paper, we will use the [7, 4, 3] Hamming code as an example to illustrate our

construction of quantum error-correcting codes. This code contains the following 16 binary
vectors of length 7:

0000000, 0001011, 0010110, 0011101,

0100111, 0101100, 0110001, 0111010,
(1)
1000101, 1001110, 1010011, 1011000,
1100010, 1101001, 1110100, 1111111.
The minimum distance is the minimum Hamming weight of a non-zero codeword, which is
3, so this is a one-error correcting code. It is easily verified that the dual code consists of

all vectors in the Hamming code with an even weight.

The quantum Hilbert space H2n over n qubits is the complex space generated by basis
vectors |b0 i, |b1 i, . . ., |b2n −1 i where bi is the representation of the number i in binary. This
Hilbert space has a natural representation as a tensor product of n copies of H2 , with the

ith copy corresponding to the ith bit of the basis vectors. We refer to each of these copies
of H2 as a qubit.
We define a quantum error-correcting code Q with rate k/n to be a unitary mapping of
H2k into H2n . Strictly speaking, this is actually a unitary mapping of H2k into a 2k -dimensional
subspace of H2n ; it can alternatively be viewed as a unitary mapping of H2k ⊗ H2n−k into H2n ,

where the quantum state in H2n−k is taken to be that where all the qubits have quantum
state |0i. In our model of error analyzed in Section IV, we will assume that the decoherence
process affects only t bits; that is, the decoherence is modeled by first applying an arbitrary
unitary transformation D to the space consisting of the tensor product H2t ⊗ Henv of any t

of the qubits and some arbitrary Hilbert space Henv designating the environment, and then
tracing over the environment Henv to obtain the output of the channel, which will thus in
general be an ensemble of states in H2k . We say that a quantum code can correct t errors
if the original state |xi ∈ H2k can be recovered from the decohered encoded state DQ|xi

5
by applying a unitary transformation R (independent of D) to H2n ⊗ Hanc , where Hanc is a
Hilbert space representing the state of an ancilla (i.e., a supplementary quantum system). It
turns out that if our quantum code will correct an arbitrary decoherence of t or fewer qubits,

it will also be able transmit information with high fidelity for a large class of channels with
physically plausible decoherence processes; this is discussed in Section VI.
Since the error correction must work for any encoded state Q|xi, the property of being
a quantum error-correcting code depends only on the subspace QH2k of H2n , and not on

the actual mapping Q. However, for ease of explanation, we will nonetheless define an
orthogonal basis of this subspace of H2n , which can be used to obtain an explicit mapping
Q, and call the elements of this basis codewords.

III. QUANTUM CODES

We will now define our quantum code. Suppose that we have a linear code C1 ⊂ Fn2 . We
let HC1 be the subspace of H2n generated by vectors |ci with c ∈ C1 . Let M be a generator
matrix for C1 ; this means that C1 is the row space of M, so that vM ranges over all the
dim(C1 )
codewords in C1 as v ranges over all vectors in F2 . For w ∈ Fn2 , we define a quantum

state |cw i by

|cw i = 2− dim(C1 )/2 (−1)vM w |vMi.

X
(2)
dim(C1 )
v∈F2

dim(C1 )
Note that if w1 + w2 ∈ C1⊥ , then |cw1 i = |cw2 i, since vMw1 = vMw2 for all v ∈ F2 .

Further note that hcw1 |cw2 i = 0 if w1 + w2 6∈ C1⊥ . This follows since v (−1)
vM w
= 0 unless
P

dim(C1 )
vMw = 0 for all v ∈ F2 Thus, for w ∈ Fn2 /C1⊥ the vectors |cw i form a basis for the space
HC1 . (Here F2n /C1⊥ stands for the cosets of C1⊥ in Fn2 , which are the sets C1⊥ +w where w ∈ Fn2 ;
there are 2dim(C1 ) of these cosets and they form the natural index set for the quantum states

|cw i.)
Suppose now that we have another linear code C2 with {0} ⊂ C2 ⊂ C1 ⊂ Fn2 . Our
quantum code will be constructed using codes C1 and C2 . We define the codewords of our

6
quantum code QC1 ,C2 as the set of |cw i for all w ∈ C2⊥ , Recall that two codewords |cw i and
|cw′ i are equal if w + w ′ ∈ C ⊥ . The natural index set for the codewords is thus over C2⊥ /C1⊥ ,
the cosets of C1⊥ in C2⊥ . This code thus contains 2dim(C1 )−dim(C2 ) orthogonal vectors. Since

its length is n qubits, it has rate (dim(C1 ) − dim(C2 ))/n. To construct a quantum error-
correcting code from the Hamming code given in Eq. (1), we will take C1 to be this code
and C2 to be C1⊥ . Thus, dim(C1 ) = 4 and dim(C2 ) = 3, so our quantum error-correcting code
will map 4 − 3 = 1 qubit into 7 qubits. There are thus two codewords. The first is
1
|c0 i = |0000000i + |0011101i + |0100111i + |0111010i
4
+|1001110i + |1010011i + |1101001i + |1110100i (3)

+|0001011i + |0010110i + |0101100i + |0110001i


+|1000101i + |1011000i + |1100010i + |1111111i ,

and the second is

1
|c1 i = |0000000i + |0011101i + |0100111i + |0111010i
4
+|1001110i + |1010011i + |1101001i + |1110100i (4)

−|0001011i − |0010110i − |0101100i − |0110001i


−|1000101i − |1011000i − |1100010i − |1111111i .

Note that in |c1 i all the codewords of the Hamming code with an odd weight have a negative
amplitude, and all the codewords with even weight have positive amplitude. This is the effect

of the (−1)vM w term in Eq. (2).

We will show that if C1 and C2⊥ have minimum distance d, then the quantum code QC1 ,C2
can correct t = ⌊ d−1
2
⌋ errors. (For our example code, C1 = C2⊥ has minimum distance 3,
so our quantum code will correct one error.) In the remainder of this section, we will give

some intuition as to why this should be true; while in the next section, we will work out this
calculation in detail.
To show why our codes are error-correcting, we must first give another representation of
our codewords. If we perform the following change of basis,

7
 |0i → √1 (|0i + |1i) (5)
2

|1i → √1 (|0i − |1i),

2

to each of the bits of our codeword |cw i we obtain the state

|sw i = 2(dim(C1 )−n)/2

X
|u + wi. (6)
u∈C1⊥

We can see this since if |xi is any basis state in the rotated basis given by Eq. (5), then

hx|cv i = 2−(n+dim C1 )/2 (−1)vM (w+x) ,

X
(7)
dim(C1 )
v∈F2

and this sum is 0 unless w + x ∈ C1⊥ . Letting u = w + x, we get Equation (6). For our
example quantum code,

1 
|s0 i = √ |0000000i + |0011101i + |0100111i + |0111010i (8)
2 2

+|1001110i + |1010011i + |1101001i + |1110100i

and

1 
|s1 i = √ |0001011i + |0010110i + |0101100i + |0110001i (9)
2 2

+|1000101i + |1011000i + |1100010i + |1111111i .

We can now see how these codes are able to correct errors. In the |cw i representation,
all the codewords are superpositions of basis vectors |vi with v ∈ C1 . Thus, any t bit errors
(those errors taking |0i → |1i and |1i → |0i) can be corrected by performing a classical

error-correction process for the code C1 in the original basis. In the |sw i representation, all
the codewords are superpositions of basis vectors |vi with v ∈ C2⊥ . Thus, any t bit errors
in the rotated basis can be corrected by performing a classical error-correction process for
the code C2⊥ in the rotated basis. However, phase errors in the original basis (errors taking

|0i → |0i and |1i → −|1i) are bit errors in the rotated basis and vice versa. Thus, our
quantum code can correct t bit errors and t phase errors in the original basis.
The correction process we use for our quantum error-correcting codes is indeed to first
correct bit errors in the |cv i basis classically and then to correct bit errors in the |sv i basis

8
classically. It remains to be shown that the correction process for the bit errors does not
interfere with the correction process for the phase errors, and that arbitrary non-unitary
errors on t or fewer quantum bits of our code will also be corrected by this procedure. This

is done through calculations which are performed in Section IV of our paper.

As in Ref. [9], we correct the error by measuring the decoherence without disturbing
the encoded information. Intuitively, what we do is to measure the decoherence without
observing the encoded state; this then lets us correct the decoherence while leaving the

encoded state unchanged. In our decoding procedure, we thus learn which qubits had bit
errors and which had phase errors, which tells us something about the decoherence process
but which gives no information about our encoded state. Linear codes are very well suited
for this application: each codeword has the same relation to all the other words in the code,

and this property is what enables us to measure the error without learning which codeword
it is that is in error.
Since this paper was submitted, we learned that related work has been done by Steane
[12]. Steane generates his quantum code using codewords

|s′w i = 2− dim(C2 )/2

X
|v + wi, (10)
v∈C2

where w is chosen from C1 /C2 . This is the same as our |sw i basis if the codes C1 and C2⊥ are
interchanged. It should also be noted that these codewords |s′w i generate exactly the same
subspace of H2n as the codewords |cw i given by Eq. 2, and thus effectively give a different
basis for the same quantum code.

IV. DECODING QUANTUM CODES

In this section we will show that errors in any t qubits of our quantum codes can be
corrected by first correcting bit errors in the |ci basis, and then correcting bit errors in the
|si basis. For this section and the remainder of this paper, we will assume for simplicity that

dim(C1 ) = n−k and dim(C2 ) = k; thus, the rate of our codes will be 1−2k/n. However, all of

9
our results are easily extendable to quantum codes derived from classical codes C2 ⊂ C1 ⊂ Fn2
of any dimension.
In order to prove that errors in quantum codes can be corrected, we first need a lemma

about purely classical codes.

Lemma 1. Suppose that C is a binary linear code of length n. Let e, E ∈ Fn2 , with e  E
and wt(E) < d(C ⊥ ). Then there exists a vector ve ∈ C such that ve |supp(E) = e.
Proof. The projection of C onto E has to have full rank, because otherwise C ⊥ would

contain a vector w with wt(w) ≤ wt(E) < d(C ⊥ ). ✷

We now need the following lemma about the states |cw i.
Lemma 2. Suppose that C1 has minimum distance d. Let e, E ∈ Fn2 with e  E. Let
P be the projection onto the subspace of H2n generated by all |vi where v is in the set

{v ∈ Fn2 : v|E = e}, that is, with v equal to e on supp(E). Then

hcw1 |P |cw2 i = 2−(n−k) (−1)vM (w1 +w2 )

X
(11a)
v:vM |E =e

(−1)e·(c+w1 +w2 ) /2wt(E) if ∃c ∈ C1⊥ such that c + w1 + w2  E,



= (11b)
0 otherwise.




Proof. From the definition of |cw i in Eq. (2), it is straightforward to show Eq. (11a). We
must now show that this is equal to Eq. (11b). Since wt(e) < d(C1⊥ ), by Lemma 1 there is
a vector ve such that ve M|E = e. We can obtain the linear space {v ∈ F2n−k : v|E = e} by

taking every vector in the set {v ∈ F2n−k : v|E = 0} and adding the vector ve . Using this
substitution in Eq. (11a) gives

hcw1 |P |cw2 i = 2−(n−k) (−1)(v+ve )M (w1 +w2 )

X
(12a)
v:vM |E =0

= 2−(n−k)(−1)ve M (w1 +w2 ) (−1)vM (w1 +w2 ) .

X
(12b)
v:vM |E =0

Now, because the set {vM : vM|E = 0} is an n − k − wt(E) dimensional subspace of

Fk2 , the sum (12b) is 0 unless vM(w1 + w2 ) = 0 for all vM in this subspace. It is clear that

10
if there is a c ∈ C1⊥ such that w1 + w2 + c  E, then vM(w1 + w2 ) = 0 if vM|E = 0, and
ve M(w1 + w2 ) = e · (c + w1 + w2 ). This shows the first part of Eq. (11b).
We now prove the other direction. Suppose that vM(w1 + w2 ) = 0 for all v with

vM|E = 0. Let ej be the vector that is 1 on the jth coordinate of E and 0 on the other
coordinates. We know from Lemma 1 that there is a vector vj ∈ F2n−k such that vj M|E = ej .
Pwt(E)
Let σj = vj M(w1 + w2 ). We consider the vector c′ = w1 + w2 + j=1 σj ej ; we will show
that this vector satisfies the conditions for the c in Eq. (11b). Clearly, w1 + w2 + c′  E. We

need also to show that c′ ∈ C1⊥ . Consider any vector v ∈ F2n−k . We can decompose it into
Pwt(E)
v = v0 + i=1 αi vi where v0 M|E = 0, and αi is 0 or 1. Note that vi Mej = δ(i, j) where δ
is the Kronecker delta function. Now,
wt(E) wt(E)
vMc′ = (v0 +
X X
αi vi )M(w1 + w2 + σj ej ) (13a)
i=1 j=1
wt(E) wt(E)
X X
=( αi vi )M(w1 + w2 + σj ej ) (13b)
i=1 j=1
wt(E) wt(E)
X X
= αi vi M(w1 + w2 ) + αi σi (13c)
i=1 i=1
= 0,

proving the second part of Eq. (11b). The terms containing v0 vanish in Eq. (13a) because
v0 M(w1 +w2 ) = 0 since v0 M|E = 0, and v0 Mei = 0 since ei ≺ E. The two terms in Eq. (13c)
cancel because of the definition of σi . ✷
We are now ready to prove the following theorem.

Theorem 1. If C1 and C2⊥ are both linear [n, n − k, d] codes with {0} ⊂ C2 ⊂ C1 ⊂ Fn2 ,
then the quantum code QC1 ,C2 is a t-error correcting code, where t = ⌊ d−1
2
⌋.
Proof. We show how to correct any t errors. Let us start with a codeword |cw i for w ∈ C2⊥ .
Now, let E be the binary vector such that supp(E) is the set of qubits that have decohered.

By our hypothesis that at most t qubits decohere, we can take wt(E) = t. We denote states
of the environment by |ai i. Since the decoherence only operates on those qubits in supp(E),
the most general decoherence D is a unitary process operating on a binary vector u and the
initial state of the environment |a0 i as follows:

11
 X
D|u, a0 i = |u + ei|au|E ,e i, (14)
eE

where the states of the environment |ai i are not necessarily normalized. Now, we let this
decoherence act on |cw i|a0 i. We get

D|cw , a0 i = 2−(n−k)/2 (−1)vM w

X X
|vM + ei|avM |E ,e i. (15)
v∈Fn−k eE
2

Now, we know vM ∈ C1 , which is a code with minimum distance d > 2wt(e). Thus, we

can restore vM + e to a unique codeword vM ∈ C1 . Intuitively, this corrects bits that have
flipped from 0 to 1 or vice versa. We can do this using a unitary operator Rf provided we
make the operation reversible; to do this we record the error e in a set of ancilla qubits A.
After this process, the quantum state of our system is

Rf D|cw i = 2−(n−k)/2 (−1)vM w

X X
|vMi|avM |E ,e i|Ae i. (16)
v eE

Note that since vM ∈ C1 , we have now corrected our state to some state in the Hilbert space
HC1 . Recall that the vectors |cu i with u ∈ Fn2 generated HC1 . What we do now is to consider

the Hilbert space HC1 in terms of the basis elements |cu i for u ∈ Fn2 /C1⊥ instead of the basis
elements |vMi. We do this by substituting the identity

|vMi = 2−(n−k)/2 (−1)vM u |cu i

X
(17)
u∈Fn ⊥
2 /C1

in Eq. (16). This gives the same type of effect as the change of basis in Eq. (5) in that it
produces a representation in which it is easier to deal with phase errors. The substitution

(17) gives the equation

Rf D|cw i = 2−(n−k) (−1)vM w (−1)vM u |cu i

X X X
|avM |E ,e i|Ae i, (18)
v u eE

which can be rewritten as

Rf D|cw i = 2−(n−k) (−1)vM w (−1)vM u

X X X X
|Ae i |ae′ ,e i |cu i (19)
eE e′ E u v:vM |E =e′

Now, by Lemma 2, the inner sum is 0 unless there exists c ∈ C1⊥ for which c + w + u  E.
This means that |cw i can only decohere to |cu i if there is a c ∈ C1⊥ such that wt(u+w+c) ≤ t.

12
We now show this means that for each |cu i there is a unique |cw i with w ∈ C2⊥ /C1⊥ which it
could have arisen from. Suppose that we have two such w’s, w1 and w2 with w1 + u + c1 = e1
and w2 + u + c2 = e2 . Then,

e1 + e2 = w1 + w2 + c1 + c2 ∈ C2⊥ . (20)

However,

wt(e1 + e2 ) ≤ wt(e1 ) + wt(e2 ) ≤ 2t. (21)

But C2⊥ has minimum distance d > 2t; thus e1 = e2 , so w1 + w2 ∈ C1⊥ and |cw1 i = |cw2 i.

This means that we can unitarily express the state in Eq. (19) in terms of |cu i, where
u ∈ Fn2 /C1⊥ , and then correct the state |cu i to |cw i, since there is at most one w with
dH (w, u) < t. As before, to unitarily correct |cu i to |cw i we need to use a second ancilla A′
to record which bits we needed to flip to get from u to w. These flipped bits correspond to

phase errors in the original basis. Denoting this correction operator by Rp , we get

′′
Rp Rf D|cw i = 2−(n−k) (−1)vM w (−1)vM (w+e ) |cw i|A′e′′ i
X X X X
|Ae i |ae′ ,e i
eE e′ E v:vM |E =e′ e′′ E
′′
= 2−(n−k) |cw i (−1)vM e
X X X X
|Ae i |ae′ ,e i |Ae′′ i (22)
eE e′ E e′′ E v:vM |E =e′
′ ′′
= 2−wt(E) |cw i |A′e′′ i (−1)e ·e |ae′ ,e i,
X X X
|Ae i
eE e′′ E e′ E

which is just |cw i tensored with a state of the ancillae and the environment that does not
depend on w. We have thus unitarily restored the original state and corrected t decohered
bits. ✷

V. WEAKLY SELF-DUAL CODES

To show that a family of codes contains codes that meet the Gilbert-Varshamov bound
we can often employ a very simple greedy argument; this argument appears in Ref. [6], pp.
557–558 (proof of Thm. 31 of Chap. 17).
Lemma 3. Let φi be a set of [ni , ki ] codes such that

13
 1. ki /ni > R

2. each nonzero vector of length ni belongs to the same number of codes in φi .

Then there are codes in the family that asymptotically meet the Gilbert-Varshamov bound:

R ≥ 1 − H2 ( nd ) as n → ∞ (23)

Proof. Let Wi be the number of codes in φi that contain a particular vector v. By

hypothesis,

(2ni − 1)Wi = (2ki − 1)|φi |. (24)

The number of vectors with weight less than d is

d−1
!
X ni
. (25)
j=0 j

If
d−1
!
ni
< Wi (2ni − 1)/(2ki − 1) = |φi |
X
Wi (26)
j=0 j

then there is a code in φi with minimum distance ≥ d. ✷

This proof is not constructive in that it does not produce codes satisfying this bound,
but merely shows that they exist. In fact, explicit constructions for classical codes that

attain the Gilbert–Varshamov bound asymptotically are not known.

Consider towers of codes as shown below:

{0} ⊆ hh1n ii ⊆ C ⊆ C ⊥ ⊆ F2n (27)

where dim C = k and dim C ⊥ = n − k. Here hh1n ii denotes the subspace of Fn2 generated by
the vector 1n containing all ones. The codes C and C ⊥ correspond to C2 and C1 , respectively,
in the Section III; we have now added the requirement that C1⊥ = C2 . We follow MacWilliams
et al. [13]. They call a code weakly self-dual if

14
 hh1n ii ⊆ C ⊆ C ⊥ . (28)

Given a vector v with even weight we need that the number of k-dimensional weakly self-dual
codes for which v ∈ C ⊥ is independent of v. In other words, the number of k-dimensional

weakly self-dual codes C contained in a given hyperplane v ⊥ is independent of v.

We apply Theorem 2.1 of Ref. [13] (actually a stronger statement established in the
proof).
Let σn,k,s be the number of k-dimensional weakly self-dual codes C[n,k] that contain a

given s-dimensional code C[n,s]. Then the numbers σn,k,s are independent of the code C[n,s]
that was chosen.
⊥ ⊥
We separate the case v ∈ C[n,k] ⊆ C[n,k] from the case v ∈ C[n,k] \C[n,k] . The number of
k-dimensional weakly self-dual codes C[n,k] for which v ∈ C[n,k] is just σn,k,2, the number of
codes containing the 2-dimensional space hh1n , vii. Next we consider pairs (C[n,k] , v) where
⊥
C[n,k] is a k-dimensional weakly self-dual code and v ∈ C[n,k] \C[n,k] . In this case C[n,k] and v
generate a (k − 1)-dimensional weakly self-dual code C[n,k+1] containing the 2-dimensional
space hh1n , vii. The number of choices for C[n,k+1] is σn,k+1,2 . Every code C[n,k+1] contains 2k
k-dimensional weakly self-dual codes of which 2k−1 do not contain the 2-dimensional space

hh1n , vii. Hence given a vector v with even Hamming weight, the number of k-dimensional
weakly self-dual codes contained in v ⊥ is independent of v. This is all that is needed to
apply the greedy argument used to establish the Gilbert-Varshamov bound.
The statement that there are codes meeting the Gilbert–Varshamov bound is that given

a ratio d/n (where d denotes minimum distance), we may achieve a rate

 
d
(n − k)/n ≥ 1 − H2 n
. (29)

The redundancy k/n satisfies k/n ≤ H2 (d/n), so that the quantum codes achieve a rate

 
d
R = (n − 2k)/n ≥ 1 − 2H2 n
. (30)

This function is plotted in Fig. 1.

15
 VI. QUANTUM CHANNELS

In order to carry Shannon’s theory of information to the quantum regime, it is necessary

to have some reasonable definition of a noisy quantum channel. We will define a quantum

channel W by a probability distribution P on unitary transformations UW mapping Hsig ⊗

Henv . For any pure input state |xi the channel produces as output a mixed state by first
obtaining an ensemble of states in Hsig ⊗ Henv by applying the transformation UW to |xi
with probability distribution P, and secondly tracing over Henv . While the initial state of

Henv could be given by an ensemble of states, it may also without loss of generality be taken
to be a fixed pure state, as the probability distribution given by an ensemble of initial states
may be absorbed into the probability distribution on the unitary transformation UW . The
probability distribution could also be concentrated entirely in the inital mixed state of Henv ,

and a fixed unitary transform U be used, but this leads to a slightly less intuitive description
of the one quantum channel that we later discuss in detail.
Actual quantum channels are unlikely to produce output that differs from the input
exactly by the decoherence of at most t qubits, and thus are unlikely to be able to transmit
quantum states perfectly using this scheme. However, if the average behavior of the channel

results in the decoherence of fewer than t qubits, a channel may still be able to transmit
quantum states very well. A measure of the success of transmission of quantum states that
has previously been successful applied in quantum information theory is fidelity [15,11]. In
this paper, we define fidelity slightly differently from the definition in Refs. [15]; we make

this change as these previous papers discuss channels that transmit some distribution of
quantum states given a priori, whereas we want our channel to faithfully transmit any pure
input state. Suppose that we have a noisy channel W that transmits quantum states in a
Hilbert space Hsig . We define the fidelity of the channel to be

min Ehx|W |xi, (31)

|xi∈Hsig

where the expectation is taken over the output of the channel. In other words, we are
measuring the fidelity of transmission of the pure state transmitted with least fidelity. We

16
could also measure the fidelity of transmission of a typical state in Hsig ; this average fideleity
is a quantity which is closer to the previous definition, and may be more useful in some
situations.

Assume that a channel W transmits qubits with a fidelity of F and is that the decoherence
process affects each qubit independently, i.e., each the decoherence of one qubit has no
correlation with the decoherence of any other qubit. This would follow from the assumption
that each qubit has a different environment, and this situation corresponds to memoryless

channels in classical information theory. Then EW hx|W |xi ≥ F for every state |xi ∈ H2 .
If the output of our channel is a pure state, our error-correction procedure Rp Rf will be
successful with probability equal to the length of the projection of the state onto the subspace
of H2n which results from decoherence of any t or fewer qubits. Since the decoherence process

for each qubit is independent, we can use the binomial theorem to calculate the probability
that the state W n |yi is projected onto the correctable subspace of H2n , where |yi is in our
quantum code C. We thus have a channel which transmits states |yi with fidelity
t
!
n n n−j
F (1 − F )j
X
Ehy|Rp Rf W |yi ≥ (32)
j=0 j

for all |yi in our quantum code C. This quantity is close to 1 as long as t/n > 1 − F . Thus,
if the fidelity F for each transmitted qubit is large enough, our quantum codes guarantee
high fidelity transmission for our encoding of k qubits. Our quantum codes will give good
results for any channel W that transmits states |yi ∈ H2n well enough that W |yi has an

expected projection of length at least 1 − ǫ onto the subspace of H2n obtained from |xi by
the decoherence at most t qubits. Our encoding and decoding schemes then give a channel
on the Hilbert space H2k which has fidelity 1 − ǫ. We will next use this observation to obtain
an upper bound on the channel capacity of quantum channels.

An upper bound for the amount of classical information carried by a quantum channel is
given by the Levitin–Holevo theorem [10]. If the output of the channel is a signal that has
density matrix ρa with probitility pa , the Levitin–Holevo bound on the information content
of this signal is

17
 X
H(ρ) − pa H(ρa ), (33)
a

where ρ = pa ρa (the density matrix for the ensemble of signals), and where H(ρ) =
P
a

−Tr(ρ log2 ρ) is the von Neumann entropy. Since quantum information can be used to carry

classical information, the Levitin–Holevo bound can be used to obtain an upper bound for
the rate of a quantum error-correcting code.
Consider the following quantum channel discussed in Ref. [11]; this channel treats each
qubit independently. With probability 1 − p, a qubit is unchanged, corresponding to the
 
1 0
identity transformation 0 1 . Otherwise, with each possibility having probability p/3, the
qubit is acted on by the unitary transformation corresponding to one of the three matrices:
     
0 1 1 0 0 1
1 0 , 0 −1 , or −1 0 . That is, each of the following possibilities has probability
p/3: the qubit is negated, or its phase is changed, or it is both negated and its phase is

changed. If t/n > p + ǫ for ǫ > 0, the length projection of the output of this channel
onto the subspace of H2n with at most t errors approaches 1 as n grows, so the quantum
error-correcting codes given earlier in this paper guarantee high fidelity. This channel can
alternatively be described as transmitting a qubit error-free with probability 1 − 34 p, and
producing a random quantum state with probability 34 p. This description shows that the

entropy of the output of the channel is at least H2 ( 32 p), so by the Levitin–Holevo theorem an
upper bound on the classical information capacity of this channel is 1 − H2 ( 32 p). This bound
is plotted in Fig. 1. For this channel, the bound is achievable for classical information, but
we believe it is unlikely to be tight for quantum information.

Another question that has been studied is: how much entanglement can be transmitted
over a quantum channel [11]. Since any means of transmitting quantum states with high
fidelity can also be used to transmit entanglement, upper bounds for entanglement transmis-
sion also apply to the quantum information capacity of a quantum channel. For the above
q
channel, the upper bound proved in Ref. [11] is H2 ( 21 + p(1 − p)) for p < 1
2
and 0 if p ≥ 21 .
This bound is also plotted in Fig. 1.

18
 ACKNOWLEDGMENTS

We would like to thank Peter Winkler for helpful discussions on quantum error-correcting

codes, and David DiVincenzo for advice on the presentation of these results.

19
 REFERENCES

[1] D. Deutsch, “Quantum theory, the Church–Turing principle and the universal quantum
computer,” Proc. R. Soc. Lond. Ser. A 400, 96 (1985); D. Simon, “On the power of

quantum computation,” in Proceedings of the 35th Annual Symposium on Foundations

of Computer Science, edited by S. Goldwasser (IEEE Computer Society, Los Alamitos,
CA, 1994) p. 116; P. W. Shor, “Algorithms for quantum computation: Discrete loga-
rithms and factoring,” ibid., p. 124; A. Ekert and R. Jozsa, “Shor’s quantum algorithm

for factorising numbers” Rev. Mod. Phys. (to appear).

[2] S. Lloyd, “A potentially realizable quantum computer,” Science 261, 1569 (1993); D. P.
DiVincenzo, “Two-bit gates are universal for quantum computation,” Phys. Rev. A 51,

1015 (1995); A. Barenco, D. Deutsch, A. Ekert and R. Jozsa, “Conditional quantum

dynamics and logic gates,” Phys. Rev. Lett. 74, 4083 (1995); T. Sleator and H. Wein-
furter, “Realizable universal quantum logic gates,” ibid. 74, 4087 (1995); I. L. Chuang
and Y. Yamamoto, “A simple quantum computer,” Phys. Rev. A 52, 3489 (1995).

[3] J. I. Cirac and P. Zoller, “Quantum computations with cold trapped ions,” Phys. Rev.
Lett. 74, 4091 (1995).

[4] W. G. Unruh, “Maintaining coherence in quantum computers,” Phys. Rev. A 51, 992
(1995); G. M. Palma, K.-A. Suominen, and A. K. Ekert, “Quantum computers and
dissipation,” Proc. R. Soc. London A, (to appear). R. Landauer, “Is quantum mechanics

useful?” Philos. Trans. R. Soc. London, Ser. A (to appear); R. Landauer, “Is quantum
mechanically coherent computation useful?” in Proceedings of the Drexel-4 Symposium
on Quantum Nonintegrability — Quantum Classical Correspondence, edited by D. H.
Feng and B.-L. Hu, (International Press, in press); I. L. Chuang, R. Laflamme, P. W.

Shor, and W. H. Zurek, “Quantum computers, factoring and decoherence,” Science 270,
1635 (1995).

[5] C. Monroe, D. M. Meekhof, B. E. King, W. M. Itano and D. J. Wineland, “Demonstra-

20
 tion of a universal quantum logic gate,” Phys. Rev. Lett. 75, 4714 (1995).

[6] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (North-

Holland, Amsterdam, 1977).

[7] R. L. Dobrushin and S. I. Ortyukov, “Lower bound for the redundancy of self-correcting
arrangements of unreliable functional elements,” Probl. Peredachi Inf. 13(1), 82 (1977)
[Probl. Inf. Transm. (USSR) 13, 59 (1977)]; “Upper bound for the redundancy of self-
correcting arrangements of unreliable functional elements,” Probl. Peredachi Inf. 13(3),
56 (1977) [Probl. Inf. Transm. (USSR) 13, 203 (1977)]; N. Pippenger, “Invariance of

complexity measures for networks with unreliable gates,” J. Assoc. Comput. Mach., 36,
531 (1989); N. Pippenger, G. D. Stamoulis and J. N. Tsitsiklis, “On a lower bound for
the redundancy of reliable networks with noisy gates,” IEEE Trans. Inf. Theory 37,
639 (1991), U. Feige, P. Raghavan, D. Peleg, and E. Upfal, “Computing with noisy

information,” SIAM J. Comput. 23, 1001 (1994).

[8] W. K. Wooters and W. H. Zurek, “A single quantum cannot be cloned,” Nature 299,

802 (1982); D. Dieks, “Communication by EPR devices,” Phys. Lett. A 92, 271 (1982).

[9] P. W. Shor, “Scheme for reducing decoherence in quantum memory,” Phys. Rev. A 52,
2493 (1995).

[10] L. B. Levitin, “On the quantum measure of the amount of information,” in Proceedings
of the Fourth All-Union Conference on Information Theory, Tashkent (1969), p. 111,

in Russian; A. S. Kholevo, “Bounds for the quantity of information transmitted by

a quantum communication channel,” Probl. Peredachi Inf. 9(3), 3 (1973) [Probl. Inf.
Transm. (USSR) 9, 177 (1973)].

[11] C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin, and W. K. Woot-

ers, “Purification of noisy entanglement and faithful teleportation via noisy channels,”
Phys. Rev. Lett. 76, 722 (1996).

21
[12] A. M. Steane, “Error correcting codes in quantum theory,” Phys. Rev. Lett. (submitted);
A. M. Steane, “Multiple particle interference and quantum error correction,” Proc. Roy.
Soc. London A (submitted).

[13] F. J. MacWilliams, N. J. A. Sloane, and J. G. Thompson, “Good self dual codes exist,”
Discrete Math., 3, 153 (1972).

[14] A. Fujiwara and H. Nagaoka, “Capacity of a memoryless quantum communication chan-

nel,” Mathematical Engineering Technical Report No. 94-22, University of Tokyo, 1994;
abstract in Proceedings of the 1995 IEEE International Symposium on Information The-

ory (IEEE, 1995) p. 138.

[15] B. Schumacher, “Quantum coding,” Phys. Rev. A 51, 2738 (1995); R. Jozsa and B.

Schumacher, “A new proof of the quantum noiseless coding theorem,” J. Mod. Opt. 41,
2343 (1994).

22
 FIGURES
FIG. 1. The solid line shows the asymptotic rate R of our quantum codes versus the error rate

of the channel t/n. Two upper bounds for this quantity are also plotted: the Levitin–Holevo upper

bound with a dashed line and the entanglement upper bound with a dotted line.

23
 1.0
0.8
0.6
R
0.4
0.2
0.0
0.0 0.1 0.2 0.3 0.4 0.5
t/n