Francoise J.-P., Naber G.L., Tsun T.S. (editors) Encyclopedia of Mathematical Physics
Подождите немного. Документ загружается.
sequence of eigenfunctions. Are the following
asymptotics valid?
Z
N
’
j
f dH
n1
j
1
VolðM; gÞ
Z
M
f dVol
This is predicted by the random wave model of
the section ‘‘Rand om wave s and orthon ormal
bases.’’ An equidist ribution law for the compl ex
zeros is known which gives some evidence for the
validity of this limit formula. Let (M, g)bea
compact real analytic Riemannian manifold and let
’
C
j
be the holomorphic extension of the real analytic
eigenfunction ’
j
to the complexification M
C
of M
(its Grauert tube). Then, if the geodesic flow is
ergodic and if ’
j
is an ergodic sequence of
eigenfunctions, the normalized current of integration
(1=
j
)Z
’
C
j
over the complex zero set of ’
C
j
tends
weakly to (i=)
@@j
g
j. This current is singular along
the zero section.
Finally, we mention some results on L
1
-norms of
eigenfunctions on arithmetic hyperbolic manifolds
of dimensi ons 2 and 3. It was proved by Iwan iec–
Sarnak that the joint eigenfunctions of and the
Hecke operators on arithmetic hyperbolic surfaces
have the upper bound k’
j
k
1
= O
(
5=48þ
j
) for all
j and >0, and the lower bound k’
j
k
1
c
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
log log
j
p
for some constant c > 0 and infinitely
many j. Rudnick and Sarnak (1994) proved that
there exists an arithmetic hyperbolic manifold and a
subsequence ’
j
k
of eigenfunctions with k’
j
k
k
L
1
1=4
j
k
, contradicting the random wave model
predictions.
Quantum Weak Mixing
There are paral lel results on quantizations of weak-
mixing geodesic flows which are the subject of this
section. First we recall the classical definition:
the geodesic flow of (M, g) is weak mixing if the
operator V
t
has purely continuous spectrum on the
orthogonal complement of the constant functions in
L
2
(S
M,d). Hence, like ergodicity, it is a spectral
property of the geodesic flow.
We have:
Theorem 2 (Zelditch 1996c). The geodesic flow
t
of (M , g) is weak mixing if and only if the conditions
(i) and (ii) of Theorem 1 hold and additionally, for
any A 2
o
(M),
ð8Þð9Þlim sup
!1
1
NðÞ
X
j 6¼k :
j
;
k
j
j
k
j<
jðA’
j
;’
k
Þj
2
<
ð8 2 RÞ
The restriction j 6¼ k is of course redundant unless
= 0, in which case the statement coincides with
quantum ergodicity. This result follows from the
general asymptotic formula, valid for any compact
Riemannian manifold (M, g), that
1
NðÞ
X
i6¼j;
i
;
j
jhA’
i
;’
j
ij
2
sin Tð
i
j
Þ
Tð
i
j
Þ
2
1
2T
Z
T
T
e
it
V
t
ð
A
Þ
2
2
sin T
T
2
!ðAÞ
2
½24
In the case of weak-mixing geodesic flows, the right-
hand side tends to 0 as T !1. As with diagonal
sums, the sharper result is true where one averages
over the short intervals [, þ 1].
Spectral Measures and Matrix Elements
Theorem 2 is based on expressing the spectral
measures of the geodesic flow in terms of matrix
elements. The main limit form ula is
Z
þ"
"
d
A
:¼ lim
!1
1
NðÞ
X
i; j:
j
;
j
i
j
j<"
jhA’
i
;’
j
ij
2
½25
where d
A
is the spectral measure for the geodesic
flow corresponding to the principal symbol of
A,
A
2 C
1
(S
M,d). Recall that the spectral mea-
sure of V
t
corresponding to f 2 L
2
is the measure
d
f
defined by
hV
t
f ; f i
L
2
ðS
MÞ
¼
Z
R
e
it
d
f
ðÞ
The limit formula [25] is equivalent to the dual
formula (under the Fourier transform):
lim
!1
1
NðÞ
X
i;j:
j
e
itð
i
j
Þ
jhA’
i
;’
j
ij
2
¼hV
t
A
;
A
i
L
2
ðS
MÞ
½26
The proof of [26] is to consider, for A 2
, the
operator A
t
A 2
with A
t
= U
t
AU
t
. By the local
Weyl law,
lim
!1
1
NðÞ
tr EðÞ A
t
A ¼hV
t
A
;
A
i
L
2
ðS
MÞ
The right-hand-side of [25] defines a measure dm
A
on R and [26] says
Z
R
e
it
dm
A
ðÞ¼hV
t
A
;
A
i
L
2
ðS
MÞ
¼
Z
R
e
it
d
A
ðÞ
192 Quantum Ergodicity and Mixing of Eigenfunctions
Since weak-mixing systems are ergodic, it is not
necessary to average in both indices along an
ergodic subsequence:
lim
j
!1
hA
t
A’
j
;’
j
i¼
X
j
e
itð
i
j
Þ
jhA’
i
;’
j
ij
2
¼hV
t
A
;
A
i
L
2
ðS
MÞ
½27
Dually, one has
lim
j
!1
X
i : j
i
j
j<"
jhA’
i
;’
j
ij
2
¼
Z
þ"
"
d
A
½28
For QUE systems, these limit formulas are valid for
the full sequence of eigenfunct ions.
Rate of Quantum Ergodicity and Mixing
A quantitative refinement of quantum ergodicity is
to ask at what rate the sums in Theorem 1(i) tend to
zero, that is, to establish a rate of quantum
ergodicity. More generally, we consider ‘‘variances’’
of matrix elements. For diagonal matrix elements,
we define
V
A
ðÞ :¼
1
NðÞ
X
j:
j
jhA’
j
;’
j
i!ðAÞj
2
½29
In the off-diagonal case, one may view jhA’
i
, ’
j
ij
2
as
analogous to jhA’
j
, ’
j
) !(A)j
2
. However, the sums
in [25] are double sums while those of [29] are
single. One may also average over the shorter
intervals [, þ 1].
Quantum Chaos Conjectures
First, consider off-diagonal matrix elements. One
conjecture is that it is not necessary to sum in j in
[28]: each individual term has the asymptotics
consistent with [28]. This is implicitly conjectured
by Feingold–Peres (1986) (see [11] ) in the form
jhA’
i
;’
j
ij
2
’
C
A
E
i
E
j
h
2ðEÞ
½30
where
C
A
ðÞ¼
Z
1
1
e
it
hV
t
A
;
A
idt
In our notation,
j
=h
1
E
j
and (E)dE dN().
There are C
n1
eigenvalues
i
in the interval
[
j
,
j
þ ], so [30] states that individual
terms have the asymptotics of [28].
On the basis of the analogy between jhA’
i
, ’
j
ij
2
and jhA’
j
, ’
j
i!(A)j
2
, it is conjectured in Feingold
and Peres (1986) that
V
A
ðÞ
C
A!ðAÞI
ð0Þ
n1
volðÞ
The idea is that ’
= (1=
ffiffiffi
2
p
)(’
i
’
j
) have the same
matrix element asymptotics as eigenfunctions when
i
j
is sufficiently small. But then 2hA’
þ
, ’
i=
hA’
i
, ’
i
ihA’
j
, ’
j
i when A
= A. Since we are
taking a difference, we may replace each matrix
element hA’
i
, ’
i
iby hA’
i
, ’
i
i!(A)(andalsofor’
j
).
The conjecture then assumes that hA’
i
, ’
i
i!(A)has
the same order of magnitude as hA’
i
, ’
i
ihA’
j
, ’
j
i.
Dynamical grounds for this conjecture are given in
Eckhardt et al. (1995). The order of magnitude is
predicted by some natural random wave models, as
discussed in the next section.
Rigorous results
At this time, the strongest variance result is an
asymptotic formula for the diagonal variance proved
by Luo and Sarnak (2004) for special Hecke
eigenfunctions on the quotient H
2
=SL(2, Z) of the
upper half plane by the modular group. Their result
pertains to holomorphic Hecke eigenforms, but the
analogous statement for smooth Maass–Hecke
eigenfunctions is expected to hold by similar
methods, so we state the result as a theorem/
conjecture. Note that H
2
=SL(2, Z) is a noncompact
finite-area surface whose Laplacian has both a
discrete and a continuous spectrum. The discrete
Hecke eigenfunctions are joint eigenfunctions of
and the Hecke operators T
p
.
Theorem/Conjecture 1 (Luo and Sarn ak 2004).
Let {’
k
} denote the orthonormal basis of Hecke
eigenfunctions for H
2
=SL(2, Z). Then there exists a
quadratic form B(f ) on C
1
0
(H
2
=SL(2, Z)) such that
1
NðÞ
X
j
Z
X
f ’
j
2
dvol
1
VolðXÞ
Z
X
f dVol
2
¼
Bðf ; f Þ
þ o
1
When the multiplier f = ’
is itself an eigenfunc-
tion, Luo–Sarnak have shown that
Bð’
;’
Þ¼C
’
ð0ÞLð
1
2
;’
Þ
where L(
1
2
, ’
) is a certain L-function. Thus, the
conjectured classical variance is multiplied by an
arithmetic factor depending on the multiplier. A
crucial fact in the proof is that the quadratic form B
is diagonalized by the ’
.
Quantum Ergodicity and Mixing of Eigenfunctions 193
The only rigorous result to date which is valid on
general Riemannian manifolds with hyperbolic
geodesic flow is the logarithmic decay:
Theorem 3 ( Zelditch). For any (M, g) with hyper-
bolic geodesic flow,
1
NðÞ
X
j
jðA’
j
;’
j
Þ!ðAÞj
2p
¼
1
ðlog Þ
p
The logarithm reflects the exponential blow-up in
time of remainder estimates for traces involving the
wave group associated to hyperbolic flows. It would
be surprising if the logarithmic decay is sharp for
Laplacians. However, a recent result of R Schubert
shows that the estimate is sharp in the case of two-
dimensional hyperbolic quantum cat maps. Hence,
the estimate cannot be improved by semiclassical
arguments that hold in both settings.
Random Waves and Orthonormal Bases
We have mentioned that the random wave model
provides a kind of guideline for what to conjecture
about eigenfunctions of quantum chaotic system. In
this final section, we briefly discuss random wave
models and what they predict.
By a random wave model, one means a prob-
ability measure on a space of functions. To deal
with orthonormal bases rather than individual
functions, one sets a probability measure on a
space of orthonormal bases, that is, on a unitary
group. We denote expected values relative to a given
probability measure by E. We now consider some
specific Gaussian models and what they predict
about variances.
As a model for quantum chaotic eigenfunctions
in plane domains, Berry (1977) suggested using
the Euclidean random wave model at fixed
energy. A rigorous version of such a model is as
follows: let E
denote the space of (tempered)
eigenfunctions of eigenvalue
2
of the Euclidean
Laplacian on R
n
. It is spanned by exponentials
e
ihk, xi
with k 2 R
n
, jkj= . The infinite-dimensional
space E
is a unitary representation of the Euclidean
motion group and carries an invariant inner
product. The inner product defines an associated
Gaussian meas ure who se covaria nce kern el
C
(x, y) = E f (x)
f (y) is the derivative at of the
spectral function
Eð; x; yÞ¼ð2Þ
n
Z
jj
e
ihxy;i
d; 2 R
n
½31
Thus,
C
ðx; yÞ¼
d
d
Eð; x; yÞ
¼ð2Þ
n
Z
jj¼
e
ihxy;i
dS
¼ð2Þ
n
n1
Z
jj¼1
e
ihxy;i
dS ½32
where dS is the usual surface measure. With this
definition, C
(x, x)
n1
. In order to make
E(f (x)
2
) = 1 consi stent with normalized eigenfunc-
tions, we divide by
n1
to define
^
C
ðx; yÞ¼ð2Þ
n
Z
jj¼1
e
ihxy;i
dS
One could express the integral as a Bessel function
to rewrite this as
n 1
2
jjx yjj
ðn2Þ=2
J
ðn2Þ=2
ðjx yjÞ
Wick’s formula in this ensemble gives
E’ðxÞ
2
’ðyÞ
2
¼
1
VolðÞ
2
½1 þ 2C
ðx; yÞ
2
Thus, in dimension n we have
E
"
ZZ
VðxÞVðyÞ’ðxÞ
2
’ðyÞ
2
dxdy
V
2
#
¼
2
VolðÞ
2
Z
Z
^
C
ðx; yÞ
2
VðxÞVðyÞdx dy
1
n1
VolðÞ
2
Z
Z
VðxÞVðyÞ
jx yj
n1
cosðjx yjÞ
2
dx dy
In the last line, we used the stationary-phase
asymptotics
ð2Þ
n
n1
Z
jj¼1
e
ihxy;i
dS
C
n
ðjx yjÞ
ðn1Þ=2
cosðjx yjÞ½33
Thus, the variances have order
(n1)
in dimension n,
consistent with the conjectures in Feingold and
Peres (1986) and Eckhardt et al. (1995).
This model is often used to obtain predictions on
eigenfunctions of chaotic systems. By construction,
it is tied to Euclidean geometry and only pertains
directly to individual eigenfunctions of a fixed
eigenvalue. It is based on the infinite-dimensional
multiplicity of eigenfunctions of fixed eigenvalue of
the Euclidean Laplacian on R
n
. There also exist
random wave models on a curved Riemannian
manifold (M, g), which model individual eigen-
functions and also random orthonormal bases
194 Quantum Ergodicity and Mixing of Eigenfunctions
(Zelditch 1996a). Thus, one can compare the
behavior of sums over eigenvalues of the orthonor-
mal basis of eigenfunctions of with that of a
random orthonormal basis. Instead of taking
Gaussian random combinations of Euclidean plane
waves of a fixed eigenvalue, one takes Gaussian
random combinations
P
j :
j
2[,þ1]
c
j
’
j
of the eigen-
functions of (M, g) with eigenvalues in a short
interval in the sense above. Equivalently, one takes
random combinations with
P
j
jc
j
j
2
= 1. These
random waves are globally adapted to (M, g). The
statistical results depend on the measure of the set of
periodic geodesics of (M, g); thus, as discussed in
Kaplan and Heller (1998), different random wave
models make different predictions about off-
diagonal variances.
Fix a compact Riemannian manifold (M, g)and
partition the spectrum of
ffiffiffiffi
p
into the intervals
I
k
= [k, k þ 1]. Let
k
= E(k þ 1) E(k)bethe
kernel of the spectral projections for
ffiffiffiffi
p
corre-
sponding to the interval I
k
.Itskernel
k
(x, y)is
the covariance k ernel of Gaussian random combi-
nations
P
j :
j
2I
k
c
j
’
j
and is analogous to C
(x, y)in
the Euclidean case; it is of course not
thederivativedE(, x, y) but the difference of the
spectral projector over I
k
.WedenotebyN(k)the
number of eigenvalues in I
k
and put H
k
= ran
k
(the range of
k
). We define a ‘‘random’’ ortho-
normal basis of H
k
by changing the basis of
eigenfunctions {’
j
}of in H
k
by a random
element of the unitary group U( H
k
) of the finite-
dimensional Hilbert space H
k
.Wethendefinea
random orthonormal basis of L
2
(M)bytakingthe
product over all the spectral intervals in our
partition. More precisely, we define the infinite-
dimensional unitary group
Uð1Þ ¼
Y
1
k¼1
UðH
k
Þ
of sequences (U
1
, U
2
, ...), with U
k
2 U(H
k
). We
equip U(1) with the product
d
1
¼
Y
1
k¼1
d
k
of the unit mass Haar measures d
k
on U(H
k
): we
then define a random orthonormal basis of L
2
(M)to
be obtained by applying a random element
U 2 U (1) to the orthonormal basis ={’
j
}of
eigenfunctions of
ffiffiffiffi
p
.
Assuming the set of periodic geodesics of (M, g)
has measure zero, the Weyl remainder results [8]
and strong Szego¨ limit asymptotics of Guillemin–
Okikiolu and Laptev–Robert–Safarov give two term
asymptotics for the traces
k
A
k
,(
k
A
k
)
2
for any
pseudodifferential operato r A. Combining the strong
Szego¨ asymptotics with the arguments of Zelditch
(1996a), random orthon ormal bases can be proved
to satisfy the following variance asymptotics:
1. Eð
P
j:
j
2I
k
jðAU ’
j
; U’
j
Þ!ðAÞj
2
ð!ðA
AÞ!ðAÞ
2
Þ;
2. Eð
P
i6¼j:
j
;
i
2I
k
sinTð
i
j
Þ
Tð
i
j
Þ
2
jðAU ’
j
; U’
i
Þj
2
2
sinT
T
2
þ
1
N ðkÞ
P
i6¼j
sinTð
i
j
Þ
Tð
i
j
Þ
2
ð!ðA
AÞ!ðAÞ
2
Þ
See also: Arithmetic Quantum Chaos; Determinantal
Random Fields; Eigenfunctions of Quantum Completely
Integrable Systems; Fractal Dimensions in Dynamics;
h-Pseudodifferential Operators and Applications; Number
Theory in Physics; Regularization for Dynamical Zeta
Functions; Semiclassical Spectra and Closed Orbits.
Further Reading
Ba¨cker A, Schubert R, and Stifter P (1998a) Rate of quantum
ergodicity in Euclidean billiards. Physical Review E (3) 57(5):
part A 5425–5447.
Ba¨cker A, Schubert R, and Stifter P (1998b) Rate of quantum
ergodicity in Euclidean billiards – erratum. Physical Review E,
(3) 58(4): 5192 (math-ph/0512030).
Barnett A (2005) Asymptotic rate of quantum ergodicity in
chaotic Euclidean billiards.
Berry MV (1977) Regular and irregular semiclassical wavefunc-
tions. Journal of Physics A 10(12): 2083–2091.
Bohigas O, Giannoni MJ, and Schmit C (1984) Characterization
of chaotic quantum spectra and universality of level fluctua-
tion laws. Physical Review Letters 52(1): 1–4.
Eckhardt B, Fishman S, Keating J, Agam O, Main J et al. (1995)
Approach to ergodocity in quantum wave functions. Physical
Review E 52: 5893–5903.
Faure F, Nonnenmacher S, and De Bie` vre S (2003) Scarred
eigenstates for quantum cat maps of minimal periods.
Communications in Mathematical Physics 239(3): 449–492.
Feingold M and Peres A (1986) Distribution of matrix elements of
chaotic systems. Physical Review A (3) 34(1): 591–595.
Heller EJ (1984) Bound-state eigenfunctions of classically chaotic
Hamiltonian systems: Scars of periodic orbits. Physical Review
Letters 53(16): 1515–1518.
Kaplan L and Heller EJ (1998) Weak quantum ergodicity. Physica
D 121(1–2): 1–18 (Appendix by S. Zelditch.).
Luo W and Sarnak P (2004) Quantum variance for Hecke
eigenforms. Annales Scientifiques de l’Ecole Normale Super-
ieure 37: 769–799.
Marklof J and O’Keefe S (2005) Weyl’s law and quantum
ergodicity for maps with divided phase space (with an
appendix ‘Converse quantum ergodicity’ by Steve Zelditch).
Nonlinearity 18(1): 277–304.
Rudnick Z and Sarnak P (1994) The behaviour of eigenstates of
arithmetic hyperbolic manifolds. Communications in Mathe-
matical Physics 161: 195–213.
Ruelle D (1969) Statistical Mechanics: Rigorous Results. New
York: W. A. Benjamin.
Quantum Ergodicity and Mixing of Eigenfunctions 195
Sarnak P (1995) Arithmetic quantum chaos. In: The Schur
Lectures (Tel Aviv, 1992), Israel Mathematical Conference
Proc, vol. 8 (1995), pp. 183–236.
Zelditch S (1996a) A random matrix model for quantum mixing.
International Mathematics Research Notices 3: 115–137.
Zelditch S (1996b) Quantum ergodicity of C
dynamical systems.
Communications in Mathematical Physics 177: 507–528.
Zelditch S (1996c) Quantum Mixing. Journal of Functional
Analysis 140: 68–86.
Zelditch S and Zworski M (1996) Ergodicity of eigenfunctions for
ergodic billiards. Communications in Mathematical Physics
175: 673–682.
Quantum Error Correction and Fault Tolerance
D Gottesman, Perimeter Institute, Waterloo, ON,
Canada
ª 2006 Elsevier Ltd. All rights reserved.
Quantum Error Correction
Building a quantum computer or a quantum com-
munications device in the real world means having
to deal with errors. Any qubit stored unprotected or
one transmitted through a communications channel
will inevitably come out at least slightly changed.
The theory of quantum error-correcting codes
(QECCs) has been developed to counteract noise
introduced in this way. By adding extra qubits and
carefully encoding the quantum state we wish to
protect, a quantum system can be insulated to a
great extent against errors.
To build a quantum computer, we face an even
more daunting task: if our quantum gates are
imperfect, everything we do will add to the error.
The theory of fault-tolerant quantum computation
tells us how to perform operations on states encoded
in a QECC without compromising the code’s ability
to protect against errors.
In general, a QECC is a subspace of a Hilbert
space designed so that any of a set of possible errors
can be corrected by an appropriate quantum
operation. Specifically:
Definition 1 Let H
n
be a 2
n
-dimensional Hilbert
space (n qubits), and let C be a K-dimensional
subspace of H
n
. Then C is an ((n, K)) (binary) QECC
correcting the set of errors E = {E
a
} iff 9R s.t. R is a
quantum operation and (RE
a
)(j i) = j i for all
E
a
2E, j i2C.
R is called the ‘‘recovery’’ or ‘‘decoding’’ oper a-
tion and serves to actually perform the correction
of the state. The decoder is sometimes also taken to
map H
n
into an unencoded Hilbert s pace H
log K
isomorphic to C. This should be distinguished from
the ‘‘encoding’’ operation which maps H
log K
into
H
n
, determining the imbedding of C. The computa-
tional complexity of the encoder is frequently
a great deal lower than that of the decoder.
In particular, the task of determining what error
has occurred can be computationally difficult
(NP-hard, in fact), and designing codes with
efficient decoding algorithms is an important task
in quantum error correction, as in classical error
correction.
This article will cover only binary quantum codes,
built with qubits as registers, but all of the
techniques discussed here can be generalized to
higher-dimensional registers, or ‘‘qudits.’’
To determine whether a given subspace is able to
correct a given set of errors, we can apply the
quantum error-correction conditions (Bennett et al.
1996, Knill and Laflamme 1997):
Theorem 1 A QECC C corrects the set of errors E iff
h
i
jE
y
a
E
b
j
j
i¼C
ab
ij
½1
where E
a
, E
b
2E and {j
i
i} form an orthonormal
basis for C.
The salient point in these error-correction condi-
tions is that the matrix element C
ab
does not depend
on the encoded basis states i and j, which, roughly
speaking, indicates that neither the environment nor
the decoding operation learns any information about
the encoded state. We can imagine the various
possible errors taking the subspace C into other
subspaces of H
n
, and we want those subspaces to be
isomorphic to C, and to be distinguishable from
each other by an appropriate measurement. For
instance, if C
ab
=
ab
, then the various erroneous
subspaces are orthogonal to each other.
Because of the linearity of quantum mechanics,
we can always take the set of errors E to be a linear
space: if a QECC corre cts E
a
and E
b
, it will also
correct E
a
þ E
b
using the same recovery opera-
tion. In addition, if we write any superoperator S in
terms of its operator-sum representation S() 7!
P
A
k
A
y
k
, a QECC that corrects the set of errors
{A
k
} automatically corrects S as well. Thus, it is
sufficient in general to check that the error-correc-
tion conditions hold for a basis of errors.
196 Quantum Error Correction and Fault Tolerance
Frequently, we are interested in codes that correct
any error affecting t or fewer physical qubits. In that
case, let us consider tensor products of the Pauli
matrices
I ¼
10
01
; X ¼
01
10
Y ¼
0 i
i0
; Z ¼
10
0 1
½2
Define the Pauli group P
n
as the group consi sting of
tensor products of I, X, Y, and Z on n qubits, with
an overall phase of 1ori. The weight wt(P)ofa
Pauli ope rator P 2P
n
is the number of qubits on
which it acts as X, Y,orZ (i.e., not as the identity).
Then the Pauli operators of weight t or less form a
basis for the set of all errors acting on t or fewer
qubits, so a QECC which corrects these Pauli
operators corrects al l errors acting on up to t
qubits. If we have a channel which causes errors
independently with probability O() on each qubit
in the QECC, then the code will allow us to
decode a correct state e xcept with probability
O(
tþ1
), which is the probability of having more
than t errors. We get a similar result in the case
where the noise is a general quantum operation on
each qubit which differs from the identity by
something of size O().
Definition 2 The distance d of an ((n, K)) QECC is
the smallest weight of a nontri vial Pauli operator
E 2P
n
s.t. the equation
h
i
jEj
j
i¼CðEÞ
ij
½3
fails.
We use the notation ((n, K, d)) to refer to an
((n, K)) QECC with distance d. Note that for P, Q 2
P
n
, wt(PQ ) wt(P) þ wt(Q). Then by comparing
the definition of distance with the quantum error-
correction conditions, we immediately see that a
QECC corrects t general errors iff its distance d > 2t.
If we are instead interested in ‘‘erasure’’ errors, when
the location of the error is known but not its precise
nature, a distance d code corrects d 1erasure
errors. If we only wish to detect errors, a distance d
code can detect errors on up to d 1qubits.
One of the central problems in the theory of
quantum error correction is to find codes which
maximize the ratios ( log K)=n and d=n, so they can
encode as many qubits as possible and correct as
many errors as possible. Conversely, we are also
interested in the problem of setting upper bounds on
achievable values of ( log K)=n and d=n. The
quantum Singleton bound (or Knill–Laflamme
(1997) bound) states that any ((n, K, d)) QECC
must satisfy
n log K 2d 2 ½4
We can set a lower bound on the existence of
QECCs using the quantum Gilbert–Varshamov
bound, which states that, for large n,an((n,2
k
, d))
QECC exists provided that
k=n 1 ðd=nÞlog 3 hðd=nÞ½5
where h(x) = x log x (1 x) log (1 x) is the
binary Hamming entropy. Note that the Gilbert–
Varshamov bound simply stat es that codes at least
this good exist; it does not suggest that better codes
cannot exist.
Stabilizer Codes
In order to better manipulate and discover QECCs,
it is helpful to have a more detailed mathematical
structure to work with. The most widely used
structure gives a class of codes known as ‘‘stabilizer
codes’’ (Calderbank et al. 1998, Gottesman
1996). They are less general than arbitrary quantum
codes, but have a number of useful properties that
make them easier to work with than the general
QECC.
Definition 3 Let S P
n
be an abelian subgroup of
the Pauli group that does not contain 1ori, and
let C(S) = {j i s.t. Pj i= j i8P 2 S}. Then C(S)isa
stabilizer code and S is its stabilizer.
Because of the simple structure of the Pauli group,
any abelian subgroup has order 2
nk
for some k and
can easily be specified by giving a set of n k
commuting generators.
The code words of the QECC are by definition in
the þ1-eigenspace of all elements of the stabilizer,
but an error E acting on a code word will move the
state into the 1-eigenspace of any stabilizer element
M which anticommutes with E:
MEj iðÞ¼EMj i¼Ej i½6
Thus, measuring the eigenvalues of the generators of
S tells us information about the error that has
occurred. The set of such eigenvalues can be
represented as an (n k)-dimensional binary vector
known as the ‘‘error syndrome.’’ Note that the error
syndrome does not tell us anything about the encoded
state, only about the error that has occurred.
Theorem 2 Let S be a stabilizer with n k gener-
ators, and let S
?
= {E 2P
n
s.t.[E, M] = 0 8M 2 S}.
Then S encodes k qubits and has distance d, where d
is the smallest weight of an operator in S
?
nS .
Quantum Error Correction and Fault Tolerance 197
We use the notation [[n, k, d]] to a refer to such a
stabilizer code. Note that the square brackets specify
that the code is a stabilizer code, and that the middle
term k refers to the number of encoded qubits, and
not the dimension 2
k
of the encoded subspace, as for
the general QECC (whose dimension mi ght not be a
power of 2).
S
?
is the set of Pauli operators that commute with
all elements of the stabilizer. They would therefore
appear to be those errors which cannot be detected
by the code. However, the theorem specifies the
distance of the code by considering S
?
nS . A Pauli
operator P 2 S cannot be detected by the code, but
there is in fact no need to detect it, since all code
words remain fixed under P, making it equivalent to
the identity operation. A distance d stabilizer code
which has nontrivial P 2 S with wt(P) < d is called
degenerate, whereas one which does not is non-
degenerate. The phenomenon of degeneracy has no
analog for classical error-correcting codes, and
makes the study of quantum codes substan tially
more difficult than the study of classical error
correction. For instance, a standard bound on
classical error correction is the Hamming bound
(or sphere-packing bound), but the analogous
quantum Hamming bound
k=n 1 ðt=nÞlog 3 hðt=nÞ½7
for [[ n, k,2t þ 1]] codes (when n is large) is only
known to apply to nondegenerate quantum codes
(though in fact we do not know of any degenerate
QECCs that violate the quantum Hamming bound).
An example of a stabilizer code is the 5-qubit
code, a [[5,1,3]] code whose stabilizer can be
generated by
X Z Z X I
I X Z Z X
X I X Z Z
Z X I X Z
The 5-qubit code is a nondegenerate code, and is the
smallest possible QECC which corrects 1 error (as
one can see from the quantum Singleton bound).
It is frequently useful to consider other represen-
tations of stabilizer codes. For instance, P 2P
n
can
be represented by a pair of n-bit binary vectors
(p
X
jp
Z
), where p
X
is 1 for any location where P has
an X or Y tensor factor and is 0 elsewhere, and p
Z
is 1 for any location where P has a Y or Z tensor
factor. Two Pauli operators P = (p
X
jp
Z
)and
Q = (q
X
jq
Z
) commute iff p
X
q
Z
þ p
Z
q
X
= 0.
Then the stabilizer for a code becomes a pair of
(nk) n binary matrices, and most interesting
properties can be determined by an appropriate
linear algebra exercise. Another useful representa-
tion is to map the single-qubit Pauli operators I, X,
Y, Z to the finite field GF(4), which sets up a
connection between stabilizer codes and a subset of
classical codes on four-dimensional registers.
CSS Codes
CSS codes are a very useful class of stabilizer codes
invented by Calderbank and Shor (1996), and by
Steane (1996). The construction takes two binary
classical linear codes and produces a quantum code,
and can therefore take advantage of much existing
knowledge from classical coding theory. In addition,
CSS codes have some very useful properties which
make them excellent choices for fault-tolerant
quantum computation.
A classical [n, k, d] linear code (n physical bits, k
logical bits, classical distance d) can be defined in
terms of an (n k) n binary ‘‘parity check’’ matrix
H – every classical code word v must satisfy Hv = 0.
Each row of the parity check matrix can be
converted into a Pauli operator by replacing each 0
with an I operator and each 1 with a Z operator.
Then the stabilizer code generated by these opera-
tors is precisely a quantum version of the classical
error-correcting code given by H. If the classical
distance d = 2t þ 1, the quantum code can correct t
bit flip (X) errors, just as could the classical code.
If we want to make a QECC that can also correct
phase (Z) errors, we should choose two classical
codes C
1
and C
2
, with parity check matrices H
1
and
H
2
. Let C
1
be an [n, k
1
, d
1
] code and let C
2
be an
[n, k
2
, d
2
] code. We convert H
1
into stabilizer
generators as above, replacing each 0 with I and
each 1 with Z. For H
2
, we perform the same
procedure, but each 1 is instead replaced by X. The
code will be able to correct bit flip (X) errors as if it
had a distance d
1
and to correct phase ( Z) errors as
if it had a distance d
2
. Since these two operations are
completely separate, it can also correct Y errors as
both a bit flip and a phase error. Thus, the distance
of the quantum code is at least min (d
1
, d
2
), but
might be higher because of the possibility of
degeneracy.
However, in order to have a stabilizer code at all,
the generators produced by the above procedure
must commute. Define the dual C
?
of a classical
code C as the set of vectors w s.t. w v = 0 for all
v 2 C. Then the Z generators from H
1
will all
commute with the X generators from H
2
iff C
?
2
C
1
(or equivalently, C
?
1
C
2
). When this is true, C
1
and C
2
define an [[n, k
1
þ k
2
n, d]] stabilizer code,
where d min (d
1
, d
2
).
198 Quantum Error Correction and Fault Tolerance
The smallest distance-3 CSS code is the 7-qubit
code, a [[7, 1, 3]] QECC created from the classical
Hamming code (consisting of all sums of classical
strings 1111000, 1100110, 1010101, and 1111111).
The encoded j
0i for this code consists of the
superposition of all even-weight classical code
words and the encoded j
1i is the superposition of
all odd-weight classical code words. The 7-qubit
code is much studied because its properties make it
particularly well suited to fault-tolerant quantum
computation.
Fault Tolerance
Given a QECC, we can attempt to supplement it
with protocols for performing fault-tolerant opera-
tions. The basic design principle of a fault-tolerant
protocol is that an error in a single location – either
a faulty gate or noise on a quiescent qubit – should
not be able to alter more than a single qubit in each
block of the QECC. If this condition is satisfied, t
separate single-qubit or single-gate failures are
required for a distance 2t þ 1 code to fail.
Particular caution is necessary, as computational
gates can cause errors to propagate from their
original location onto qubits that were previously
correct. In general, a gate coupling pairs of qubits
allows errors to spread in both directions across the
coupling.
The solution is to use transversal gates whenever
possible (Shor 1996). A transversal operation is one
in which the ith qubit in each block of a QECC
interacts only with the ith qubit of other blocks of
the code or of special ancilla states. An operation
consisting only of single-qubit gates is automatically
transversal. A transversal operation has the virtue
that an error occurring on the third qubit in a block,
say, can only ever propagate to the third qubit of
other blocks of the code, no matter what other
sequence of gates we perform before a complete
error-correction procedure.
In the case of certain codes, such as the 7-qubit
code, a number of different gates can be performed
transversally. Unfortunately, it does not appear to
be possible to perform universal quantum compu-
tations using just transversal gates. We therefore
have to resort to more complicated techniques.
First we create special encoded ancilla states in a
non-fault-tolerant way, but perform some sort of
check on them (in addition to error correction) to
make sure they are not too far off from the goal.
Then w e interact the ancilla with the encoded data
qubits using gates from our stock of transversal
gates and perform a fault-tolerant measurement.
Then we complete the operation with a further
transversal gate which depends on the outcome of
the measurement.
Fault-Tolerant Gates
We will focus on stabilizer codes. Universal fault
tolerance is known to be possible for any stabilizer
code, but in most cases the more complicated type
of construction is needed for all but a few gates. The
Pauli group P
k
, however, can be performed trans-
versally on any stabilizer code. Indeed, the set S
?
nS
of undetectable errors is a boon in this case, as it
allows us to perform these gates. In particular, each
coset S
?
=S corresponds to a different logical Pauli
operator (with S itself corresponding to the identity).
On a stabilizer code, therefore, logical Pauli opera-
tions can be performed via a transversal Pauli
operation on the physical qubits.
Stabilizer codes have a special relationship to a
finite subgroup C
n
of the unitary group U(2
n
)
frequently called the ‘‘Clifford group.’’ The Clifford
group on n qubits is defined as the set of unitary
operations which conjugate the Pauli group P
n
into
itself; C
n
can be generated by the Hadamard trans-
form, the controlled-NOT (CNOT), and the single-
qubit =4 phase rotation diag(1, i). The set of
stabilizer codes is exactly the set of codes which can
be created by a Clifford group encoder circuit using
j0i ancilla states.
Some stabilizer codes have interesting symmetries
under the action of certain Clifford group elements,
and these symmetries result in transversal gate
operations. A particularly useful fact is that a
transversal CNOT gate (i.e., CNOT acting between
the ith qubit of one block of the QECC and the ith
qubit of a second block for all i) acts as a logical
CNOT gate on the encoded qubits for any CSS code.
Furthermore, for the 7-qubit code, transversal
Hadamard performs a logical Hadamard, and the
transversal =4 rotation performs a logical =4
rotation. Thus, for the 7-qubit code, the full logical
Clifford group is accessible via transversal
operations.
Unfortunately, the Clifford group by itself does
not have much computational power: it can be
efficiently simulated on a classical computer.
We need to add some additional gate outside
the Clifford group to allow universal quantum
computation; a single gate will suffice, such as the
single-qubit =8 phase rotation diag(1, exp (i=4)).
Note that this give s us a finite generating set of
gates. However, by taking appropriate products, we
get an infinite set of gates, one that is dense in the
unitary group U(2
n
), allowing universal quantum
computation.
Quantum Error Correction and Fault Tolerance 199
The following circuit performs a =8 rotation,
given an ancilla state j
=8
i= j0iþexp (i=4)j1i:
PX
⏐
ψ
π/8
〉
Here P is the =4 phase rotation diag(1, i), and X
is the bit flip. The product is in the Clifford group,
and is only performed if the measurement outcome
is 1. Therefore, given the ability to perform fault-
tolerant Clifford group operations, fault-tolerant
measurements, and to prepare the encoded j
=8
i
state, we have universal fault-tolerant quantum
computation. A slight generalization of the fault-
tolerant measurement procedure below can be used
to fault-tolerantly verify the j
=8
i state, which is a
þ1 eigensta te of PX. Using this or another verifica-
tion procedure, we can check a non-fault-tolerant
construction.
Fault-Tolerant Measurement
and Error Correction
Since all our gates are unreliable, including those
used to correct errors, we will need some sort of
fault-tolerant quantum error-correction procedure.
A number of different techniques have been devel-
oped. All of them share some basic features: they
involve creation and verification of specialized
ancilla states, and use transversal gates which
interact the data block with the ancilla state.
The simplest method, due to Shor, is very general
but also requires the most overhead and is
frequently the most susceptible to noise. Note that
the following procedure can be used to measure
(non-fault-tolerantly) the eigenvalue of any (possibly
multiqubit) Pauli operator M: produce an ancilla
qubit in the state jþi= j0iþj1i. Perform a con-
trolled-M operation from the ancilla to the state
being measured. In the case where M is a multiqubit
Pauli operator, this can be broken down into a
sequence of controlled-X, controlled-Y, and con-
trolled-Z operations. The n measure the ancilla in the
basis of jþi and ji= j0ij1i. If the state is a þ1
eigenvector of M, the ancilla will be jþi, and if the
state is a 1 eigenvector, the ancilla will be ji.
The advantage of this procedure is that it
measures just M and nothing more. The disadvan-
tage is that it is not transversal, and thus not fault
tolerant. Instead of the unencoded jþi state, we
must use a more complex ancilla state j00 ...0iþ
j11 ...1i known as a ‘‘cat’’ state. The cat state
contains as many qubits as the operator M to
be measured, and we perform the controlled-X,-Y,
or -Z operations transversally from the appropriate
qubits of the cat state to the appropriate qubits in
the data block. Since, assuming the cat state is
correct, all of its qubits are either j0i or j1i, the
procedure either leaves the data state alone or
performs M on it uniformly. A þ1 eigenstate in the
data therefore leaves us with j
00 ...0iþj11 ...1i in
the ancilla and a 1 eigenstate leaves us with
j00 ...0ij11 ...1i. In either case, the final state
still tells us nothing about the data beyond the
eigenvalue of M. If we perform a Hadamard
transform and then measure each qubit in the
ancilla, we get either a random even-weight string
(for eigenvalue þ1) or an odd-weight string (for
eigenvalue 1).
The pro cedure is transversal, so an error on a
single qubit in the initial cat state or in a single gate
during the interaction will only produce one error in
the data. However, the initial construction of the cat
state is not fault tolerant, so a single-gate error then
could eventually produce two errors in the data
block. Therefore, we must be careful and use some
sort of technique to verify the cat state, for instance,
by checking if random pairs of qubits are the same.
Also, note that a single phase error in the cat state
will cause the final measurement outcome to be
wrong (even and odd switch places), so we should
repeat the measurement procedure multiple times
for greater reliability.
We can then make a full fault-tolerant error-
correction procedure by performing the above
measurement technique for each generator of the
stabilizer. Each measurement gives us one bit of the
error syndrome, which we then decipher classically
to determine the actual error.
More sophisticated techniques for faul t-tolerant
error correction involve less interaction with the
data but at the cost of more complicated ancilla
states. A procedure due to Steane uses (for CSS
codes) one ancilla in a logical j
0i state of the same
code and one ancilla in a logical j
0iþj
1i state. A
procedure due to Knill (for any stabilizer code)
teleports the data qubit through an ancilla consisting
of two blocks of the QECC containing an encoded
Bell state j
00iþj11i. Because the ancillas in Steane
and Knill error correction are more complicated
than the cat state, it is especially im portant to verify
the ancillas before using them.
The Threshold for Fault Tolerance
In an unencoded protocol, even one error can
destroy the computation, but a fully fault-tolerant
protocol will give the right answer unless multiple
200 Quantum Error Correction and Fault Tolerance
errors occur before they can be corrected. On the
other hand, the fault-tolerant protocol is larger,
requiring more qubits and more time to do each
operation, and therefore providing more opportu-
nities for errors. If errors occur on the physical
qubits independently at random with probability p
per gate or time step, the fault-tolerant protocol has
probability of logical error for a single logical gate
or time step at most Cp
2
, where C is a constant that
depends on the design of the fault-tolerant circuitry
(assume the QECC has distance 3, as for the 7-qubit
code). When p < p
t
= 1=C, the fault tolerance helps,
decreasing the logical error rate. p
t
is the ‘‘thresh-
old’’ for fault-tolerant quantum computation. If the
error rate is higher than the thres hold, the extra
overhead means that errors will occur faster than
they can be reliably corrected, and we are better off
with an unencoded system.
To further lower the logical error rate, we turn to
a family of codes known as ‘‘concatenated codes’’
(Aharonov and Ben-Or, Kitaev 1997, Knill et al.
1998). Given a code word of a particular [[n, 1]]
QECC, we can take each physical qubit and again
encode it using the same code, producing an [[n
2
, 1]]
QECC. We could repeat this procedure to get an n
3
-
qubit code, and so forth. The fault-tolerant proce-
dures concatenate as well, an d after L levels of
concatenation, the effective logical error rate is
p
t
(p=p
t
)
2
L
(for a base code correcting 1 error).
Therefore, if p is below the threshold p
t
, we can
achieve an arbitrarily good error rate per logical
gate or time step using only poly( log ) resources,
which is excellent theoretical scaling.
Unfortunately, the practical requirements for this
result are not nearly so good. The best rigorous
proofs of the threshold to date show that the
threshold is at least 2 10
5
(meaning one error
per 50,000 operations). Optimized simulations of
fault-tolerant protocols suggest that the true thresh-
old may be as high as 5%, but to tolerate this much
error, existing protocols require enormous overhea d,
perhaps increasing the number of gates and qubits
by a factor of a million or more for typical
computations. For lower physical error rates, over-
head requirements are more modest, particularly if
we only attempt to optimize for calculations of a
given size, but are still larger than one would like.
Furthermore, these calculations make a number of
assumptions about the physical properties of the
computer. The errors are assumed to be independent
and uncorrelated between qubits except when a gate
connects them. It is assumed that measurements and
classical comput ations can be performed quickly
and reliably, and that quantum gates can be
performed between arbitrary pairs of qubits in the
computer, irrespective of their physical proximity.
Of these, only the assumption of independent errors
is at all necessary, and that can be considerably
relaxed to allow short-range correlations and certain
kinds of non-Markovian environments. However,
the effects of relaxing these assumptions on the
threshold value and overhead requirements have not
been well studied.
Further Reading
Aharonov D and Ben-Or M (1999) Fault-tolerant quantum
computation with constant error rate, quant-ph/9906129.
Bennett C, DiVincenzo D, Smolin J, and Wootters W (1996)
Mixed state entanglement and quantum error correction.
Physical Review A 54: 3824–3851 (quant-ph/9604024).
Calderbank AR and Shor PW (1996) Good quantum error-
correcting codes exist. Physical Review A 54: 1098–1105
(quant-ph/9512032).
Calderbank AR, Rains EM, Shor PW, and Sloane NJA (1998)
Quantum error correction via codes over GF(4). IEEE
Transactions on Information Theory 44: 1369–1387 (quant-
ph/9605005).
Gottesman D (1996) Class of quantum error-correcting codes
saturating the quantum Hamming bound. Physical Review A
54: 1862–1868 (quant-ph/9604038).
Kitaev AY (1997) Quantum error correction with imperfect gates.
In: Hirota O, Holeva AS, and Caves CM (eds.) Quantum
Communication, Computing, and Measurement (Proc. 3rd
Int. Conf. of Quantum Communication and Measurement),
pp. 181–188. New York: Plenum.
Knill E and Laflamme R (1997) A theory of quantum error-
correcting codes. Physical Review A 55: 900–911 (quant-ph/
9604034).
Knill E, Laflamme R, and Zurek WH (1998) Resilient quantum
computation. Science 279: 342–345.
Shor PW (1996) Fault-tolerant quantum computation. In: Proc. 35th
Ann. Symp. on Fundamentals of Computer Science, pp. 56–65.
(quant-ph/9605011). Los Alamitos: IEEE Press.
Steane AM (1996) Multiple particle interference and quantum
error correction. Proceedings of the Royal Society of London
A 452: 2551–2577 (quant-ph/9601029).
Quantum Error Correction and Fault Tolerance 201