Contemporary Mathematics

Pauli Exchange and Quantum Error Correction

Mary Beth Ruskai

Abstract. In many physically realistic models of quantum computation, Pauli exchange interactions cause a special type of two-qubit errors, called exchange errors, to occur as a first order effect of couplings within the computer. We discuss the physical mechanisms behind exchange errors and codes designed to explicitly deal with them.

1. Introduction

Most discussions of quantum error correction assume, at least implicitly, that errors result from interactions with the environment^{1} 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 (given in [27]) of these more complete wave functions suggests that more attention should be given to the effect of exchange interactions within a quantum computer. Interactions between identical particles can cause an error in two bits simultaneously as a first order effect. Moreover, because they result from interactions within the quantum computer, exchange errors cannot be reduced by better isolating the quantum computer from its environment. The effect of a (single) exchange error is to flip two bits if, and only if, they are different. It is a non-classical type of error in the sense that it arises directly from a physical mechanism which occurs only in the case of identical particles which follow the rules of quantum theory. If classical systems were to exhibit this type of behavior, they would require unusual correlations which do not normally occur from first-order couplings.

Schemes for fault-tolerant computation [6, 22, 28] have been developed which treat two-bit, and even multi-bit, errors. (See, e.g., [8, 9, 11, 29] and references in [7, 23] and at the end of Chapter 10 of [20].) However, many of these, such as those arising from concatenated codes [1, 10, 23] require a large number of physical bits to represent one logical bit. Steane, in particular, has emphasized the problems associated with the size of repeatedly concatenated codes and discussed techniques [29] for coding m logical bits in n qubits. Furthermore, threshold estimates [1, 6, 12, 22, 28] are generally based on the assumption that two-bit errors are second order effects resulting from uncorrelated interactions with the environment. In those situations where exchange errors are important, shorter codes that explicitly address exchange errors can be effective.

2000 Mathematics Subject Classification. Primary 81V70; Secondary 94B60, 81R99, 81Q05.

Supported in part by National Science Foundation Grant DMS-97-06981 and Army Research Office Grant DAAG55-98-1-0374.

1We consider the “environment” as external to the quantum computer in the sense that interactions among qubits, whether or not used in the implementation of quantum gates, are not regarded as arising from the environment. Many authors follow [9] in defining the environment to include all “unwanted interactions”.

\begin{matrix}c \\ ◯ \end{matrix}2000 by author. Reproduction of this article, in its entirety, is permitted for non-commercial purposes.

A very different approach to fault tolerant computation is based on the assumption of highly correlated errors at low temperature, allowing the use of “‘decoherence free subspaces” (DFS) [14, 15]. Shortly after [27] was posted, Lidar, et al observed [16] that the existing schemes for concatenating a DFS code with a standard 5qubit code for correcting single-bit errors [15] could also correct exchange errors. This is because exchange errors on physical qubits appear as single Pauli errors on the logical bits used in DFS codes, i.e., it appears as if Pauli matrices act on the 4-qubit units which form DFS codes. Subsequently, they [17] turned this idea around to show how exchange interactions could be used to construct universal gates within the DFS scheme for quantum computation.

In section 2 we first review some of the basic principles underlying permutational symmetry of multi-particle quantum wave functions and then show how this leads to exchange errors. In Section 3 we discuss the issues associated with correction of exchange errors and present an explicit (non-additive) 9-bit code which can correct both exchange errors and all one-qubit errors. Section 3.4 contains an ambitious proposal for constructing powerful new codes using irreducible representations of the symmetric group.

2. The full wave function

