Content-Type: multipart/mixed; boundary="-------------9906290353163"
This is a multi-part message in MIME format.
---------------9906290353163
Content-Type: text/plain; name="99-245.keywords"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="99-245.keywords"
Pauli exchange, quantum computing, error correction
---------------9906290353163
Content-Type: application/x-tex; name="pauli9btok2.tex"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="pauli9btok2.tex"
%\documentstyle[aps,twocolumn]{revtex}
\documentclass[12pt]{article}
% \usepackage{amsfonts}
% \usepackage{amssymb}
\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{defn}[thm]{Definition}
\def\pf{\medbreak\noindent{\bf Proof:}\enspace}
\def\lanbox{{$\, \vrule height 0.25cm width 0.25cm depth 0.05mm \,$}}
\def\qed{{\bf QED}}
\def\iff{\Longleftrightarrow}
\def\half{{\textstyle \frac{1}{2}}}
\def\tr{\hbox{Tr}}
\def\fm{\lfloor m \rfloor}
\def\Hil{{\cal H}}
\newcommand\binom[2]{ \left( \begin{array}{c}{#1}\\{#2} \end{array} \right)}
\def\cP{{\cal P}}
\def\shan{{\rm Shan}}
\def\holv{{\rm Holv}}
\def\ds{\displaystyle}
\def\ts{\textstyle}
\def\bra{\langle}
\def\ket{\rangle}
\def\kb{ \ket \bra }
\def\trho{ \tilde{\rho} }
\def\rt2{ \frac{1}{\sqrt{2}} }
\def\lraw{\leftrightarrow}
\def\raw{\rightarrow}
\def\uparw{\uparrow}
\def\dwnarw{\downarrow}
\def\half{{\textstyle \frac{1}{2}}}
\def\frth{{\textstyle \frac{1}{4}}}
\def\PE{ {\rm ProbErr} }
\def\MPE{ {\rm MinProbErr} }
\def\nl{\newline}
\title{Pauli Exchange Errors in Quantum Computation}
\author {Mary Beth Ruskai \thanks{Partially supported by National Science
Foundation Grant DMS-97-06981 and Army Research Office Grant
DAAG55-98-1-0374} \\ Department of
Mathematics \\ University of Massachusetts Lowell \\ Lowell,
MA 01854 USA}
\begin{document}
\maketitle
\begin{abstract}
We argue that a physically reasonable model of fault-tolerant
computation requires the ability to correct a type of two-qubit
error which we call Pauli exchange errors as well as one qubit
errors. We give an explicit 9-qubit code which can handle
both Pauli exchange errors and all one-bit errors.
\end{abstract}
Most discussions of quantum error correction assume, at least
implicitly, that errors result from interactions with the
environment and that single qubit errors are much more likely
than two qubit errors. Most discussions also ignore the
Pauli exclusion principle and permutational symmetry of the
states describing multi-qubit systems. Although this can be
justified by consideration of the full wave function, including
spatial as well as spin components, an analysis of these
more complete wave functions suggests that an important
source of error has been ignored. Exchange of identical
particles and interactions between qubits give rise to a type of
error, not seen classically, in which a {\em single} exchange error
can affect two qubits.
\bigskip
A (pure) state of a quantum mechanical particle with spin $q$
corresponds to a one-dimensional subspace of the Hilbert space
${\cal H} = {\bf C}^{2q+1} \otimes L^2({\bf R}^3)$ and is typically
represented by a vector in that subspace. The state of a
system of $N$ such particles is then represented by a vector
$\Psi(x_1,x_2,\ldots,x_N)$ in ${\cal H}^N$. However, when dealing
with identical particles $\Psi$ must also satisfy the Pauli
principle, i.e., it must be symmetric or anti-symmetric under
exchange of the coordinates $x_j \leftrightarrow x_k$ depending
on whether the particles in question are bosons (e.g. photons)
or fermions (e.g., electrons). In either case, we can write
the full wave function in the form
\begin{eqnarray}
\Psi(x_1,x_2,\ldots,x_N) = \sum_k b_k
\chi_k(s_1,s_2,\ldots,s_N) \Phi_k({\bf r}_1,{\bf r}_2,\ldots,{\bf r}_N)
\end{eqnarray}
where the ``space functions" $\Phi_k$ are elements of
$L^2({\bf R}^{3N})$, the ``spin functions" $\chi_k$ are in
$[{\bf C}^{2q+1}]^N$ and $x_k = ({\bf r}_k,s_k)$
with ${\bf r}$ with a vector in ${\bf R}^3$ and the so-called
"spin coordinate" $s_k$ in $0, 1, \ldots 2q$.
[In the parlance of quantum computing a spin states $\chi$
is a (possibly entangled) N-qubit state.] It
is not necessary that $\chi$ and $\Phi$ each satisfy the Pauli
principle; indeed, when $q= \half$ so that $2q+1 = 2$ and we
are dealing with ${\bf C}^2$ it is {\em not} possible for $\chi$
to be anti-symmetric when $N \geq 3$. Instead, we
expect that $\chi$ and $\Phi$ satisfy certain duality conditions
which guarantee that $\Psi$ has the correct permutational symmetry.
(For example, antisymmetric $\Psi$ arise when the
states $\chi_k$ and $\Phi_k$ form bases for irreducible
representations of the symmetric group with dual Young tableaus.)
With this background, we now restrict attention to the
important special case in which $q = \half$ yielding
two spin states labeled so that $s = 0$ corresponds to $|0\ket$
and $s = 1$ corresponds to $|1\ket$,
and the particles are electrons so that $\Psi$ must
be anti-symmetric. Although analogous considerations apply in other
cases, the additional component of electron-electron interaction implies
that Pauli exchange errors are particularly important in this case.
We present our brief for the importance of Pauli exchange
errors by analyzing the two-qubit case in detail.
For multi-particle states, it is sometimes convenient to
replace $|0\ket$ and $|1\ket$ by $\uparw$ and $\dwnarw$ respectively.
Thus, the notation $|01\ket$ describes a two-qubit state in which the
particle in the first qubit has spin ``up'' ($\uparrow$) and that
in the second qubit spin ``down'' ($\downarrow$). What does it
mean for a particle to ``be'' in a qubit? A reasonable model
is that each qubit corresponds to some type of well in which
a particle is trapped if the spatial component of its wave
function is $f_A({\bf r})$ where $A, B, C \ldots$ label the
wells and wave functions for different wells are orthogonal.
Thus, we write
\begin{eqnarray}\label{psi01}
|01\ket = \rt2 \Big( [f_A({\bf r_1})\uparw ]~[ f_B({\bf r_2})\dwnarw]
- [ f_B({\bf r_1})\dwnarw ]\frac{}{}[ f_A({\bf r_2})\uparw ] \Big).
\end{eqnarray}
Notice that the electron whose spatial function is $f_A$ always
has spin ``up'' regardless of whether its coordinates are
labeled by $1$ or $2$. We can rewrite this as
\begin{eqnarray}\label{eq:twobit}
|01\ket = \rt2 \left[ \chi^+ \phi^- + \chi^- \phi^+ \right]
\end{eqnarray}
where $\chi^{\pm}(s_1,s_2) = \rt2 \left[ |01\ket \pm |10\ket \right]$
denotes the indicated Bell states and
$\phi^{\pm}({\bf r_1}{\bf r_2}) = \rt2 \left[f_A({\bf r_1}) f_B({\bf
r_2}) \pm f_B({\bf r_1}) f_A({\bf r_2}) \right] .$
If the Hamiltonian $H$ is spin-free, then the time development of
(\ref{psi01}) is determined by $e^{iHt} \phi^{\pm}$.
Since we assumed the particles
are electrons, $H$ must include a term corresponding
to the $\frac{1}{r_{12}} \equiv \frac{1}{|{\bf r_1}-{\bf r_2}|}$
electron-electron interaction. Since the Hamiltonian must be
symmetric, the states
$\phi^{\pm}$ retain their permutational symmetry; however, the
presence of the electron-electron interaction suggests that they
cannot retain the simple form of symmetrized (or anti-symmetrized)
product states. Hence, after some time the states $\phi^{\pm}$
evolve into
\begin{eqnarray*}
\Phi^- ({\bf r_1, r_2}) & = & \sum_{m < n} c_{mn} \rt2 \left[
f_m({\bf r_1}) f_m({\bf r_2}) - f_n({\bf r_1}) f_m({\bf r_2}) \right] \\
\Phi^+ ({\bf r_1, r_2}) & = & \sum_{m \leq n} d_{mn} \rt2 \left[
f_m({\bf r_1}) f_m({\bf r_2}) + f_n({\bf r_1}) f_m({\bf r_2}) \right].
\end{eqnarray*}
where $f_m$ denotes any orthonormal basis whose first two elements
are $f_A$ and $f_B$ respectively.
There is no reason to expect that $c_{mn} = d_{mn}$ in general.
On the contrary, only the symmetric sum includes pairs with $m = n$.
Hence if one $d_{mm} \neq 0$, then one must have some
$c_{mn} \neq d_{mn}.$
Inserting this in (\ref{eq:twobit}) yields
\begin{eqnarray}\label{eq:twobittime}
\nonumber e^{iHt} |01 \ket & = & (c_{AB} + d_{AB})
\Big( [f_A({\bf r_1})\uparw ]~[ f_B({\bf r_2})\dwnarw]
- [ f_B({\bf r_1})\dwnarw ]\frac{}{}[ f_A({\bf r_2})\uparw ] \Big) \\
\nonumber & ~ & + (c_{AB} - d_{AB})
\Big( [f_B({\bf r_1})\uparw ]~[ f_A({\bf r_2})\dwnarw]
- [ f_A({\bf r_1})\dwnarw ]\frac{}{}[ f_B({\bf r_2})\uparw ] \Big) \\
& ~ & + \Psi^{\rm Remain} \nonumber \\
& = & (c_{AB} + d_{AB}) |01 \ket + (c_{AB} - d_{AB}) |10 \ket +
\Psi^{\rm Remain}
\end{eqnarray}
where $\Psi^{\rm Remain}$ is orthogonal to $\phi^{\pm}$.
A measurement of qubit-A (or B) corresponds to projecting onto $f_A$
(or $f_B$). Hence a measurement of qubit-A on the state (\ref{eq:twobit})
yields spin ``up'' with with probability $|c_{AB} + d_{AB}|^2$
and spin down with probability $|c_{AB} - d_{AB}|^2$,
and zero with probability $\| \Psi^{\rm Remain} \|^2$. Note
that the {\em full} wave function is {\em necessarily} an {\em entangled}
state and that the measurement process leaves the system in
state $|10 \ket$ or $|01 \ket$ with probabilities
$|c_{AB} \pm d_{AB}|^2$ respectively, i.e., subsequent measurement
of qubit-B always gives the opposite spin. With probability
$|c_{AB} - d_{AB}|^2$ the initial state $|10 \ket$ has been
converted to $|01 \ket$
Although the probability of this is small, it is not zero.
Precise estimates would require a more detailed model
of the actual experimental implementation.
However, it would seems that any
implementation which provides a mechanism for two-qubit
gates would necessarily involve a model in which the
interactions between particles in different qubits is at
least as large as their interaction with the environment.
Since the environment is assumed to be the cause of one-bit
errors, Pauli exchange errors seems at least as likely and
worthy of more attention.
If the implementation involves charged particles,
such as electrons in ion traps, then the interaction includes a
contribution from the $\frac{1}{r_{12}}$ Coulomb potential
which is known to have long-range effects. This suggests
that implementations involving neutral particles, such as
Briegel, et al's proposal \cite{BCJCZ} using optical lattices, may be
advantageous for minimizing exchange errors.
\bigskip
A Pauli exchange error is a special type of ``two-qubit" error
which has the same effect as ``bit flips" if (and {\it only} if)
they are different. Exchange of bits $j$ and $k$ is equivalent
to acting on a state with the operator
\begin{eqnarray}\label{def:Ejk}
E_{jk} = \half \Big( I_j \otimes I_k + Z_j \otimes Z_k
+ X_j \otimes X_k + Y_j \otimes Y_k \Big)
\end{eqnarray}
where $X_j, Y_j, Z_j$ denote the action of the Pauli matrices
$\sigma_x, \sigma_y, \sigma_z$ respectively on the bit $j$.
One can easily verify that
\begin{eqnarray*}
\half \Big( I_j \otimes I_k + Z_j \otimes Z_k \Big)
|s_1, s_2 \ldots s_N \ket & = & \delta_{s_j,s_k} \\
\half \Big( X_j \otimes X_k + Y_j \otimes Y_k \Big)
|s_1, s_2 \ldots s_N \ket & = &
\delta_{s_j,s_k+1 } = 1 - \delta_{s_j,s_k}
\end{eqnarray*}
%pagebreak
As an example, we consider Pauli exchange errors
in the simple 9-bit code of Shor \cite{Shor}
\begin{eqnarray} \label{Shorcode}
| c_0 \ket & = & \half \Big( |000000000\ket
+ |000111111\ket + |111000111\ket + |111111000\ket \Big) \nonumber \\
& = & \half \Big( |{\bf 000} \ket + |{\bf 011} \ket +
|{\bf 101} \ket + |{\bf 110} \ket \Big) \\
| c_1 \ket & = & \half \Big( |111111111\ket +
|111000000\ket + |000111000\ket + |000000111\ket \Big) \nonumber \\
& = & \half \Big( |{\bf 111} \ket +
|{\bf 100} \ket + |{\bf 010}\ket + |{\bf 001} \ket \Big)
\end{eqnarray}
where we have used boldface to denote a triplet of 0's or 1's.
It is clear that these code words are invariant under exchange
of electrons within the 3-qubit triples (1,2,3), (4,5,6), or (7,8,9).
To see what happens when electrons in different triplets are
exchanged, consider the exchange $E_{34}$.
\begin{eqnarray*}
E_{34} | c_0 \ket & = & \half \Big( |000000000\ket + |001011111\ket +
|110100111\ket + |111111000\ket \Big) \\
& = & \half \Big( | c_0 \ket + Z_8 | c_0 \ket +
|001011111\ket + |110100111\ket \Big) \\
E_{34} | c_1 \ket & = & \half \Big( |111111111\ket +
|110100000 \ket + |001011000 \ket + |000000111\ket \Big) \\
& = & \half \Big( | c_1 \ket - Z_8 | c_1 \ket
+ |110100000 \ket + |001011000 \ket \Big)
\end{eqnarray*}
If $|\psi \ket = a | c_0 \ket + b | c_1 \ket$ is a superposition
of code words,
\begin{eqnarray*}
E_{34} |\psi \ket = \half \Big( |\psi \ket +
Z_2 | \tilde{\psi} \ket \Big) + \rt2 | \gamma \ket
\end{eqnarray*}
where $ | \tilde{\psi} \ket = a | c_0 \ket - b | c_1 \ket$ differs
from $\psi$ by a ``phase error" on the code words and $| \gamma \ket$
is orthogonal to the space of codewords and single bit errors.
Therefore, this code cannot reliably distinguish between an exchange
error $E_{34}$ and a phase error on any of the last 3 bits. This
problem arises because if we write
\begin{eqnarray}\label{eq:Shor.prob}
E_{34} | c_0 \ket = \half \Big( | c_0 \ket + | d_0 \ket \Big)
\end{eqnarray}
then $| d_0 \ket = \half \Big( |001011111\ket + |110100111\ket
- |000111111\ket - |111000111\ket \Big)$ is not orthogonal
to the codewords.
\bigskip
In order to be able to correct a given class of errors, we first identify
a set of basic errors $e_p$ in terms of which all other errors can
be written as linear combinations. In the case of unitary transformations
on single bit, or one-qubit errors, this set usually consists of
$X_k, Y_k, Z_k ~~ (k= 1 \ldots n)$ where $n$ is the number of qubits in
the code and $X_k, Y_k, Z_k$ now denote
$I \otimes I \otimes I \ldots\otimes \sigma_p \otimes \ldots \otimes I$
where $ \sigma_p $ denotes one of the three Pauli matrices acting
on qubit-k. If we let $e_0 = I$ denote the identity, then a
sufficient condition for error correction is
\begin{eqnarray}\label{err.orthog}
\bra e_p C_i | e_q C_j \ket = \delta_{ij} \delta_{pq}
\end{eqnarray}
However, this condition is not necessary and can be replaced
\cite{CRSS} by the weaker condition
\begin{eqnarray}\label{err.suff}
\bra e_p C_i | e_q C_j \ket = \delta_{ij} d_{pq}
\end{eqnarray}
where the matrix $D$ with elements $d_{pq}$ is independent of $i,j$.
When considering Pauli exchange errors, it is natural to seek codes
which are invariant under some subset of permutations. This is
clearly incompatible with (\ref{err.orthog}) since some of the exchange
errors will then satisfy $ E_{jk} | C_i \ket = | C_i \ket $.
Hence we will need to use (\ref{err.suff}).
The most common code words have the
property that $| C_1 \ket $ can be obtained from $| C_0 \ket$
by exchanging all 0's and 1's. For such codes, it is not
hard to see that
$ \bra C_1 | Z_k C_1 \ket = - \bra C_0 | Z_k C_0 \ket $
which is consistent with (\ref{err.suff}) if and only if
it is identically zero.
Hence even when using (\ref{err.suff}) rather than (\ref{err.orthog})
it is necessary to require
\begin{eqnarray}\label{eq:dualphase}
\bra C_1 | Z_k C_1 \ket = - \bra C_0 | Z_k C_0 \ket = 0
\end{eqnarray}
when the code words are related in this complementary way.
\bigskip
We now present a 9-bit code code which
can handle both Pauli exchange errors and all one-bit errors.
It is based on the realization that codes
which are invariant under permutations are impervious to
Pauli exchange errors .
Let
\begin{eqnarray}\label{code9}
| C_0 \ket & = & |000000000\ket +
\frac{1}{\sqrt{28}} \sum_{\cP} |111111000\ket \nonumber \\
& = & |{\bf 000} \ket + \frac{1}{\sqrt{28}} \sum_{\cP} |{\bf 100} \ket \\
| C_1 \ket & = & |111111111\ket +
\frac{1}{\sqrt{28}} \sum_{\cP} |000000111\ket \nonumber \\
& = & |{\bf 111} \ket + \frac{1}{\sqrt{28}} \sum_{\cP} |{\bf 011} \ket
\end{eqnarray}
where $\sum_{\cP}$ denotes the sum over all permutations of the
indicated sequence of 0's and 1's and it is understood that we
count permutations which result in identical vectors only once.
As before, boldface denotes a triple , but $\sum_{\cP}$ includes
permutations between triples (rather than {\em of} triples).
This differs from the 9-bit Shor code in that
{\em all} permutations of $|111111000\ket$ are included,
rather than only three. The normalization of the code words is
$\bra C_i | C_i \ket = 1 + \frac{1}{\sqrt{28}} \binom {9}{3} = 4$.
The coefficient $1/\sqrt{28}$ is needed to satisfy (\ref{eq:dualphase}).
Simple combinatorics implies
\begin{eqnarray*}
\bra C_i | Z_k C_i \ket =
(-1)^i \left[ 1 - \frac{1}{3}\binom{9}{3}\frac{1}{28} \right]
= 0.
\end{eqnarray*}
Moreover,
\begin{eqnarray}\label{eq:phase.mat}
\bra Z_k C_i | Z_{\ell} C_i \ket =
1 + \delta_{k \ell} \binom {9}{3}\frac{1}{28} = 1 + 3 \delta_{k \ell} .
\end{eqnarray}
The second term in (\ref{eq:phase.mat}) is zero
when $k \neq \ell$ because of
the fortuitous fact that there are exactly the same
number of positive and negative terms. If, instead, we had
used all permutations of $\kappa$ 1's in $n$ qubits, this term would be
$\ds{\frac{(n-2 \kappa)^2 - n}{n(n-1)} }\binom{n}{\kappa}$ when
$k \neq \ell$.
Since all components of $|C_0\ket$ have $0$ or $6$ bits equal to 1,
any single bit flip acting on $|C_0\ket$, will yield a vector
whose components have $1, 5$, or $7$ bits equal to 1 and is
thus orthogonal to $|C_0\ket$, to $|C_1\ket$, to a bit flip acting
on $|C_1\ket$ and to a
phase error on either $|C_0\ket$ or $|C_1\ket$.
Similarly, a single bit flip on $|C_1\ket$ will yield a vector
orthogonal to $|C_0\ket$, to $|C_1\ket$, to a bit flip acting
on $|C_0\ket$ and to a phase error on $|C_0\ket$ or $|C_1\ket$.
However, single bit flips on a given code word
are not mutually orthogonal.
To find $\bra X_k C_i | X_{\ell} C_i \ket$ when $k \neq \ell$,
consider
\begin{eqnarray}\label{eq:bit.mat}
\bra X_k ~(\nu_1 \nu_2 \ldots \nu_9) |
X_{\ell} ~(\mu_1 \mu_2 \ldots \mu_9) \ket.
\end{eqnarray}
where $\nu_i, \mu_i$ are in $0,1$.
This will be nonzero only when
$\nu_k = \nu_{\ell} = 0, ~~ \nu_{\ell} = \mu_k = 1$ or
$\nu_k = \nu_{\ell} = 1, ~~ \nu_{\ell} = \mu_k = 0$
and the other $n-2$ bits are equal. From $\sum_{\cP}$ with
$\kappa$ of $n$ bits
equal to 1, there are $2 \binom{n-2}{\kappa-1}$ such terms. Thus, for the
code (\ref{code9}), there are 42 such terms which yields an
inner product of $\frac{42}{28} = \frac{3}{2}$ when $k \neq \ell$.
If we consider instead,
\begin{eqnarray}\label{eq:xyprod}
\bra Y_k C_i | X_{\ell} C_i \ket = - i \bra X_k Z_k C_i | X_{\ell} C_i \ket
\end{eqnarray}
for $k \neq \ell$ it is not hard to see that exactly half of the
terms analogous to (\ref{eq:bit.mat}) will occur with a positive
sign and half with a negative sign, yielding a net inner product
of zero in (\ref{eq:xyprod}).
We also find
\begin{eqnarray}
\bra Y_k C_i | X_k C_i \ket = - i \bra X_k Z_k C_i | X_k C_i \ket
= -i \bra Z_k C_i | C_i \ket = 0
\end{eqnarray}
so that $\bra Y_k C_i | X_{\ell} C_i \ket = 0 $ for all $k, \ell$.
In addition
\begin{eqnarray}
\bra Y_k C_i | Z_{\ell} C_i \ket = - i \bra X_k Z_k C_i | Z_{\ell} C_i \ket
= 0
\end{eqnarray}
for the same reason that $\bra X_k C_i | C_i \ket = 0$.
These results imply that imply (\ref{err.suff}) holds and
that the matrix $D$ is block diagonal with the form
\begin{eqnarray}
D = \left( \begin{array}{cccc}
D_0 & 0 & 0 & 0 \\
0 & D_X & 0 & 0 \\
0 & 0 & D_Y & 0 \\
0 & 0 & 0 & D_Z \end{array} \right)
\end{eqnarray}
where $D_0$ is the $37 \times 37$ matrix corresponding to the
identity and the 36 exchange errors, and
$D_X, D_Y, D_Z$ are $9 \times 9$ matrices corresponding
respectively to the $X_k, Y_k, Z_k$ single bit errors.
One easily finds that $d^0_{pq} = 4$ for all $p,q$.
The $9 \times 9$ matrices $D_X, D_Y, D_Z$ all have the form
\begin{eqnarray}\label{eq:mat.form}
d_{k \ell} = \left\{ \begin{array}{lcc}
\alpha = 4 & ~{\rm for}~ & k = \ell \\
\beta & ~{\rm for}~ & k \neq \ell \end{array} \right.
\end{eqnarray}
with $\beta =3/2$ in $D_X$ and $D_Y$
and $\beta = 1$ in $D_Z$.
Orthogonalization of this matrix is straightforward.
Since $D$ has rank $28 = 3 \cdot 9 + 1$, i.e., we are using only
a $54 < 2^6$-dimensional subspace of our $2^{9}$ dimension space
or 28 mutually orthogonal subspaces.
\bigskip
The simplicity of codes which are impervious to Pauli exchange errors because
they are invariant under permutations makes them are attractive.
However, there are few such codes. All code words necessarily have the form
\begin{eqnarray}\label{eq:permcode}
\sum_{\kappa=0}^n a_\kappa \sum_{\cP}
|\underbrace{ 1 \ldots 1}_\kappa \underbrace{ 0 \ldots 0}_{n-\kappa} \ket.
\end{eqnarray}
Condition
(\ref{err.suff}) places some severe restrictions
on the coefficient $a_\kappa.$ For example, in (\ref{code9})
only $a_0$ and $a_6$
are non-zero in $|C_0\ket$ and only $a_3$ and $a_9$ in $|C_1\ket$.
If we try to change this so that $a_0$ and $a_3$ are non-zero
in $|C_0\ket$ and $a_6$ and $a_9$ in $|C_1\ket$, then it is {\em not}
possible to satisfy (\ref{eq:dualphase}).
The 5-bit code in \cite{CRSS,LMPZ,BDSW} does not quite
have the form (\ref{eq:permcode}). Instead
\begin{eqnarray*}
|C_0\ket & = & |00000\ket + \sum_{\cP} \pm | 11000 \ket +
\sum_{\cP} | 11110 \ket \\
|C_1\ket & = & |11111\ket + \sum_{\cP} \pm | 11100 \ket +
\sum_{\cP} | 10000 \ket
\end{eqnarray*}
These code words are not
permutationally invariant because the components of
$\sum_{\cP} \pm | 11000 \ket$ and $\sum_{\cP} \pm | 11100 \ket$
do not all have the same sign. This is needed to satisfy (\ref{eq:dualphase}).
The non-additive 5-bit code in \cite{RHSS} also requires
sign changes in the $\sum_{\cP} | 10000 \ket$ term.
We do not believe that 5-bit codes can handle Pauli exchange errors,
but have no proof.
\bigskip
However, permutational invariance, in which each code words is the
basis for a one-dimensional representation of the symmetric group,
is not the only approach to Pauli exchange errors. Our analysis of
(\ref{eq:Shor.prob}) suggests the following construction. Let
$|c_0 \ket, |d_0 \ket, |c_1 \ket, |d_1 \ket$ be four mutually orthogonal
n-bit vectors such that $|c_0 \ket, |c_1 \ket$ form a code
for one-bit errors and $|c_0 \ket, |d_0 \ket$ and $|c_1 \ket, |d_1 \ket$
are each bases of a two-dimensional representations of the symmetric
group $S_n$. If $|d_0 \ket$ and $|d_1 \ket$ are also
orthogonal to one-bit errors on the code words, then this code can correct
Pauli exchange errors as well as one-bit errors. If, in addition,
the vectors $|d_0 \ket, |d_1 \ket$ also form a code
isomorphic to $|c_0 \ket, |c_1 \ket$, then the code should also be
able to correct products of one-bit and Pauli exchange errors.
If (\ref{err.orthog}) is required and the basic error set has size
$N$ (i.e., $p = 0, 1 \ldots N-1$), then a two-word code requires
codes which lie in a space of dimension at least $2N$. For example, for
the familiar case of single-bit errors $N = 3n+1$ and, since an
n-bit code word lies in a space of dimension $2^n$, any code must
satisfy $3n+1 < 2^{n-1}$ or $n \geq 5$.
There are $\frac{n(n-1)}{2}$ possible single exchange
errors. Hence, the basic error set for correcting both single bit
and single exchange errors will have $N = \half(n^2 + 5n +2 )$ elements
and the condition $2N \leq 2^n$ implies $n \geq 7$.
Codes of the generalized stabilizer type proposed above will require
a space of dimension $4N$. Hence,
one needs $4(3n+1) \leq 2^n$ which implies $n \geq 7$.
To correct {\em all} two-bit errors as well as one-bit
errors, the basic error set will have
$N = \frac{9n(n-1)}{2} + 3n+1 = \half(9n^2 - 3n +2)$ elements
which requires $n \geq 10$. Thus it appears that correcting Pauli
exchange errors can be done with shorter codes than correcting
all two-bit errors. Moreover, further reduction in size may be possible.
Consider the simple codes
\begin{eqnarray*} \begin{array}{lll}
~ & | C_0 \ket = |000\ket & ~~ | C_1 \ket = |111\ket \\
{\rm and}~~~~~ & ~ & \\
~ & | C_0 \ket = |000\ket + \sum_{\cP} |110\ket ~~ & ~~
| C_1 \ket = |111\ket + \sum_{\cP} |011\ket
\end{array}\end{eqnarray*}
It is well-known that
the first can correct single bit flips, but not phase errors;
the second single phase errors, but not bit flips. In the first
case, the basic error set is $I, X_1, X_2, X_3$ and in the
second $I, Z_1, Z_2, Z_3$. Hence, in both cases, N = 4, and since
$n = 3$ satisfies $2n = 8 = 2^n$ one would not expect to be able
to handle additional errors. However, both codes are invariant
under permutations. Hence in both cases, basic error set can be
expanded to include all 6 exchange errors $E_{jk}$ for a total
of $N = 10$ without increasing the size of the code words.
Thus, the minimal size analysis when two-bit or exchange errors
are included does not seem straightforward.
If one requires that
code words be invariant under some permutation, that constraint
would appear to increase the size of the space.
However, some permutational invariance may hold accidentally.
Although codes which can correct Pauli exchange errors will be
larger than the minimal 5-qubit codes proposed for single-bit
error correction, this may not be a serious drawback.
For implementations of quantum computers which have a grid
structure (e.g., solid state or cold atoms) it may be natural and
advantageous to use 9-qubit codes codes which can be implemented in
$3 \times 3$ blocks. See \cite{BCJCZ} for further discussion of
this point.
Whether or not any 7-bit codes exist which can handle Pauli exchange
errors -- either via permutational invariance or the generalization
of stabilizer codes suggest above -- is an open question. We
leave the actual construction of such 7-bit codes as a challenge
for coding theorists.
\bigskip
\noindent{\bf Acknowledgment} It is a pleasure to thank Professor
Eric Carlen for a useful comment and Professor Chris King for
several helpful discussions and comments on a draft of this manuscript.
\pagebreak
\begin{thebibliography}{~~}
\bibitem{BCJCZ} H.J. Briegel, T. Calarco, D. Jaksch, J.I. Cirac,
and P. Zoller ``Quantum Computing with Neutral Atoms''
lanl preprint quant-ph/9904010.
\bibitem{BDSW} C.H. Bennett, D.P. DiVincenzo, J.A. Smolin and W.K. Wooters,
``Mixed State Entanglement and Quantum Error Correction''
{\em Phys. Rev. A} {\bf54}, 3824--3851 (1996).
\bibitem{CS} R. Calderbank and P. Shor,
``Good quantum error-correcting codes exist''
{\em Phys. Rev. A} {\bf54}, 1098--1106 (1996).
\bibitem{CRSS} R. Calderbank, E.M. Rains, P.W. Shor and N.J.A. Sloane,
``Quantum Error Correction and Orthogonal Geometry''
{\em Phys. Rev. Lett.} {\bf 78}, 405--408 (1997);
`Quantum Error Correction via Codes Over $GF(4)$''
{\em IEEE Trans. Info. Theory} (in press).
\bibitem{LMPZ} R. Laflamme, C. Miquel, J.P. Paz, W.H. Zurek,
``Perfect Quantum Error Correction Code''
{\em Phys. Rev. Lett.} {\bf 77}, 198--201 (1996).
\bibitem{RHSS} E.M. Rains, R. H. Hardin, P.W. Shor and N.J.A. Sloane,
``A Nonadditive Quantum Code'' {\em Phys. Rev. Lett.}
{\bf 79}, 953--954 (1997).
\bibitem{Shor} P. Shor,
``Scheme for reducing decoherence in quantum computer memory''
{\em Phys. Rev. A} {\bf 52}, 2493-2496 (1995).
\bibitem{St} A.M. Steane,
``Error Correcting Codes in Quantum Theory''
{\em Phys. Rev. Lett.} {\bf 77}, 793-797 (1996).
\end{thebibliography}
\end{document}
---------------9906290353163--