EDWIN B. FABILLAR
Information carried by a quantum system has notoriously weird properties. Physicists and engineers are now learning how to put that weirdness to work. Quantum computers, which manipulate quantum states rather than classical bits, may someday be able to perform tasks that would be inconceivable with conventional digital technology. A particularly daunting difficulty is that quantum computers are highly susceptible to making errors. The magical power of the quantum computer comes from its ability to process coherent quantum states; but such states are very easily damaged by uncontrolled interactions with the environment—a process called decoherence. In response to the challenge posed by decoherence, the new discipline of quantum error correction has arisen at the interface of physics and computer science. We have learned that quantum states can be cleverly encoded so that the debilitating effects of decoherence, if not too severe, can be resisted.
The power of the quantum computer
A classical computer executes a series of simple operations (often called “gates”), each of which acts on a single bit or pair of bits. By executing many gates in succession, the computer can evaluate any Boolean function of a set of input bits. Also a quantum computer executes a series of elementary quantum gates, each of which is a unitary transformation that acts on a single qubit or pair of qubits. By executing many such gates in succession, the quantum computer can apply a complicated unitary transformation to a particular initial state of a set of qubits. A classical computer can faithfully simulate a quantum computer, so that anything the quantum computer could do, the classical computer could also do. Still, there is a sense in which the quantum computer appears to be a more powerful device: In more physical terms, running a classical simulation of a quantum computer is hard because (as exemplified by John Bell’s famous inequalities) correlations among quantum bits are qualitatively different from correlations among classical bits. The exponential explosion in the size of Hilbert space as we increase the number of qubits arises because the correlations among qubits are too weird to be expressed easily in classical language.
The challenge of error correction
Are there any obstacles that might be fundamental matters of principle, that would prevent us from ever constructing a quantum computer? In fact, there is a problem of principle that is potentially very serious: decoherence. Unavoidable interactions with the environment will cause the quantum information stored in a quantum computer to decay, thus inducing errors in the computation. If quantum computers are ever to be capable of solving hard problems, a means must be found to control decoherence and other potential sources of error.
Quantum error-correcting codes
In 1995, Shor and Andrew Steane discovered that the obstacles were illusory— that quantum error correction really is possible. To appreciate the insights of Shor and Steane, lets first consider how to defend quantum information against a dragon who performs only bit flips . We are to protect the state
(1) [eq] a|0> + b|1> [/eq],
a coherent superposition of the red (|0>) and green (|1>) states of a single qubit, where the complex coefficients a and b are unknown. Were the dragon to attack, the bit flip would transform the state to
(2) [eq] a|1> + b|0>[/eq],
and damage would be inflicted unless a =±b. The beaver’s assignment is to diagnose and reverse bit flips, but without disturbing the delicate superposition state, that is without modifying a and b, the beaver applies the principle of redundant storage by encoding the qubit in a state of three qubits.
The red state is encoded as three red qubits, and the green state as three green qubits; that is,
(3.a) [eq] |0> \rightarrow |0> = |000>[/eq],
(3.b) [eq] |1> \rightarrow |1> = |111>[/eq],
Thus the unknown superposition state becomes
(4) [eq] a|0> + b|1> \rightarrow a|0> + b|1> = a|000> + b|111> [/eq],
This redundant state is not the same as three identical copies of the original unknown state, which would be
(5) [eq](a|0> + b|1>) (a|0> + b|1>) (a|0> + b|1>)[/eq],
Although it is impossible to copy unknown quantum information, nothing prevents us from building a (unitary) machine that will execute the encoding transformation given as equation 4.
Now suppose that the dragon flips one of the three qubits, let’s say the first one, so that the state becomes
(6) [eq] a|100> + b|011>[/eq],
and the beaver is to detect and reverse the damage. His first impulse would be to open the boxes and look to see if one ball was a different color from the others, just as he would to diagnose errors in classical information, but he must resist that temptation. If he were to open door 1 of all three boxes, he would find either I100> (with probability |a|2), or I011 > (with probability IbI2); either way, the coherent quantum information (the values of a and b) would be irrevocably lost. But he is a clever beaver who knows he need not restrict his attention to single-qubit measurements. Instead, he performs collective measurements on two qubits at once. The beaver won that round, but now the dragon tries a more subtle approach. Rather than flipping the first qubit, he rotates it only slightly, so that the three-qubit state becomes
(7) [eq] a|000> + b|111> \rightarrow a|000> + b|111> [/eq]
[eq] + e(a|100> + b|011>) + o (e2)[/eq],
where |e| >> 1. What should the beaver do now? In fact, he can do the same thing as before. If he performs a collective measurement on the first two qubits, then most of the time
(with probability [eq] 1 – |e|^2 [/eq]), the measurement well project the damaged state (equation 7) back to the completely undamaged state (equation 4). Only much more rarely (with probability [eq] |e|^2 [/eq]) will the measurement project onto the state given as equation 6 with a bit-flip error. But then the measurement outcome tells the beaver what action to take to repair the damage, just as in theprevious case.
Collective measurement and fault tolerance
Topological ideas arise naturally in the theory of fault tolerance. The topological properties of an object remain invariant when we smoothly deform the object. Similarly, how a fault-tolerant gate acts on encoded information should remain unchanged when we deform the gate by introducing a small amount of noise. In seeking fault-tolerant implementations of quantum logic, we are led to contemplate physical interactions with a topological character. What comes quickly to mind is the Aharonov-Bohm effect. When an electron is transported around a magnetic flux tube, its wave function acquires a phase that depends only on the winding number of the electron about the solenoid; it is unmodified if the electron’s trajectory is slightly deformed. If we could perform quantum logic by means of topological interactions, then we would be able to give the beaver a rest! We could protect encoded information not by vigilantly checking for errors and reversing them, but rather by weaving fault tolerance into the design of our hardware.
For a quantum computer to compete with a state-of-the-art classical computer, we will need machines with hundreds or thousands of qubits capable of performing millions or billions of operations. The technology clearly has far to go before quantum computers can assume their rightful place as the world’s fastest machines. But now that we know how to protect quantum information from errors, there are no known insurmountable obstacles blocking the path. Quantum computers of the 21st century may well unleash the vast computational power woven into the fundamental laws of physics. Apart from enabling a new technology, the discovery of fault-tolerant methods for quantum error correction and quantum computation may have deep implications for the future of physics. What else might coherent quantum systems be capable of? In what ways will they surprise, baffle, and delight us? Armed with new tools for maintaining and controlling intricate quantum states, physicists of the next century will seek the answers.
1. R. P. Feynman, Int. J. Theor. Phys. 21, 467 (1982).
2. D. Deutsch, Proc. Roy. Soc. London, Ser. A400, 96 (1985).
3. P. Shor, in Proc. of the 35th Annual Symp. on Foundations of
Computer Science, Los Alamitos, Calif., IEEE Press (1994), p.
4. D. Dieks, Phys. Lett. A 92, 271 (1982). W. K Wootters, W. H.
Zurek, Nature 299, 802 (1982).
5. P. Shor, Phys. Rev. A 52, 2493 < 1995).
6. A. M. Steane, Phys. Rev. Lett. 77, 793 (1996).
7. R. Laflamme, C. Miquel, J. P. Paz, W. Zurek, Phys. Rev. Lett.
77, 198 (1996). C. Bennett, D. DiVincenzo, <L Smolin, W.
Wootters, Phys. Rev. A 54, 3824 (1996).
8. A. R. Calderbank, P. W. Shor, Phys. Rev. A 54, 1098 (1996).
A. M. Steane, Proc. Roy. Soc. London, Ser. A452, 2551 (1996).
9. P. Shor, in Proc. of the 37th Annual Symp. on Foundations of
Computer Science, Los Alamitos, Calif, IEEE Press (1996), p.
10. E. Knill, R. Laflamme, preprint, http://xxx.lanl.gov/abs/quantph/
11. E. Knill, R. Laflamme, W. Zurek, Proc. Roy. Soc. London, Ser.
A454, 365 (1998). A. Yu. Kitaev, Russ. Math. Surveys 52,1191
(1997). D. Aharonov, M. Ben-Or, in Proc. of the 29th Annual
ACM Symp. on the Theory of Computing, New York, ACM
(1997), p. 176. J. Preskill, Proc. Roy. Soc. London, Ser. A 454,
12. A. Yu. Kitaev, preprint, http://xxx.lanl.gov/abs/quantph/
9707021. J. Preskill, preprint, http://xxx.lanl.gov/
13. D. G. Cory, M. D. Price, W. Maas, E. Knill, R. Laflamme, W. H.
Zurek, T. F. Havel, S. S. Samaroo, Phys. Rev. Lett. 81, 2152
14. D. Leung, L. Vandersypen, X. Zhou, M. Sherwood, C. Yannoni,
M. Kubinec, I. Chuang, preprint, http://xxx.lanl.gov/
15. C. Monroe, D. M. Meekhof, B. E. King, W. M. Itano, D. J.
Wineland, Phys. Rev. Lett. 75, 4714 (1995). Q. A. Turchette,
C. J. Hood, W. Lange, H. Mabuchi, H. J. Kimble, Phys. Rev.
Lett. 75,4710 (1995).