2.1. Permutational symmetry. A (pure) state of a quantum mechanical particle with spin q corresponds to a one-dimensional subspace of the Hilbert space = C^{2q+1} ⊗ L^{2}(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 Ψ(x_{1}, x_{2}, …, x_{N}) in H^{N}. However, when dealing with identical particles Ψ must also satisfy the Pauli principle, i.e., it must be symmetric or anti-symmetric under exchange of the coordinates x_{j} ↔ x_{k} so that, e.g.,

Ψ(x_{2}, x_{1}, …, x_{N}) = ±Ψ(x_{1}, x_{2}, …, x_{N}). (2.1)

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

Ψ(x_{1}, x_{2}, …, x_{N}) = ∑_{k} χ_{k}(s_{1}, s_{2}, …, s_{N})Φ_{k}(r_{1}, r_{2}, …, r_{N}) (2.2)

where the “space functions” Φ_{k} are elements of L^{2}(R^{3N}), the “spin functions” χ_{k} are^{2} in [C^{2q+1}]^{N} and x_{k} = (r_{k}, s_{k}) with r a vector in R^{3} and s_{k} (called the spin coordinate) an element of \{0, 1, … 2q\} corresponding to spin values going from −\frac{1}{2}q to +\frac{1}{2}q in integer steps. It is not necessary that χ and Φ each satisfy the Pauli principle; indeed, when q = \frac{1}{2} so that 2q + 1 = 2 and we are dealing with C^{2} it is not possible for χ to be anti-symmetric when N ≥ 3.^{3} Instead, we expect that χ and Φ satisfy certain duality conditions which guarantee that Ψ has the correct permutational symmetry. In the case of anti-symmetric functions there is an extensive literature, e.g., [18, 19], about functions in which the χ_{k} and Φ_{k} are bases for irreducible representations of S_{n} with dual Young tableaux.

2A spin state χ looks formally like a (possibly entangled) N-qubit state. However, unlike qubits which involve an implicit spatial component, we want only vectors in [C^{2q+1}]^{N} itself.

With this background, we now restrict attention to the important special case in which q = \frac{1}{2} yielding two spin states labeled^{4} so that s = +\frac{1}{2} corresponds to |0⟩ and s = −\frac{1}{2} corresponds to |1⟩, and the particles are electrons so that Ψ must be anti-symmetric.

To emphasize the distinction between a pure spin state as an element of C^{2} and a spin associated with a particular qubit or spatial wave function, we will replace |0⟩ and |1⟩ by ↑ and ↓ respectively. The notation |01⟩ then describes a two-qubit state in which the particle in the first qubit has spin “up” (↑) and that in the second has spin “down” (↓). What does it mean for a particle to “be” in a qubit? A reasonable answer is that each qubit is identified by the spatial component of its wave function f_{A}(r) where A, B, C … label the qubits and wave functions for different qubits are orthogonal. Thus, if the qubits did not correspond to identical particles we would have |01⟩ = f_{A}(r_{1})↑ f_{B}(r_{2})↓. In the more realistic situation of identical particles

|01⟩ = \frac{1}{\sqrt{2}}(f_{A}(r_{1})↑ f_{B}(r_{2})↓ ± f_{B}(r_{1})↓ f_{A}(r_{2})↑ ). (2.3)

with the plus sign (+) for bosons and the minus sign (−) for fermions. We will henceforth consider the special case of electrons, which are fermions, in which case the antisymmetric function given by (2.3) is called a Slater determinant. Note that a function of the form (2.3) has the important property that the electron whose spatial function is f_{A} always has spin “up” regardless of whether its coordinates are labeled by 1 or 2. Although (2.3) is not a simple product, but a special type of superposition which is the anti-symmetrization of a product, it behaves in some ways like a product state. It should be contrasted with the a true entangled Bell state such as

(2.4)  \frac{1}{\sqrt{2}}[|01⟩ − |10⟩] = \frac{1}{2}(f_{A}(r_{1})↑ f_{B}(r_{2})↓ −f_{B}(r_{1})↓ f_{A}(r_{2})↑
− f_{A}(r_{1})↓ f_{B}(r_{2})↑ +f_{B}(r_{1})↑ f_{A}(r_{2})↓ )

which is a superposition of two Slater determinants or four products.

It may be useful to observe that (2.4) has the form of a wave function associated with an entangled state shared by “Alice” and “Bob” when f_{A} describes a particle localized near Alice and f_{B} a particle localized near Bob, and discuss its interpretation in that situation. When Alice uses a detector in her lab to measure the spin, she also implicitly makes a measurement of the spatial function, i.e., a measurement which projects onto spatial functions localized in her lab. She may get electron #1 with spin “up” with probability \frac{1}{4} or electron #2 with spin “up” with probability \frac{1}{4}. However, there is no physical way to distinguish these two possibilities. The net result is a measurement of spin “up” in Alice’s lab with total probability \frac{1}{2}. The other two states in the superposition would correspond to measuring some electron in her lab with spin “down”, also with net probability \frac{1}{2}. Once Alice has made a measurement, a corresponding measurement by Bob always yields the opposite spin.

3This is because an antisymmetric N-particle wave function requires at least N linearly independent one-particle functions.

4These labels are the reverse of the usual physicists’s convention; in essence, the convention in quantum computation is to label the eigenvectors of σ_{z} so that the eigenvalue = e^{i label}.

Returning to (2.3), we note that it can be rewritten in the form (2.5) as

|01⟩ = \frac{1}{\sqrt{2}}[χ^{+}(s_{1}, s_{2})ϕ^{−}(r_{1}, r_{2}) + χ^{−}(s_{1}, s_{2})ϕ^{+}(r_{1}, r_{2})] (2.5)

where χ^{±} = \frac{1}{\sqrt{2}} [↑↓ ± ↓↑] denote the indicated Bell-like spin states and

ϕ^{±} = \frac{1}{\sqrt{2}} [f_{A}(r_{1})f_{B}(r_{2}) ± f_{B}(r_{1})f_{A}(r_{2})] .

We emphasize again that the reduction to a simple expression of the form (2.5), in which each term in the product is either an antisymmetric spin function times a symmetric spatial functions or vice-versa, is possible only^{3} when N = 2. For more than two electrons, more complex expressions, of the form (2.2) are needed.

2.2. The origin of Pauli exchange errors. We now describe the origin of Pauli exchange errors by analyzing the two-qubit case in detail, under the additional simplifying assumption that the Hamiltonian is spin-free. This is certainly not realistic; quantum computers based upon spin will involve magnetic fields and hence, not be spin-free. However, the assumption of a spin-free Hamiltonian H, merely implies that the time development of (2.3) is determined by e^{−iHt}ϕ^{±}, and this suffices to illustrate the principles involved. With a spin-dependent Hamiltonian the time development e^{−iHt}χ^{±} would also be non-trivial.

We will also assume that the qubits are formed using charged particles, such as electrons or protons, so that H includes a term corresponding to the \frac{1}{r_{12}} ≡ \frac{1}{|r_{1}−r_{2}|} long-range Coulomb interaction. The Hamiltonian will be symmetric so that the states ϕ^{±} retain their permutational symmetry; however, the interaction term implies that they will not retain the simple form of symmetrized (or antisymmetrized) product states. Hence, after some time the states ϕ^{±} evolve into

(2.6a)  Φ^{−}(r_{1}, r_{2}) = ∑_{m<n} c_{mn} \frac{1}{\sqrt{2}} [f_{m}(r_{1})f_{n}(r_{2}) − f_{n}(r_{1})f_{m}(r_{2})]

(2.6b)  Φ^{+}(r_{1}, r_{2}) = ∑_{m≤n} d_{mn} \frac{1}{\sqrt{2}} [f_{m}(r_{1})f_{n}(r_{2}) + f_{n}(r_{1})f_{m}(r_{2})] .

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} ≠ 0, then one must have some c_{mn} ≠ d_{mn}. Inserting (2.6a) in (2.5) yields

