The work of John Bell in the mid 1960s and experiments carried out to test his famous inequalities in the following decades have led to a detailed re-examination of the concepts of quantum mechanics, and revealed the full importance of the notion of entanglement. This reconsideration helped to generate the new and extremely rich field of research known as quantum information in the 1980s. The guiding idea behind this field of activity is that, by exploiting the specific rules of quantum physics, one can conceive of new ways of calculating and communicating, in which the rules of play are no longer the well-known classical rules. One can thus develop new methods of cryptography in which the message is protected by the basic principles of quantum mechanics, and new computation methods that can be exponentially more efficient than classical algorithms. Quantum information is not therefore a mere sideline for physics, but concerns information theory, algorithmics and the mathematics of complexity theory. This research has already led to proposals for new algorithms and new computation architectures based on quantum logic gates with no classical equivalent. Still on the fundamental level, the meeting of information theory and quantum mechanics which lies at the heart of quantum information has led to a very stimulating regeneration of the theoretical tools used on both sides.
The work of John Bell in the mid 1960s and experiments carried out to test his famous inequalities in the following decades have led to a detailed re-examination of the concepts of quantum mechanics, and revealed the full importance of the notion of entanglement. This reconsideration helped to generate the new and extremely rich field of research known as quantum information in the 1980s. The guiding idea behind this field of activity is that, by exploiting the specific rules of quantum physics, one can conceive of new ways of calculating and communicating, in which the rules of play are no longer the well-known classical rules. One can thus develop new methods of cryptography in which the message is protected by the basic principles of quantum mechanics, and new computation methods that can be exponentially more efficient than classical algorithms. Quantum information is not therefore a mere sideline for physics, but concerns information theory, algorithmics and the mathematics of complexity theory. This research has already led to proposals for new algorithms and new computation architectures based on quantum logic gates with no classical equivalent. Still on the fundamental level, the meeting of information theory and quantum mechanics which lies at the heart of quantum information has led to a very stimulating regeneration of the theoretical tools used on both sides.
Quantum Information Science is a cross-disciplinary subject that has arisen in the last twenty years. It concerns itself with the consequences of our most complete description of the physical world (that is, quantum mechanics) for the reliable, secure, private, and rapid processing of information, both in communication and computation. While its invention is often ascribed to the famous theoretical physicist Richard Feynman in the 1980s, his contributions were only one of many that initiated the field around that time. While he perceived that new types of physical devices, in which the quantum laws of superposition and entanglement function at the logical level, could give new power in the simulation of quantum physics, it was others (Bennett, Brassard) who showed that the uncertainty principle led to fundamentally more secure ways of communicating secret messages. It was yet others (Deutsch, Vazirani) who understood that quantum theory defined a new kind of Turing machine, and that not only quantum physics simulations, but potentially many other computational problems, are sped up in this machine. And it was yet another (Shor) who found a simple, very fast algorithm for prime factorization. The word "qubit" was coined only in 1995. Its introduction is indicative of a new mindset that has developed in recent years for studying and using quantum systems. "Qubit" now stands for a durable paradigm that spans a very wide variety of fields. It thus has many sub-meanings: first, it is the basic abstract unit of information for workers ranging from optical communication engineers to NMR spectroscopists to black-hole theorists. Second, it is the name we now routinely give to physical two level systems, as they are realized by photons, atomic and ionic eigenlevels, electronic and nuclear spin, structural defects in solids, and circulating-current states of superconducting devices. Physics has long dealt with some of these two-level systems, but calling them qubits implies a whole suite of interrelated ideas and capabilities that we ascribe to these systems: the ability to precisely set, and to precisely measure, the quantum state of one unique specimen, to avoid its coupling with the environment while at the same time strongly and controllably coupling the qubits together, to exploit the resulting quantum entanglement as a resource for metrological, cryptographic, and computational tasks. Quantum Information is a very diverse subject pursued today in many different directions, by many hundreds of researchers internationally: In theoretical physics, it has enlivened and sharpened the understanding of efficient representations of entangled many-particle wavefunctions, and has provided the prospect of applications for new concepts such as anyons and majorana fermions. Information theorists has benefitted from having a rigorous extension of the basis of their field, in which classical information theory is subsumed into a greatly broader subject. Theoretical computer scientists continue the search for new quantum algorithms, and have used quantum concepts to prove new results about the classification of computational complexity. Coding theorists have had the new and subtle problem of quantum error correction to analyse and conquer. Most strikingly, the program of experimental physics has been influenced in many directions by Quantum Information Science. State-of-the-art optics experiments transmit quantum states over long distances and perform precision manipulations in single quanta (atomic ions, impurity spins, quantum dots) in the quest to have working quantum cyptography and quantum computing. Quantum Hall systems, and topological insulators, are being assiduously examined for new elementary excitations for use as qubits. In the course of ten years, superconducting devices have improved by over four orders of magnitude in their quantum coherence, a metric made precise by the ideas of quantum computing. [...] DiVincenzo, David
Quantum information has dramatically changed information science and technology, looking at the quantum nature of the information carrier as a resource for building new information protocols, designing radically new communication and computation algorithms, and ultra-sensitive measurements in metrology, with a wealth of applications. From a fundamental perspective, this new discipline has led us to regard quantum theory itself as a special theory of information, and has opened routes for exploring solutions to the tension with general relativity, based, for example, on the holographic principle, on non-causal variations of the theory, or else on the powerful algorithm of the quantum cellular automaton, which has revealed new routes for exploring quantum fields theory, both as a new microscopic mechanism on the fundamental side, and as a tool for efficient physical quantum simulations for practical purposes. In this golden age of foundations, an astonishing number of new ideas, frameworks, and results, spawned by the quantum information theory experience, have revolutionized the way we think about the subject, with a new research community emerging worldwide, including scientists from computer science and mathematics.
Quantum information, which studies the representation of information by quantum mechanical systems and the type of information processing this makes possible, is a relatively new field. Its roots, however, go back to early discussions of the interpretation of the quantum mechanical formalism. In 1935 Einstein, Podolsky and Rosen suggested that there were interpretational issues with quantum mechanics, having to do with local realism. Einstein was puzzled by an apparent lack of locality in quantum mechanical descriptions of reality, and suggested that quantum mechanics was not a complete theory. This stimulated a subsequent series of theoretical and experimental investigations. In particular, John Bell realized that Einstein's proposal for a ‘completion’ of quantum mechanics by the addition of more variables – called ‘hidden’ variables – was not consistent with quantum predictions, and could not be carried out. While these interpretational issues set the stage for what followed, the modern field of quantum information arose in the 1980s stimulated by the ever decreasing size of the elements in information processing circuits. It was realized that at some point a threshold would be crossed and the devices would start to exhibit quantum mechanical behavior. It was first determined that, if they did, it would not present a problem, and, in addition, it could even be advantageous. This led to the idea of a quantum computer that stores information in quantum states, or ‘qubits’, rather than as binary digits, or ‘bits’, in a standard digital computer. The field took off when, in 1994, Peter Shor found an efficient quantum algorithm for finding the prime factors of an integer.
Scientific progress in physics and mathematics has led to the development of efficient technology for communicating and distributing information in the 20th century. This technology forms one of the cornerstones of information society and our global economy, which are highly reliant on secure methods to transfer and distribute information quickly. To satisfy ever-increasing demands for speed and security, encryption and communication methods are constantly improved and there is an ongoing effort to develop corresponding technology further. Classical information theory is not usually part of a physics undergraduate degree course. The theory assumes simple classical properties of physical systems and based on those a largely mathematical theory of information is established. The obtained results are independent of the chosen implementation and its physical details. However, one still has to acknowledge that information is physical, that is information carriers, senders, and receivers obey the laws of physics. The notion of quantum information comes about since it turns out that the rules of quantum mechanics violate some of the basic physics assumptions in classical information theory. The consequences of this are many, ranging from improved channel capacities, the possibility of physically secure communication protocols, to invalidating some beliefs about the security of classical communication protocols. So far the approach followed in this book was to assume idealized physical systemswhich perfectly implement qubits and then demonstrate how quantum computing algorithms can be realized using perfect qubits. Error correction and fault tolerance were only mentioned briefly.
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.
Quantum physics is well known for being counter-intuitive, or even bizarre. Quantum correlations have no equivalence in classical physics. This was all well known for years. But several discoveries in the 1990's changed the world. First, in 1991 Artur Ekert, from Oxford University, discovered that quantum correlations could be used to distribute cryptographic keys. Suddenly physicists realized that quantum correlations and its associated bizarre non-locality, could be exploited to achieve a useful task that would be impossible without quantum physics. What a revolution! And this was not the end. Three years later, Peter Shor, from the AT&T Laboratories, discovered an algorithm that breaks the most used public key crypto-systems. Shor's algorithm requires a quantum computer, yet another bizarre quantum device, a kind of computer that heavily exploits the quantum superposition principle. The following year, in 1995, a collaboration between six physicists and computer scientists from three continents led to the discovery of quantum teleportation, a process with a science-fiction flavour. These discoveries and others led to the emergence of a new science, marrying quantum physics and theoretical computer science, called quantum information science. Today, a steadily growing community of physicists, mathematicians and computer scientists develop the tools of this new science. This leads to new experiments and new insights into physics and information theory. It is a fascinating time. Quantum information is still a very young science. In particular, the technology required to build a quantum computer is still unknown. Only quantum key distribution has reached a certain level of maturity, with a few start-ups already offering complete systems. Nevertheless, quantum information has been widely recognised as a source for truly innovative ideas and disruptive technologies.