From: greg@math.ucdavis.edu (Greg Kuperberg)
Subject: This week in the mathematics arXiv (6 Mar - 10 Mar)
Date: 16 Mar 2000 14:17:46 -0800
Newsgroups: sci.math.research
Summary: [missing]

[deletia --djr]

This week I'd like to conclude my short discussion of quantum computation by
describing quantum error correction.  First, for comparison, what is classical
error correction?  In a finite classical error correction problem, we are given
a space of words W and a set E of possible errors, which can be given as maps
from  W to W.   For example W may be the space of binary strings of length n and
the error map e_i may be given by flipping the i'th bit. A code C is a subset
of W.  The code is said to detect errors in E if for every code word c and
every error e in E, e(c) does not lie in C-c.  (I might have said that e(c)
does not lie in C, period.  However we may have to allow errors that move some
of the word space around but happen not to disturb the code words.)  The code
is said to correct errors in E if it detects errors in E^2 (compositions of
pairs of elements of E).  In this case there is at most codeword c associated
to an erroneous word c' = e(c), regardless of the error e.  As a trivial
example, the triple repetition code aaabbbccc corrects one error in the  word
space (Z/2)^9 if an error is given by changing one bit. A less trivial example
is a code in (Z/2)^(2^n).  If you interpret elements of this word space as
functions from (Z/2)^n to Z/2, you can let C be the set of functions which are
polynomials of degree d or less for some d.  If d is much smaller than n, the
code detects many errors, because two polynomials of degree d must differ in
many places.  This is called a Reed-Muller code.

The quantum error correction problem is a linearized version of all of the
above.  Namely instead of a word space we have a finite-dimensional complex
Hilbert space H, the state space, and a self-adjoint vector space E of
Hermitian operators, the errors.  A code is a vector subspace V of H. The code
is said to detect E if for every e in E and every v in V, the projection of
e(v) onto V is proportional to v. Or in the notation of quantum mechanics,
<v|e|v> = epsilon(e) <v|v> for some dual vector epsilon on E.  (In general in
quantum mechanics two vectors |v> and |w> are interpreted as mutually exclusive
states of existence if they are orthogonal.  If we had demanded that e|v> is
orthogonal to V, it would have been strictly analagous to the condition above
that e(c) does not lie in C.  The given condition is analogous to requiring
that e(c) does not lie in C-c.) It is said to correct for E if it detects E^2. 
In the most important example of this formalism, H = Q^{tensor n} is the state
space of n qubits, where Q is  the 2-dimensional state space of a single
qubit.  The analogue of changing one bit in a classical word is applying an
operator e on Q to the i'th qubit, in other words applying  I^{tensor i-1}
tensor e tensor I^{tensor n-i}, where I is the identity operator.  In a sense
there are three possible errors for each qubit, because the set of operators
orthogonal to the operator e=I is a 3-dimensional vector space.

Once you understand this formalism, it is not hard to believe that there should
be enough room to detect or even correct errors.  For example we can consider
whether we have room for a two-state code V in the 32-dimensional state space H
of 5 qubits.  In this case the space E of 1-qubit error operators is
15-dimensional. A sufficient condition for the code to correct one error is
that the evaluation map from V tensor E to H should be a unitary embedding and
that the image should be orthogonal to V.  V tensor E is 30-dimensional, V is
2-dimensional, and H has dimension 32=30+2, so in principle there is enough
room for the code.  In fact such a code does exist, and moreover the numbers
become only more favorable (for correcting one error) if you increase the
number of qubits.

So what's an example of a quantum code? There is a class of codes, called
additive codes, found independently by Daniel Gottesman and by the quantum
computation group at AT&T that provides simple examples.   An additive code is
defined from the error model itself, by analogy with the approach of using
parity checks to define classical error-correcting binary codes.  More
explicitly, let I, X = [[0,1],[1,0]], Z = [[1,0],[0,-1]], and Y = XZ be a basis
of the operators on the state space Q of one qubit. A tensor product of n of
these operators acts on Q^{tensor n}, while a set of such products generates an
elementary abelian 2-group provided that the operators all commute.  In this
case the subspace of Q^{tensor n} fixed by the group action defines a quantum
code.  For example the six operators

    IIIXXXX  IXXIIXX  XIXIXIX  IIIZZZZ  IZZIIZZ  ZIZIZIZ

acting on Q^{tensor 7} (where I have omitted the word 'tensor') all commute and
their invariant space is 2-dimensional.  It is a quantum code, found by Steane,
that detects 3-qubit errors.  The construction is closely related to classical
Reed-Muller codes.

Let me conclude with some comments about the physical interpretation of these
results.  Certain models of anolog classical computation are unrealistic in the
sense that they draw computational power from impossibly high precision.  For
example if in your model a variable is a real number, you could in principle
encode infinitely many bits, or even infinitely many real numbers, in the
digits of a single variable. When Peter Shor and others first made progress
with quantum algorithms, some physicists viewed quantum computers as impossibly
accurate analog computers of this type. They had a rough model of error as an
*arbitrary* operator acting on the state space H, with only the constraint that
the error is small per unit of computation time. This is analogous to a
classical error correction problem in which a single error can transform any
word into any other word; even if the probability of error is small, error
correction is not possible.  What makes error correction possible is the
assumption that error is independent for different bits or qubits. Actually it
is unrealistic to require complete independence and a strict upper bound on the
number of qubits affected by an error. But it turns out (both in classical and
quantum codes) that codes that protect against independent, bounded-number
errors also protect against many other more plausible error models.  By now the
theory of quantum error correction has put to rest this particular argument
that quantum computers are impossible.

Reference: Preskill, "Reliable quantum computers" [quant-ph/9705031].

"This week in the mathematics archive" may be freely redistributed
with attribution and without modification.
[deletia --djr]
-- 
  /\  Greg Kuperberg (UC Davis)
 /  \
 \  / Visit the Math Archive Front at http://front.math.ucdavis.edu/
  \/  * The best things in life are free *