e^{−iHt}|01⟩ = \frac{c_{AB} + d_{AB}}{2} (f_{A}(r_{1})↑ f_{B}(r_{2})↓ −f_{B}(r_{1})↓ f_{A}(r_{2})↑ )

+ \frac{c_{AB} − d_{AB}}{2} (f_{B}(r_{1})↑ f_{A}(r_{2})↓ −f_{A}(r_{1})↓ f_{B}(r_{2})↑ ) + Ψ^{Remain}

= \frac{c_{AB} + d_{AB}}{2} |01⟩ + \frac{c_{AB} − d_{AB}}{2} |10⟩ + Ψ^{Remain} (2.7)

where Ψ^{Remain} is orthogonal to ϕ^{±}.

A measurement of qubit-A corresponds to projecting onto f_{A}. Hence a measurement of qubit-A on the state (2.5) yields spin “up” with probability \frac{1}{4}|c_{AB} + d_{AB}|^{2} and spin “down” with probability \frac{1}{4}|c_{AB} − d_{AB}|^{2}. Note that the full wave function is necessarily an entangled state and that the measurement process leaves the system in state |10⟩ or |01⟩ with probabilities \frac{1}{4}|c_{AB} ±d_{AB}|^{2} respectively, i.e., a subsequent measurement of qubit-B always yields the opposite spin. With probability \frac{1}{4}|c_{AB} − d_{AB}|^{2} the initial state |10⟩ has been converted to |01⟩.

Although the probability of this may be small, it is not zero. Moreover, it would seem that any implementation which provides a mechanism for two-qubit gates would not allow the qubits to be so isolated as to preclude interactions between particles in different qubits^{5}. In general, one would expect qubits to be less isolated from each other than from the external environment so that the interaction between a single pair of qubits would be greater than between a qubit and a particle in the environment. However, the environment consists of a huge number of particles (in theory, the rest of the world) and it may well happen that the number of environmental particles which interact with a given qubit is several orders of magnitude greater than the number of qubits, giving a net qubit-environment interaction which is greater than a typical qubit-qubit interaction. On the other hand, the number of qubit-qubit interactions grows quadratically with the size of the computer. Thus, prototype quantum computers, using only a few qubits, may not undergo exchange errors at the same level as the larger computers needed for real computations.

It is worth emphasizing that when the implementation involves charged particles, whether electrons or nuclei, the interaction always includes a contribution from the \frac{1}{r_{12}} Coulomb potential, which is known to have long-range^{6} effects. This is true even when the interaction used to implement the gates is entirely different, and does not involve electrostatics. Screening may reduce the effective charge, but it will not, in general, remove the basic long-range behavior of the Coulomb interaction.

Precise estimates of exchange errors require more detailed models of the specific experimental implementations. The role of long-range Coulomb effects (for which exchange errors grow quadratically with the size of the computer) suggests that implementations involving neutral particles may be advantageous for minimizing exchange errors. This would include both computers based on polarized photons (rather than charged particles) and more innovative schemes, such as Briegel, et al’s proposal [3] using optical lattices. On the other hand, the ease with which exchange errors can be corrected using appropriate 9-qubit codes, suggests that dealing with exchange interactions need not be a serious obstacle.

3. Correcting Exchange Errors

A Pauli exchange error is a special type of “two-qubit” error which has the same effect as “bit flips” if (and only if) they are different. Exchange of bits j and k is equivalent to acting on a state with the operator

5Although the gates themselves require interactions, we expect these to be short-lived and well-controlled, i.e., in a well-designed quantum computer the gates themselves should not be a significant source of error. However, the process of turning gates on and off could induce errors in other qubits. We do not consider this error mechanism.

6This is because even when f and g have non-overlapping compact support [a, b] and [c, d] respectively, such expectations as ∫ ∫ |f(r_{1})|^{2} \frac{1}{|r_{1}−r_{2}|} |f(r_{2})|^{2} will be non-zero because the integrand is non-zero on [a, b] × [c, d]. Non-overlapping initial states will not prevent the system from evolving in time to one whose states are not simple products or (in the case of fermions) Slater determinants!

