Quantum Computation and Quantum Information: Quantum information theory

Chiara Macchiavello, G. Massimo Palma, Anton Zeilinger

Andrew M. Steane

The subject of quantum computing brings together ideas from classical information theory, computer science, and quantum physics. This review aims to summarize not just quantum computing, but the whole subject of quantum information theory. Information can be identified as the most general thing which must propagate from a cause to an effect. It therefore has a fundamentally important role in the science of physics. However, the mathematical treatment of information, especially information processing, is quite recent, dating from the mid-20th century. This has meant that the full significance of information as a basic concept in physics is only now being discovered. This is especially true in quantum mechanics. The theory of quantum information and computing puts this significance on a firm footing, and has led to some profound and exciting new insights into the natural world. Among these are the use of quantum states to permit the secure transmission of classical information (quantum cryptography), the use of quantum entanglement to permit reliable transmission of quantum states (teleportation), the possibility of preserving quantum coherence in the presence of irreversible noise processes (quantum error correction), and the use of controlled quantum evolution for efficient computation (quantum computation). The common theme of all these insights is the use of quantum entanglement as a computational resource. It turns out that information theory and quantum mechanics fit together very well. In order to explain their relationship, this review begins with an introduction to classical information theory and computer science, including Shannon's theorem, error correcting codes, Turing machines and computational complexity. The principles of quantum mechanics are then outlined, and the Einstein, Podolsky and Rosen (EPR) experiment described. The EPR-Bell correlations, and quantum entanglement in general, form the essential new ingredient which distinguishes quantum from classical information theory and, arguably, quantum from classical physics. Basic quantum information ideas are next outlined, including qubits and data compression, quantum gates, the `no cloning' property and teleportation. Quantum cryptography is briefly sketched. The universal quantum computer (QC) is described, based on the Church-Turing principle and a network model of computation. Algorithms for such a computer are discussed, especially those for finding the period of a function, and searching a random list. Such algorithms prove that a QC of sufficiently precise construction is not only fundamentally different from any computer which can only manipulate classical information, but can compute a small class of functions with greater efficiency. This implies that some important computational tasks are impossible for any device apart from a QC. To build a universal QC is well beyond the abilities of current technology. However, the principles of quantum information physics can be tested on smaller devices. The current experimental situation is reviewed, with emphasis on the linear ion trap, high- Q optical cavities, and nuclear magnetic resonance methods. These allow coherent control in a Hilbert space of eight dimensions (three qubits) and should be extendable up to a thousand or more dimensions (10 qubits). Among other things, these systems will allow the feasibility of quantum computing to be assessed. In fact such experiments are so difficult that it seemed likely until recently that a practically useful QC (requiring, say, 1000 qubits) was actually ruled out by considerations of experimental imprecision and the unavoidable coupling between any system and its environment. However, a further fundamental part of quantum information physics provides a solution to this impasse. This is quantum error correction (QEC). An introduction to QEC is provided. The evolution of the QC is restricted to a carefully chosen subspace of its Hilbert space. Errors are almost certain to cause a departure from this subspace. QEC provides a means to detect and undo such departures without upsetting the quantum computation. This achieves the apparently impossible, since the computation preserves quantum coherence even though during its course all the qubits in the computer will have relaxed spontaneously many times. The review concludes with an outline of the main features of quantum information physics and avenues for future research.

F. De Martini, Christopher R. Monroe

This Fermi Summer School of Physics on Experimental Quantum Information and Computing represents a primer in an expanding area in physics. In this part, the interest in quantum information (QI) science is due to the discovery that a computer operating on quantum mechanical principles can solve certain important computational problems exponentially faster than any conceivable classical computer. But this interest is also due to the interdisciplinary nature of the field: the rapid growth is attributable, in part, to the stimulating confluence of researchers and ideas from physics, chemistry, mathematics, information theory, and computer science. The lectures cover Quantum Information (QI) processing, spanning quantum optics and laser physics, atomic and molecular physics, physical chemistry, and condensed-matter physics.

David Peter Divincenzo

Mary Beth Ruskai

In nanotechnology, one is dealing with physical systems at a scale so small that quantum effects are important. As the size of computer chips decreases, one eventually reaches the point where quantum effects, wanted or not, occur. If these quantum effects can be controlled, they can be exploited to build computers that can do some tasks more effectively than classical ones. Moreover, quantum particles can be be used advantageously for other purposes in information technology, most notably for communication and cryptography. In fact, experiments demonstrating the feasibility of the process known as quantum key distribution (QKD) are quite impressive. QKD, which is described in Sec. 9.5.1, is likely to be practical long before a full-fledged quantum computer (QC) is built. The area of quantum information theory (QIT) encompasses quantum computation, quantum communication, and quantum cryptography. A device for implementing any of these is called a quantum information processor. We begin by considering methods of encoding information in such devices.