and Error Correction
A quantum computer is a computing device that invokes intrinsically quantum-mechanical phenomena, such as interference and entanglement. These phenomena endow a quantum computer with certain capabilities that cannot be matched, even in principle, by any classical computer. Unfortunately though, these quantum phenomena are exceptionally vulnerable to the effects of noise and of imperfections in the machine. A scheme must be found to overcome this difficulty if quantum computers are ever to become practical devices .
For example, the quantum factoring algorithm suggested by Shor works by coherently summing an exponentially large number of amplitudes that interfere constructively. But when the computer interacts with its environment, the quantum state of the computer becomes entangled with the state of the environment; hence the quantum state of the computer decays to an incoherent mixed state, a phenomenon known as decoherence. Decoherence destroys the constructive interference, and so drastically compromises the performance of the machine.
In classical computation or communication, the effects of noise can de systematically dealt with by means of error-correcting codes, in which information is stored with sufficient redundancy that it can be reliably recovered even after the signal has been substantially degraded. Shannon's Main Theorem of classical information theory shows that a noisy classical channel has a finite channel capacity, such that information can be sent over the channel with an arbitrarily small probability of error at a rate arbitrarily close to (but below) the channel capacity.
Generalizing the concept of an error-correcting code to quantum information (information encoded in the state of a quantum system) is problematic for several reasons. First, quantum information cannot be faithfully copied (the ``no-cloning theorem''), so it is subtle to encode the information redundantly and to process the information so encoded. Furthermore, to detect that an error has occurred, we must make a measurement and extract some data about the state of the quantum system. But this measurement may disturb the system and modify the encoded information.
Nevertheless, there has been dramatic recent progress in error-correcting quantum coding . The crucial idea is that information can be encoded in correlations involving many "qubits" (or spins), in such a way that none of the information can be accessed by measuring just a few qubits at a time. Information encoded in this way is not destroyed if a few of the qubits interact with the environment. Yet the error caused by the interaction can be detected and corrected by making suitable measurements of the system together with an auxiliary device.
There are many open questions. For example, it is not clear how a general mathematical model of a noisy quantum communication channel should be formulated, nor how a quantum channel capacity can be defined that quantifies the highest attainable rate at which information can be transmitted. Aside from this important question of principle, work needs to be done to formulate efficient new schemes for error-correcting quantum coding that might prove to be of practical value. Even when a reliable means of storing quantum information is in hand, new ideas will be needed to perform error-free quantum computation. We intend to perform (classical) computer simulations of a quantum computer operating in a noisy environment to test the efficacy of various proposed machine architectures and error correction schemes. In the longer term, experimental realizations will be sought (e.g., in cavity QED) of quantum networks that incorporate error correction protocols.
b. Quantum coding -
While classical information can be represented as a string of bits, quantum information is represented as a density matrix acting on a Hilbert space (or, in the case of a pure state, a ray in a Hilbert space). A quantum code is essentially a way of embedding one finite-dimensional Hilbert space inside another larger (higher-dimensional) Hilbert space. Suppose, for example, that we denote by Hk the 2k-dimensional Hilbert space of k spin-1/2 objects. Then a quantum code is a unitary mapping that takes Hk to a subspace of Hn , where n>k. We say that the code stores k qubits of quantum information in a system of n qubits; the image of the mapping is spanned by 2k basis states, which are the "valid codewords." R=k/n is called the rate of the code. Quantum coding theory addresses the issue of whether encoded quantum information can be reliably transmitted through a noisy channel. One possible way to define a "quantum channel" is as a linear operation (the "dollar matrix" $) acting on density matrices,
that preserves the conditions that probabilities are nonnegative and sum to one. Usually, we will find it convenient to consider a model for the channel that is not quite so general - for a system of n qubits, we may imagine that the channel leaves most of the qubits undisturbed, but that at most t of the qubits become entangled with the environment (and thus "decohere"). The rationale for this simplified model is that we expect the Hamiltonian of the world to be local in space; for example, there are no terms in the Hamiltonian that flip over all n of the spins. Therefore, as n gets large, we can expect the number of qubits that interact with the environment to be close to t =np typically, where p is the error rate of the channel.
Now we can explain what is meant by an error-correcting quantum code. We say that a code can correct t errors if we can unambiguously recover the initial quantum state even after t qubits have decohered. That is, suppose that an initial pure state |init> is chosen that is an arbitrary superposition of valid codewords, which then propagates through the channel and decoheres. We may describe the decoherence as a unitary transformation Udec that acts on Hn Henv , where Henv is the Hilbert space of states of the environment. By assumption, Udec acts nontrivially on at most t of the n qubits of Hn , where these t qubits are chosen randomly. The action Udecwill entangle the state of the n qubits with the state of the environment.
To recover the initial state, we may make use of an auxiliary system (the "ancilla") with a Hilbert space Haux that is orthogonal to Hn , where the state of the ancilla has been preset to a standard value. After decoherence, a unitary transformation (the recovery matrix) acts on Hn Haux . This recovery matrix can be chosen so that it maps the decohered state back to the tensor product of |init> with a state of the environment and ancilla. In effect, the recovery operation disentangles the coded state from the environment, and transfers the entanglement to the ancilla. The ancilla can then be reset, and if desired, reused.
A fundamental question is, given k qubits to be encoded, what is the minimal value of n for which a code can be constructed that can correct t errors? Or, given an error rate p of the channel, what is the minimal rate R=k/n of a code that allows quantum information to be transmitted with arbitrarily good reliability (as n gets large)? The answers are not known.
c. Nondegenerate and degenerate coding:
There is one class of error-correcting quantum codes that is particularly easy to characterize; we will call the codes in this class "nondegenerate." To understand the terminology, note first of all that when a spin interacts with the environment, there are 3 linearly independent nontrivial ways that the spin can be affected---the spin may flip over, the phase of the spin may change sign, or both a spin flip and a phase change may occur. Therefore, for a system of n qubits, the total number of possible independent ways for errors to afflict at most t qubits is
(where we have included the "trivial error" -- the case of no error at all, and C( n , j ) indicates "n choose j"). In a nondegenerate code that corrects t errors, the 2k codewords are chosen so that any two possible errors acting on any two codewords yield mutually orthogonal states in Hn . It is now easy to explain how the error correction procedure works. For each possible error, there is a dimension-2k subspace of Hn that is obtained when the error acts on the space spanned by the valid codewords. In the case of a nondegenerate code, there are E(n, t) error subspaces, all mutually orthogonal. By detecting what subspace a message lies in after propagating through the channel, we can determine what error occurred and take the appropriate action to reverse the error. The detection can be carried out without any information being acquired about where in the subspace the message lies, so the error is corrected without finding out anything about the content of the message.
From the requirement that Hn must contain E(n,t) mutually orthogonal subspaces each of dimension 2k , it is clear that for a nondegenerate error-correcting code to exist, the inequality
must be satisfied. For asymptotically large n, this inequality can be expressed as a bound on the rate of the code:
where H(p)= - p log2p - ( 1 - p ) log2( 1 - p ) is the entropy function and p=t/n is the error rate. This relation can be regarded as a quantum version of the Hamming bound that applies to classical error-correcting codes -- the "quantum correction" to the Hamming bound is the extra term -p log23 on the RHS that arises because there are three distinct possible errors for each qubit.
A good quantum error-correcting code need not be nondegenerate. For example, it may be that two distinct errors both map the valid codewords to the same subspace; then we say that the code is "degenerate." For a degenerate code, the error diagnostic will not tell us the precise nature of the error that occurred, but if will still provide enough information to tell us how to recover the initial state. A degenerate code can in principle have a rate that exceeds the quantum Hamming bound. For example, in the case k=1, t=1 (one qubit encoded so as to correct one error), the quantum Hamming bound says that n must be at least 5. We have, in fact, constructed a nondegenerate n=5 code that saturates this bound. As best we can determine, it is not possible to do better, in this case, with a degenerate code. However, for larger values of k and t, we believe that degenerate codes might outperform nondegenerate codes, and are now investigating this issue.
We intend to continue with the study of the systematics of error-correcting quantum codes. In particular, we will further explore the theory of degenerate codes, and will improve the estimates of the optimal rates that can be attained.
d. Encoder design -
One central problem in quantum coding theory is to optimize the rate of an error-correcting code. But a high rate is only one consideration that makes a code efficient. We also want to make the procedure for encoding and decoding the message as algorithmically simple as possible. Therefore, an important part of the formulation of a code is the design of the quantum circuit that performs the encoding. In fact, if the encoding procedure is very complex, then errors are likely to occur during encoding and decoding, which will compromise the effectiveness of error-correcting communication.
We intend to study the tradeoff between the rate of the code and the complexity of the encoder. In particular, encoding will be more efficient if it can be made highly parallelizable. To build a parallelizable encoder, we require additional qubits, and hence a lower rate of data storage. But the improved speed of decoding and encoding (and the reduction in the probability of encoding/decoding errors) may more than offset the loss of rate.
Aside from the issue of the efficiency of the encoder there is also the issue of the efficiency of the error correction protocol. Actually, these issues are more closely related than might have been suspected. In fact, we have shown that it is always possible to design the encoder so that it can be used (running backwards) to perform the error correction, and that the "ancilla" can be dispensed with. The encoder is a unitary transformation U that acts on n qubits. If the input to the encoder is a number i ranging from 0 to 2k-1 in the first k qubits, and 0's in the remaining n-k qubits, then the output is the ith codeword. Suppose that an arbitrary state in Hk is chosen and encoded, and that up to t qubits of the coded message decohere. Then, for a suitably designed encoder, we apply U -1 to the message that has decohered. The recovered initial state will then occupy the first k qubits, and the error syndrome can be read by measuring the remaining n-k qubits. Thus, we can use the same piece of hardware both to perform the encoding and to recover from decoherence -- the machine can be used repeatedly if we reset the n-k "error qubits" at the beginning of each cycle. (However, this might not be the simplest possible error-correction procedure for a given code.)
e. Codes for computation -
Error-correcting quantum codes protect quantum information from being degraded by decoherence, and so allow us to store quantum data reliably. Of course, in the operation of a quantum computer, we must do more than merely store quantum data -- we must also process the data. A code with a high rate allows us to design an error-correcting quantum computer that saves on storage space, but if the code is algorithmically complex we will pay a heavy price: processing the data will be difficult and slow. Hence there is another tradeoff to study -- that between the efficiency of the code and the efficiency of the quantum gates that process the encoded data. For the codes that we formulate, we will also design quantum gates that process encoded information, with the goal of optimizing the performance of a quantum computer in a noisy environment. We will perform computer simulations that test the efficacy of various candidate error-correction schemes.
f. Error prevention -- the watchdog scheme -
We have so far focussed on schemes that correct errors that arise due to decoherence. But it is also useful to ask whether any form of intervention can prevent errors from occurring in the first place. There is no practical way to prevent decoherence (other than the obvious one of isolating the computer from the environment as well as possible). But decoherence is not the only source of error in the operation of a quantum computer. Another problem is that quantum gates cannot be implemented with perfect precision. Small errors in the gates accumulate throughout the course of a computation and can markedly reduce the likelihood that the computation is completed successfully.
One way to control the accumulation of error is to exploit the quantum "watchdog effect." Suppose that when a quantum gate acts on a state, the amplitude for the output state to be "wrong" is typically of order e << 1. Then a large error will tend to accumulate in a circuit that contains of order 1/e gates. However, the probability that each gate makes an error is only of order e2. Thus, if there is a way to "check" whether the gate has made an error after each gate operates, we can increase the size of the circuit to of order 1/e2 before the likelihood of error becomes appreciable. The trick is to perform the error detection without disturbing the computation. We have designed general purpose watchdog schemes that can be incorporated into a quantum circuit to improve its reliability [d]. We intend to simulate errors in the operation of sample quantum networks and test the effectiveness of the watchdog.
g. Cryptography -
Another quite important application of quantum information theory is to cryptography. Not only is quantum information highly vulnerable to the effects of noise in the environment, for much the same reason it is also very difficult to intercept quantum information without modifying it in a detectable way. That is, an eavesdropper in intercepting the signal becomes entangled with it, and so causes decoherence. Statistical tests can then be performed to verify that decoherence has occurred. Indeed, it was suggested some time ago that quantum information provides a natural solution to the problem of secure key distribution in public key cryptosytems .
However, detection of eavesdropping becomes more problematic if a noisy channel is used to distribute the key --- one must be able to distinguish the "natural" decoherence caused by uncontrollable noise from the "synthetic" decoherence caused by the eavesdropper. Fortunately, error correction techniques can be employed to "purify" the transmitted quantum information, in effect removing the entanglement of the signal both with the environment and with the eavesdropper . We intend to study the application of error-correcting quantum codes to signal purification, and to investigate the complexity of quantum cryptography using noisy channels.
a. Q. A. Turchette, C. J. Hood, W. Lange, H. Mabuchi, and H. J. Kimble, Phys. Rev. Lett. 75, 4710(1995).
b. S. Lloyd, Phys. Rev. Lett. 75, 346(1995).
c. S. Lloyd, "Quantum Analog Computers," submitted to Science (1996).
d. J. Preskill, "Can Quantum Errors Be Corrected?," unpublished notes (November, 1994).
e. A. Despain et al., JASON Report JSR-95-115, Mitre Corporation, McLean, VA.
f. D. Beckman, A. Chari, S. Devabhaktuni, and J. Preskill, Caltech Preprint CALT-68-2021 (1995).
g. H. Mabuchi and P. Zoller, Phys. Rev. Lett.(1996).
h. N. J. Cerf and C. Adami, "Negative Entropy and Information in Quantum Mechanics," Caltech Preprint (1995), quant-phy/9512022.
1. R. P. Feynman, Intl. J. Theoretical Physics 21, 467 (1982); D. Deutsch, Proc. R. Soc. Lond. A400, 97 (1985); P. Benioff, Phys. Rev. Lett. 48, 1581(1982).
2. P. W. Shor, in 35th Annual Symposium on Foundations of Computer Science: Proceedings, ed. S. Goldwasser, IEEE Computer Society Press (1994).
3. C. Monroe, D. M. Meekhof, B. E. King, W. M. Itano, and D. J. Wineland, Phys. Rev. Lett. 75, 4714(1995).
4. T. Pellizzari, S. A. Gardiner, J. I. Cirac, and P. Zoller, "Decoherence, Continuous Observation, and Quantum Computing: A Cavity QED Model," Phys. Rev. Lett. 75, 3788 (1995).
5. J. I. Cirac and P. Zoller, Phys. Rev. Lett. 74, 4091 (1995).
6. A. Barenco, D. Deutsch, A. Ekert, and R. Jozsa, Phys. Rev. Lett. 74, 4083 (1995); T. Sleator and H. Weinfurter, ibid., 4087; J. I. Cirac and P. Zoller, ibid., 4091.
7. C. W. Gardiner, Phys. Rev. Lett 70, 2269 (1993); H. J. Carmichael, ibid., 2273.
8. A. S. Parkins, P. Marte, P. Zoller, O. Carnal, and H. J. Kimble, Phys. Rev. A 51, 1578 (1995).
9. Z. Hu and H. J. Kimble, Optics Lett. 19,1888 (1994).
10. R. Hughes, et. al., "Quantum Computation and Factoring," Presentation from Los Alamos National Laboratory, (1995).
11. R. Landauer, "Is quantum mechanically coherent computation useful?," in Proceedings of the Drexel-4 Symposium on Quantum Nonintegrability -- Quantum-Classical Correspondence, edited by D. H. Feng and B.-L. Hu (International Press, to appear).
12. P. W. Shor, Phys. Rev. A 52, 2493 (1995); A. R. Calderbank and P. W. Shor, "Good quantum error-correcting codes exist," (1995, unpublished), quant-ph/9512032; A. Steane, "Multiple particle interference and quantum error correction," (1995, unpublished), quant-ph/9601029.
13. For an elementary review see C. H. Bennett, G. Brassard, and A. K. Ekert, Sci. Am. Oct. 1992, 50.
14. C. H. Bennett et al., "Purification of noisy entanglement and faithful teleportation via noisy channels," (1995, unpublished); D. Deutsch et al., "Entanglement-based quantum cryptography is unconditionally secure," (1995, unpublished).
15. V. Vedral, A. Barenco, and A. Ekert, "Quantum networks for elementary arithmetic operations," Oxford preprint (1995), quantu-ph/9511018.
16. C. Miquel, J. P. Paz, R. Perazzo, "Factoring in a dissipative quantum computer," Technical report 9601021 from Los Alamos National Laboratory repository, (1996).
17. C. H. Bennett et al., "Purification of noisy entanglement and faithful teleportation via noisy channels," (1995, unpublished).
18. D. Deutsch et al., "Entanglement-based quantum cryptography is unconditionally secure," (1995, unpublished).
19. H.-K. Lo and H. F. Chau, "Quantum cryptography in noisy channels," (1995, unpublished), quant-ph/9511025.