E_{jk} = \frac{1}{2}(I_{j} ⊗ I_{k} + Z_{j} ⊗ Z_{k} + X_{j} ⊗ X_{k} + Y_{j} ⊗ Y_{k}) (3.1)

where X_{j}, Y_{j}, Z_{j} denote the action of the Pauli matrices σ_{x}, σ_{y}, σ_{z} respectively on the bit j.

3.1. Example: the 9-bit Shor code. As an example of potential difficulties with existing codes, consider the simple 9-bit code of Shor [28]

(3.2a)  |c_{0}⟩ = |000⟩ + |011⟩ + |101⟩ + |110⟩
(3.2b)  |c_{1}⟩ = |111⟩ + |100⟩ + |010⟩ + |001⟩

where boldface denotes 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} acting on |c_{0}⟩. This yields |000 000 000⟩+|001 011 111⟩+ |110 100 111⟩ + |111 111 000⟩ so that

(3.3a)  E_{34}|c_{0}⟩ = |c_{0}⟩ + Z_{8}|c_{0}⟩ + |001 011 111⟩ + |110 100 111⟩
(3.3b)  E_{34}|c_{1}⟩ = |c_{1}⟩ − Z_{8}|c_{1}⟩ + |110 100 000⟩ + |001 011 000⟩

If |ψ⟩ = a|c_{0}⟩ + b|c_{1}⟩ is a superposition of code words,

E_{34}|ψ⟩ = \frac{1}{2}(|ψ⟩ + Z_{8}|ψ̃⟩) + \frac{1}{\sqrt{2}}|γ⟩

where |ψ̃⟩ = a|c_{0}⟩−b|c_{1}⟩ differs from ψ by a “phase error” on the code words and |γ⟩ is orthogonal to the space of codewords and single bit errors. Thus, this code cannot reliably distinguish between an exchange error E_{34} and a phase error on any of the last 3 bits. This problem occurs because if one tries to write E_{34}|c_{0}⟩ = α|c_{0}⟩+β|d_{0}⟩ with |d_{0}⟩ orthogonal to |c_{0}⟩, then one can not also require that |d_{0}⟩ be orthogonal to |c_{1}⟩.

3.2. Conditions for error correction. Before discussing specific codes for correcting exchange errors, we first review some of the basic principles of error correction. In order to be able to correct a given class of errors, we 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 … n) where n is the number of qubits in the code and X_{k}, Y_{k}, Z_{k} now denote I ⊗ I ⊗ I … ⊗ σ_{p} ⊗ … ⊗ I where σ_{p} denotes one of the three Pauli matrices acting on qubit-k. If we let e_{0} = I denote the identity and {C_{j}} the set of code words, then a sufficient condition for error correction is

⟨e_{p}C_{i}|e_{q}C_{j}⟩ = δ_{ij}δ_{pq} (3.4)

However, (3.4) can be replaced [2, 4, 9] by the weaker condition

⟨e_{p}C_{i}|e_{q}C_{j}⟩ = δ_{ij}d_{pq}. (3.5)

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 (3.4) since some of the exchange errors will then satisfy E_{kℓ}|C_{i}⟩ = |C_{i}⟩. Hence we will need to use (3.5).

The most common code words have the property that |C_{1}⟩ can be obtained from |C_{0}⟩ by exchanging all 0’s and 1’s. For such codes, it is not hard to see that ⟨C_{1}|Z_{k}C_{1}⟩ = −⟨C_{0}|Z_{k}C_{0}⟩ which is consistent with (3.5) if and only if it is identically zero. Hence even when using (3.5) rather than (3.4) it is necessary to require

⟨C_{1}|Z_{k}C_{1}⟩ = −⟨C_{0}|Z_{k}C_{0}⟩ = 0 (3.6)

when the code words have this type of 0 ↔ 1 duality.

If the basic error set has size N (i.e., p = 0, 1 … N − 1), then a two-word code requires codes which lie in a space of dimension at least 2N. 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 ≥ 5. There are n(n − 1)/2 possible single exchange errors compared to 9n(n − 1)/2 two-bit errors of all types. Thus, similar dimension arguments would imply that codes which can correct all one- and two-bit errors must satisfy 2N = 9n(n − 1) + 2(3n + 1) ≤ 2^{n} or n ≥ 10. The shortest code known [4] which can do this has n = 11. We will see that, not surprisingly, correcting both one-bit and Pauli exchange errors, can be done with shorter codes than required to correct all two-bit errors.

However, the dimensional analysis above need not yield the best bounds when exchange errors are involved. Consider the simple code |C_{0}⟩ = |000⟩, |C_{1}⟩ = |111⟩ which is optimal for single bit flips (but can not correct phase errors). In this case N = n + 1 and n = 3 yields equality in 2(n + 1) ≤ 2^{n}. But, since this code is invariant under permutations, the basic error set can be expanded to include all 6 exchange errors E_{jk} for a total of N = 10 without increasing the length of the code words.

3.3. Permutationally invariant codes. 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

