Landmarks—Correcting Quantum Computer Errors
Landmarks articles feature important papers from the archives of the Physical Review journals.
Quantum computers were dreamed up long before any practical demonstration became possible. In the mid 1990s, two researchers working independently showed theoretically how to get around one major difficulty that some thought insurmountable. They devised error-correction methods that would protect the fragile quantum states essential to the inner workings of a quantum computer. The discovery inspired fault-tolerant designs that could make large-scale quantum computers feasible, as well as methods to preserve information transmitted by quantum-mechanical means.
The idea of quantum computing is often credited to Richard Feynman, who gave a talk in 1981 arguing that quantum combinations, or “superpositions,” of two distinct states could form the elements of a computer. Instead of ones and zeros, the quantum bits (“qubits”) could be in states that were partially one and partially zero—a more versatile system [1]. In 1994, Peter Shor of AT&T Bell Labs in Murray Hill, New Jersey, showed that such a device could rapidly find the factors of large numbers, a task that is prohibitively time-consuming using conventional computers [2].
But doubts also arose about the feasibility of quantum computing. A qubit can maintain its identity only as long as it is kept strictly isolated from disturbances that would knock it out of its quantum superposition and force it to become either a one or a zero. Some researchers argued that it would be impossible to preserve qubits long enough to perform a calculation [3].
Shor addressed this concern in 1995 by coming up with a way to test whether a qubit has been disturbed and, if so, correct it. The problem is that any direct test of a qubit amounts to a measurement that destroys its superposed state. Shor explained how to create, from a single qubit, a state of nine qubits that are connected through quantum entanglement and that encode the original superposition. The nine-qubit state is a set of three groups containing three qubits each, all of which are identical at the start. If one qubit out of the nine is disturbed, then the triplet it belongs to will become different from the other two. The two identical triplets, however, retain an accurate record of the original qubit state.
To assess the condition of the triplets without destroying the relevant information, Shor made use of measurements that reveal only one aspect of an entangled state. For example, with qubits based on quantum spins, a certain measurement of an entangled qubit pair will show whether their spins point in the same or opposite directions, without indicating what those directions are.
Shor constructed a sequence of such operations on the three triplets that would indicate whether one of them had changed and that would allow another sequence of operations to reconstruct the original qubit from the unchanged pair.
The next year, Andrew Steane of Oxford University, UK, published an analysis in the same vein, except that his error-correction method needed only seven qubits. Both his and Shor’s methods were, at the time, theoretical proposals. As Steane observed, “the experimental production of such states … is a demanding task which remains to be addressed.”
“Shor’s work was revelatory,” says David DiVincenzo, now at Aachen University in Germany. At the time he was at IBM in Yorktown Heights, New York, working with colleagues on issues arising from the 1993 discovery of quantum teleportation (see Landmarks—Teleportation Is not Science Fiction). In teleportation, two observers at different locations share an entangled state, and a problem analogous to error correction arises in that the connection between the observers will typically be subject to disturbances that can disrupt the entanglement. The IBM group was studying this problem when Shor’s work appeared, and it influenced their research on how to guarantee accurate teleportation through a noisy channel [4].
Theoretical work blossomed rapidly, says DiVincenzo. It quickly emerged that infinitely many error-correction codes exist, classifiable using group theory, and connections with statistical mechanics and phase transitions became apparent. The first demonstration of an error-correction method came in 1998 [5]. But the experimental work is difficult, and progress continues to be “more plodding,” as DiVincenzo puts it. So far, working quantum computers have involved only a handful of qubits that can be protected from disturbance, and quantum error-correction has been demonstrated only for single qubits. For large-scale quantum computing to become practical, however, fault-tolerant methods originating in Shor and Steane’s work will be a necessary design element.
This research is published in Physical Review Letters and Physical Review A.
–David Lindley
David Lindley is a freelance science writer in Alexandria, Virginia.
References
- R. P. Feynman, “Simulating Physics with Computers,” Int. J. Theor. Phys. 21, 467 (1982).
- P. W. Shor, “Algorithms for Quantum Computation,” in SFCS '94 Proceedings of the 35th Annual Symposium on Foundation of Computer Science (IEEE Computer Society Press, Washington, DC, 1994), p. 124[Amazon][WorldCat]; Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM J. Comput. 26, 1484 (1997).
- R. Landauer, “Is Quantum Mechanics Useful?,” Philos. Trans. R. Soc. London A 353, 367 (1995).
- C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin, and W. K. Wootters, “Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels,” Phys. Rev. Lett. 76, 722 (1996).
- D. G. Cory, M. D. Price, W. Maas, E. Knill, R. Laflamme, W. H. Zurek, T. F. Havel, and S. S. Somaroo, “Experimental Quantum Error Correction,” Phys. Rev. Lett. 81, 2152 (1998).
More Information
Landmarks—Teleportation Is not Science Fiction
Correction (13 June 2016): This article was corrected to say that Feynman’s talk was in 1981 (published in ’82) and that Andrew Steane was not mainly a theorist, even though this paper was theoretical.