(3.7a)  |C_{0}⟩ = |000 000 000⟩ + \frac{1}{\sqrt{28}} ∑ |111 111 000⟩
(3.7b)  |C_{1}⟩ = |111 111 111⟩ + \frac{1}{\sqrt{28}} ∑ |000 000 111⟩

where ∑ 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. This differs from the 9-bit Shor code in that all permutations of |111 111 000⟩ are included, rather than only three. The normalization of the code words is

⟨C_{i}|C_{i}⟩ = 1 + \frac{1}{28}\binom{9}{3} = 4 .

The coefficient 1/\sqrt{28} is needed to satisfy (3.6). Simple combinatorics implies

⟨C_{i}|Z_{k}C_{i}⟩ = (−1)^{i} [1 − \frac{1}{3}\binom{9}{3}\frac{1}{28}] = 0.

Moreover,

⟨Z_{k}C_{i}|Z_{ℓ}C_{i}⟩ = 1 + δ_{kℓ}\binom{9}{3}\frac{1}{28} = 1 + 3δ_{kℓ}. (3.8)

The second term in (3.8) is zero when k ≠ ℓ 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 κ 1’s in n qubits, this term would be \frac{(n − 2κ)^{2} − n}{n(n − 1)}\binom{n}{κ}

when k ≠ ℓ.

Since all components of |C_{0}⟩ have 0 or 6 bits equal to 1, any single bit flip acting on |C_{0}⟩, will yield a vector whose components have 1, 5, or 7 bits equal to 1 and is thus orthogonal to |C_{0}⟩, to |C_{1}⟩, to a bit flip acting on |C_{1}⟩ and to a phase error on either |C_{0}⟩ or |C_{1}⟩. Similarly, a single bit flip on |C_{1}⟩ will yield a vector orthogonal to |C_{0}⟩, to |C_{1}⟩, to a bit flip acting on |C_{0}⟩ and to a phase error on |C_{0}⟩ or |C_{1}⟩. This suffices to ensure that (3.4), and hence (3.5), holds if e_{p} is I or some Z_{k} and e_{q} is one of the X_{ℓ} or Y_{ℓ}.

However, single bit flips on a given code word need not be mutually orthogonal. To find ⟨X_{k}C_{i}|X_{ℓ}C_{i}⟩ when k ≠ ℓ, consider

⟨X_{k} (ν_{1}ν_{2} … ν_{9}) | X_{ℓ} (μ_{1}μ_{2} … μ_{9})⟩. (3.9)

where ν_{i}, μ_{i} are in 0, 1. This will be nonzero only when ν_{k} = μ_{ℓ} = 0, ν_{ℓ} = μ_{k} = 1 or ν_{k} = μ_{ℓ} = 1, ν_{ℓ} = μ_{k} = 0 and the other n − 2 bits are equal. From ∑ with κ of n bits equal to 1, there are 2\binom{n−2}{κ−1} such terms. Thus, for the code (3.7), there are 42 such terms which yields an inner product of \frac{42}{28} = \frac{3}{2} when k ≠ ℓ. We similarly find that

⟨Y_{k}C_{i}|X_{ℓ}C_{i}⟩ = −i⟨X_{k}Z_{k}C_{i}|X_{ℓ}C_{i}⟩ = 0 for all k ≠ ℓ

because exactly half of the terms analogous to (3.9) will occur with a positive sign and half with a negative sign, yielding a net inner product of zero. We also find

⟨Y_{k}C_{i}|X_{k}C_{i}⟩ = −i⟨X_{k}Z_{k}C_{i}|X_{k}C_{i}⟩ = −i⟨Z_{k}C_{i}|C_{i}⟩ = 0

so that

⟨Y_{k}C_{i}|X_{ℓ}C_{i}⟩ = 0 for all k, ℓ.

These results imply that (3.5) holds and that the matrix D is block diagonal with the form

D = ( \begin{matrix}D_{0} & 0 & 0 & 0 \\ 0 & D_{X} & 0 & 0 \\ 0 & 0 & D_{Y} & 0 \\ 0 & 0 & 0 & D_{Z} \end{matrix} ) (3.10)

where D_{0} is the 37 × 37 matrix corresponding to the identity and the 36 exchange errors, and D_{X}, D_{Y} , D_{Z} are 9 × 9 matrices corresponding respectively to the X_{k}, Y_{k}, Z_{k} single bit errors. One easily finds that d_{pq}^{0} = 4 for all p, q so that D_{0} is is a multiple of a one-dimensional projection. The 9 × 9 matrices D_{X}, D_{Y} , D_{Z} all have d_{kk} = 4 while for k ≠ ℓ, d_{kℓ} = 3/2 in D_{X} and D_{Y} but d_{kℓ} = 1 in D_{Z}. Orthogonalization of this matrix is straightforward. Since D has rank 28 = 3·9+1, we are using only a 54 < 2^{6} dimensional subspace of our 2^{9} dimension space.

The simplicity of codes which are invariant under permutations makes them attractive. However, there are few such codes. All code words must have the form

∑_{κ=0}^{n} a_{κ} ∑ | \underbrace{1 … 1}_{κ} \underbrace{0 … 0}_{n−κ}⟩. (3.11)

Condition (3.5) places some severe restrictions on the coefficient a_{κ}. For example, in (3.7) only a_{0} and a_{6} are non-zero in |C_{0}⟩ and only a_{3} and a_{9} in |C_{1}⟩. If we try to change this so that a_{0} and a_{3} are non-zero in |C_{0}⟩, i.e.,

(3.12a)  |C_{0}⟩ = a_{0}|000 000 000⟩ + a_{3} ∑ |111 000 000⟩
(3.12b)  |C_{1}⟩ = a_{9}|111 111 111⟩ + a_{6} ∑ |000 111 111⟩

then it is not possible to satisfy (3.6).

The 5-bit error correction code in [2, 13] does not have the permutationally invariant form (3.11) because the code words include components of the form ∑ ±|11000⟩, i.e., not all terms in the sum have the same sign. The non-additive 5-bit error detection code in [24] also requires changes in the ∑ ±|10000⟩ term. Since such sign changes seem needed to satisfy (3.6), one would not expect that 5-bit codes can handle Pauli exchange errors. In fact, Rains [25] has shown that the 5-bit error correction code is essentially unique, which implies that no 5-bit code can correct both all 1-bit errors and exchange errors. In [27] the possibility of 7-bit codes of the form (3.11) was raised. However, Wallach [30] has obtained convincing evidence that no permutationally invariant 7-bit code can correct all one-qubit errors.

3.4. Proposal for a new class of codes. Permutational invariance, which is based on a one-dimensional representation of the symmetric group, is not the only approach to exchange errors. Our analysis of (3.2) suggests a construction which we first describe in over-simplified form. Let |c_{0}⟩, |d_{0}⟩, |c_{1}⟩, |d_{1}⟩ be four mutually orthogonal n-bit vectors such that |c_{0}⟩, |c_{1}⟩ form a code for one-bit errors and |c_{0}⟩, |d_{0}⟩ and |c_{1}⟩, |d_{1}⟩ are each bases of a two-dimensional representation of the symmetric group S_{n}. If |d_{0}⟩ and |d_{1}⟩ are also orthogonal to one-bit errors on the code words, then the code |c_{0}⟩, |c_{1}⟩ can correct Pauli exchange errors as well as one-bit errors. If, in addition, the vectors |d_{0}⟩, |d_{1}⟩ also form a code isomorphic to |c_{0}⟩, |c_{1}⟩ in the sense that the matrix D in (3.5) is identical for both codes, then the code should also be able to correct products of one-bit and Pauli exchange errors.

However, applying this scheme to an n-bit code requires a non-trivial irreducible representation of S_{n} of which the smallest has dimension n − 1. Thus we will seek a set of 2(n − 1) mutually orthogonal vectors denoted |C_{0}^{m}⟩, |C_{1}^{m}⟩ (m = 1 … n − 1) such that |C_{0}^{1}⟩, |C_{1}^{1}⟩ form a code for one bit errors and |C_{0}^{m}⟩ (m = 1 … n − 1) and |C_{1}^{m}⟩ (m = 1 … n − 1) each form basis of the same irreducible representation of S_{n}. Such code will be able to correct all errors which permute qubits; not just single exchanges. If, in addition, (3.5) is extended to

⟨e_{p}C_{i}^{m}|e_{q}C_{j}^{m′}⟩ = δ_{ij}δ_{mm′}d_{pq} (3.13)

with the matrix D = {D_{pq}} independent of both i and m, then this code will also be able to correct products of one bit errors and permutation errors.

In the construction proposed above, correction of exchange and one-bit errors would require a space of dimension 2(n − 1)(3n + 1) ≤ 2^{n} or n ≥ 9. If codes satisfying (3.13) exist, they could correct all permutation errors as well as products of permutations and one-bit errors (which includes a very special subclass of 3-bit errors and even a few higher ones). Thus exploiting permutational symmetry may yield powerful new codes.

In some sense, the strategy proposed here is the opposite of that of Section 3.3 (despite the fact that both are based on representations of S_{n}). In Section 3.3 we sought code words with the maximum symmetry of being invariant under all permutatations. Now, we seek instead, a pair of dual code words |C_{0}^{1}⟩, |C_{1}^{1}⟩ with “minimal” symmetry in the sense that a set of generators of S_{n} acting on each of these code words yields an orthogonal basis for a non-trivial irreducible representation of S_{n}. If the code words |C_{0}^{m}⟩, |C_{1}^{m}⟩ n = 2 … n − 1 can be obtained in this way, then each pair should also be a single-bit error correction code, as desired.

3.5. Non-additive codes. Most existing codes used for quantum error correction are obtained by a process [4, 5, 7] through which the codes can be described in terms of a subgroup, called the stabilizer, of the error group. Such codes are called “stabilizer codes” or “additive codes”. In [24] an example of a non-additive 5-bit code was given, establishing the existence of non-additive codes. However, this was only an error detection code and, hence, less powerful than the 5-bit error correction code [2, 13] obtained using the stabilizer formalism. Subsequently, V. P. Roychowdhury and F. Vatan [26] showed that many non-additive codes exist; however, it was not clear how useful such codes might be.

H. Pollatsek [21] has pointed out that the 9-qubit code (3.7) is a non-additive code. This establishes that non-additive codes may well have an important role to play in quantum error correction, particularly in situations in which exchange errors and permutational symmetry are important. The non-additivity is immediate if one accepts that for additive codes all non-zero blocks of D consist entirely of d_{pq} = 1. In (3.10), this is true only for D_{0} (after suitable normalization); but not for D_{X}, D_{Y} , D_{Z}.

Nevertheless, it may be instructive to present an argument is based on the observation that the set of vectors which occur in ∑ in (3.7b) spans the vector space of binary 9-tuples Z_{2}^{9}. More generally let Γ_{κ,n} denote the set of all vectors a = (a_{1}, a_{2}, … a_{n}) in Z_{2}^{n} with precisely κ of the a_{j} taking the value 1 and n − κ the value 0 as in (3.11). Then span {Γ_{κ,n}} = Z_{2}^{n} if κ is odd and κ ≠ 0, n. (If κ ≠ 0, n is even, {Γ_{κ,n}} spans the even subspace of Z_{2}^{n}.) By definition, an additive (or stabilizer) code forms an eigenspace for an abelian subgroup S of the error group E = {i^{ℓ}X(a)Z(b) : a, b ∈ Z_{2}^{9}}. When the stabilizer S consists of only the scalar multiples of the identity I, then the corresponding eigenspace is all of C^{2^{9}}. Consequently, to show that (3.7) is not a stabilizer code, it suffices to show that no vector of the subspace spanned by the codewords |C_{0}⟩ and |C_{1}⟩ can be an eigenvector for an element of E other than I.

It suffices to consider the image of |C_{1}⟩ under X(a)Z(b), i.e.,

X(a)Z(b)|C_{1}⟩ = (−1)^{b·e}|a + e⟩ + \frac{1}{\sqrt{28}} ∑_{v∈Γ_{3,9}}(−1)^{b·v}| v + a ⟩

where e = (111 111 111). If X(a)Z(b)|C_{1}⟩ = λ|C_{1}⟩, we must have, in particular, X(a)Z(b)|e⟩ = λ|e⟩ which implies a = (000 000 000) or, equivalently, X(a) = I. Then λ = (−1)^{b·e} and the eigenvalue equation reduces to

Z(b)|C_{1}⟩ = λ (|e⟩ + +\frac{1}{\sqrt{28}} ∑_{v∈Γ_{3,9}}(−1)^{b·(v+e)}| v ⟩)

which implies b·(v+e) = 0 for every v ∈ Γ_{3,9}. But since (as noted above) Γ_{3,9} spans Z_{2}^{9} this implies that b is orthogonal to all of Z_{2}^{9}, which implies b = (000 000 000) so that Z(b) = I as well. Thus, since any element of E can be written as a multiple of X(a)Z(b), the stabilizer S contains only multiples of the identity.

4. Conclusion

Although codes which can correct Pauli exchange errors will be larger than the minimal 5-qubit codes obtained 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 optical lattices) it may be natural and advantageous to use 9-qubit codes which can be implemented in 3 × 3 blocks. (See, e.g., [3].) However, codes larger than 9-bits may be impractical for a variety of reasons. Hence it is encouraging that both the code in section 3.3 and the construction proposed in section 3.4 do not require n > 9.

It may be worth investigating whether or not the codes proposed here can be used advantageously in combination with other schemes, particularly those [10] based on hierarchical nesting. Since the code in sections 3.3 and 3.4 can already handle some types of multiple errors, concatenation of one of these 9-bit codes with itself will contain some redundancy and concatenation with a 5-bit code may be worth exploring. Indeed, when exchange correlations are the prime mechanism for multi-bit errors, the need for repeated concatenation may be significantly reduced.

Construction of codes of the type proposed in Section 3.4 remains a significant challenge. However, development of such new methods of may be precisely what is needed to obtain codes powerful enough to correct multi-qubit errors efficiently, without the large size drawback of codes based on repeated concatenation.

Acknowledgment It is a pleasure to thank Professor Eric Carlen for a useful comment which started my interest in exchange interactions, Dr. Daniel Gottesman for helpful information on existing codes and error correction procedures, Professor Chris King for several helpful discussions and comments on earlier drafts, Professor Harriet Pollatsek for additional comments, discussions and permission to include her observations about the non-additivity of the 9-bit code presented here, Professor Nolan Wallach for communications about 7-bit codes, and the five anonymous referees of Physical Review Letters for their extensive commentary on [27].

Note added in proof: Recent work with H. Pollatsek suggests that condition (3.13) is too strong and the simultaneous orthogonality conditions cannot be satisfied. Other methods for using codes which involve (n − 1)-dimensional representations of S_{n} are under investigation.

References

[1] D. Aharanov, M. Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate” lanl preprints quant-ph/9611025 and quant-ph/9906129.

[2] C.H. Bennett, D.P. DiVincenzo, J.A. Smolin and W.K. Wooters, “Mixed State Entanglement and Quantum Error Correction” Phys. Rev. A 54, 3824–3851 (1996) [lanl preprint quantph/9604024].

[3] H.J. Briegel, T. Calarco, D. Jaksch, J.I. Cirac, and P. Zoller “Quantum computing with neutral atoms” lanl preprint quant-ph/9904010.

[4] R. Calderbank, E.M. Rains, P.W. Shor and N.J.A. Sloane, “Quantum Error Correction and Orthogonal Geometry” Phys. Rev. Lett. 78, 405–408 (1997) [lanl preprint quant-ph/9605005]; and “Quantum Error Correction via Codes over GF(4)” IEEE Trans. Info. Theory 44, 1369– 1387 (1998) [lanl preprint quant-ph/9608006].

[5] D. Gottesman “Stabilizer Codes and Quantum Error Correction” PhD thesis, Caltech (1997). [lanl preprint quant-ph/9705052].

[6] D. Gottesman “A Theory of Fault-Tolerant Quantum Computation” Phys.Rev. A 57, 127– (1998) [lanl preprint quant-ph/9702029].

[7] D. Gottesman, “An Introduction to Quantum Error Correction,” in “Quantum Computation: A Grand Mathematical Challenge for the Twenty-First Century and the Millennium,” edited by Samuel J. Lomonaco, Jr, Proceedings of the Symposia of Applied Mathematics, Volume 58, American Mathematical Society, Providence, RI, (2002).

[8] A. Y. Kitaev “Fault-tolerant Quantum Computation by Anyons” lanl preprint quantph/9707021.

[9] E. Knill and R Laflamme, “A Theory of Quantum Error-Correcting Codes” Phys. Rev. A 55, 900-911 (1997).

[10] E. Knill and R Laflamme, “Concatenated Quantum Codes” lanl preprint quant-ph/9608012.

[11] E. Knill, R Laflamme, and L. Viola “Theory of Quantum Error Correction for General Noise” Phys. Rev. Lett. 84, 25254–28 (2000) [lanl preprint quant-ph/9908066].

[12] E. Knill, R Laflamme, W. H. Zurek “Resilient Quantum Computation: Error Models and Thresholds” Proc. Roy. Soc. A 454, 365–384 (1998). [lanl preprint quant-ph/9702058]

[13] R. Laflamme, C. Miquel, J.P. Paz, W.H. Zurek, “Perfect Quantum Error Correction Code” Phys. Rev. Lett. 77, 198–201 (1996).

[14] D.A. Lidar, I.L. Chuang, and K.B. Whaley “Decoherence Free Subspaces for Quantum Computation” Phys. Rev. Lett. 81, 2594–97 (1998) [lanl preprint quant-ph/9807004].

[15] D.A. Lidar, D. Bacon, and K.B. Whaley “Concatenating Decoherence Free Subspaces with Quantum Error Correcting Codes” Phys. Rev. Lett. 82, 4556–59 (1999) [lanl preprint quantph/9809081].

[16] D.A. Lidar, J. Kempe, D. Bacon, and K.B. Whaley “Protecting Quantum Information Encoded in Decoherence Free States Against Exchange Errors” Phys. Rev. A 61, 052307 (2000) [lanl preprint quant-ph/0004064].

[17] D. Bacon, J. Kempe, D.A. Lidar, and K.B. Whaley, “Universal Fault-Tolerant Computation on Decoherence-Free Subspaces” Phys. Rev. Lett. 85, 1758-61 (2000) [lanl preprint quantph/9909058]; and J. Kempe, D. Bacon, D.A. Lidar, and K.B. Whaley, “ Theory of Decoherence-Free Fault-Tolerant Universal Quantum Computation” lanl preprint quant-ph/0004064.

[18] M. Hamermesh, Group Theory (Addison-Wesley Publishing, 1962).

[19] L. Landau and L. Lifshitz, Quantum Mechanics (Second edition of English translation, Pergamon Press, 1965).

[20] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2000).

[21] H. Pollatsek, private communication

[22] J. Preskill, “Reliable Quantum Computers” Proc. Roy. Soc. A 454, 385–410 (1998) [lanl preprint quant-ph/9705031], and “Fault-Tolerant Quantum Computation ” lanl preprint quant-ph/9712048

[23] J. Preskill, “Battling Decoherence: The Fault Tolerant Quantum Computer” Physics Today (6)52, 24–30 (June, 1999).

[24] E.M. Rains, R. H. Hardin, P.W. Shor and N.J.A. Sloane, “A nonadditive quantum code” Phys. Rev. Lett. 79, 953–954 (1997).

[25] E.M. Rains, “Quantum Codes of Minimum Distance Two” lanl preprint quant-ph/9704043 [26] V. P. Roychowdhury and F. Vatan, “On the Structure of Additive Quantum Codes and the

Existence of Nonadditive Codes” lanl preprint quant-ph/9710031

[27] M.B. Ruskai, “Pauli Exchange Errors in Quantum Computation” Phys. Rev. Lett. 85, 194– 197 (2000); [lanl preprint quant-ph/9906114]

[28] P. Shor, “Scheme for Reducing Decoherence in Quantum Computer Memory” Phys. Rev. A 52, 2493-2496 (1995).

[29] A.M. Steane, “Efficient Fault-tolerant Quantum Computing” Nature 399, 124–126 (May 1999).

[30] N. Wallach, private communication.

(Mary Beth Ruskai) Department of Mathematics, University of Massachusetts Lowell, Lowell, MA 01854 USA

E-mail address, Mary Beth Ruskai: bruskai@cs.uml.edu