Information is physical: the laws which govern its encoding, processing and communication are those of its unavoidable physical embodyment. In today's computing, information obeys the laws of Newton's and Maxwell's classical physics: this assertion holds all the way from commercial computers down to their most abstract models, e.g. Turing machines and lambda-calculi. Today's computation is classical.Research in quantum information processing and communication (QIPC) was born some twenty years ago, as a child of two major scientific achievements of the 20th century, namely quantum physics and information sciences. The driving force of this interdisciplinary research is that of looking for the consequences of having information encoding, computation and communication obey the laws of quantum physics, i.e. the ultimate knowledge that we have, today, of the foreign world of elementary particles, as described by quantum mechanics. Breakthroughs in algorithmics, cryptography, information theory and abstract computational models have shown that this rerooting of information from classical to quantum has far reaching consequences, both quantitative and qualitative, and opens new avenues for research within the foundations of computer science.The aim of this tutorial is to give a survey of the principles, main results and long term perspectives of current research in QIPC, from a computer science point of view. No prior knowledge in quantum mechanics is required to follow this tutorial. There will be two parts:1 - Computation, the quantum way: quantum bits and quantum operations; two major quantum algorithms: quadratic speedup for unordered database search (Grover's algorithm), exponential speedup for integer factoring (Shor's algorithm);2 - Communication, the quantum way, and longer term perspectives: quantum state teleportation; a quantum cryptographic protocol for secret key distribution. Hot topics in QIPC research, state of the art in physical implementation of quantum computers.
Information is physical: the laws which govern its encoding, processing and communication are those of its unavoidable physical embodyment. In today's computing, information obeys the laws of Newton's and Maxwell's classical physics: this assertion holds all the way from commercial computers down to their most abstract models, e.g. Turing machines and lambda-calculi. Today's computation is classical.Research in quantum information processing and communication (QIPC) was born some twenty years ago, as a child of two major scientific achievements of the 20th century, namely quantum physics and information sciences. The driving force of this interdisciplinary research is that of looking for the consequences of having information encoding, computation and communication obey the laws of quantum physics, i.e. the ultimate knowledge that we have, today, of the foreign world of elementary particles, as described by quantum mechanics. Breakthroughs in algorithmics, cryptography, information theory and abstract computational models have shown that this rerooting of information from classical to quantum has far reaching consequences, both quantitative and qualitative, and opens new avenues for research within the foundations of computer science.The aim of this tutorial is to give a survey of the principles, main results and long term perspectives of current research in QIPC, from a computer science point of view. No prior knowledge in quantum mechanics is required to follow this tutorial. There will be two parts:1 - Computation, the quantum way: quantum bits and quantum operations; two major quantum algorithms: quadratic speedup for unordered database search (Grover's algorithm), exponential speedup for integer factoring (Shor's algorithm);2 - Communication, the quantum way, and longer term perspectives: quantum state teleportation; a quantum cryptographic protocol for secret key distribution. Hot topics in QIPC research, state of the art in physical implementation of quantum computers.
Information is physical. Today’s information processing and communication are classical: they are based upon the laws of Newton’s and Maxwell’s classical physics. This assertion holds all the way, from commercial computers and networks, up to their most abstract models, e.g. Turing machines. Research in quantum information was born some twenty five years ago, with the encounter of two major scientific achievements of the 20th century, namely quantum physics and information sciences. A technological motivation for that is an extrapolation of Moore’s law which seems to indicate that the amount of matter needed for one bit will be reduced to one particle sometimes before year 2020. A deeper, scientific driving force of this interdisciplinary research is that of looking for the consequences of having computation and communication based directly upon the laws of quantum physics, i.e. our current ultimate knowledge of the world of elementary particles, as described by quantum mechanics. Breakthroughs in cryptography, communications, information theory and algorithmics have shown that this transplantation from classical to quantum has far reaching consequences, both quantitative and qualitative, and opens new avenues for research within the foundations of computer science and physics. The principles 388 and most striking results and hot topics of this promising way of encoding, processing and communicating information are briefly introduced in this chapter from a mostly computer science point of view, with detailed examples in algorithmics and in cryptography. At the end of the chapter, a short list of some significant articles, textbooks and reports on quantum information are suggested for further reading.
Information is physical: the laws which govern its encoding, processing and communication are bound by those of its unavoidably physical embodiment. In today's informatics, information obeys the laws of Newton's and Maxwell's classical physics: this assertion holds all the way from commercial computers down to (up to?) their most abstract models, e.g. Turing machines and lambda-calculus. Today's computation and communication are classical. Research in quantum information processing and communication was born some twenty five years ago, as a child of two major scientific achievements of the 20th century, namely quantum physics and information sciences. The driving force of this interdisciplinary research is that of looking for the consequences of having information encoding, computation and communication based upon the laws of quantum physics, i.e. the ultimate knowledge that we have, today, of the foreign world of elementary particles, as described by quantum mechanics. Breakthroughs in cryptography, communications, information theory, algorithmics and, more recently, in abstract computational models, programming languages and semantics frameworks, have shown that this transplantation of information from classical to quantum has far reaching consequences, both quantitative and qualitative, and opens new avenues for research within the foundations of computer science.From a computer scientist's point of view, which is my point of view, I will explain the basics, survey the main achievements, and outline the current hot topics and major challenges of this promising and stimulating research. I will not assume any prior knowledge in quantum mechanics from the audience.
Research in quantum computation is looking for the consequences of having information encoding, processing and communication exploit the laws of quantum physics, i.e. the laws which govern the ultimate knowledge that we have, today, of the foreign world of elementary particles, as described by quantum mechanics. This paper starts with a short survey of the principles which underlie quantum computing, and of some of the major breakthroughs brought by the first ten to fifteen years of research in this domain; quantum algorithms and quantum teleportation are very biefly presented. The next sections are devoted to one among the many directions of current research in the quantum computation paradigm, namely quantum programming languages and their semantics. A few other hot topics and open problems in quantum information processing and communication are mentionned in few words in the concluding remarks, the most difficult of them being the physical implementation of a quantum computer. The interested reader will find a list of useful references at the end of the paper.
The theoretical, experimental and technological areas covering the use of quantum mechanics for communication and computation.Quantum information processing includes investigations in quantum information theory, quantum communication, quantum computation, quantum algorithms and their complexity, and quantum control.The science of quantum information processing is a highly interdisciplinary field.In the context of mathematics it is stimulating research in pure mathematics (e.g.coding theory, *algebras, quantum topology) as well as requiring and providing many opportunities for applied mathematics.The science of quantum information processing emerged from the recognition that usable notions of information need to be physically implementable.In the 1960s and 1970s researchers such as R. Landauer, C. Bennett, C. Helstrom and A. Holevo realized that the laws of physics give rise to fundamental constraints on the ability to implement and manipulate information.Landauer repeatedly stated that "information is physical", providing impetus to the idea that it should be possible to found theories of information on the laws of physics.This is in contrast to the introspective approach which led to the basic definitions of computer science and information theory as formulated by A. Church, A. Turing, C. Shannon and others in the first half of the 20th century.Early work in studying the physical foundations of information focused on the effects of energy limitations and the need for dissipating heat in computation and communication.Beginning with S. Wiesner's work on applications of quantum mechanics to cryptography in the late 1960s, it was realized that there may be intrinsic advantages to using quantum physics in information processing.Quantum cryptography and quantum communication in general were soon established as interesting and non-trivial extensions of classical communication based on bits.That quantum mechanics may be used to improve the efficiency of algorithms was first realized when attempts at simulating quantum mechanical systems resulted in exponentially complex algorithms compared to the physical resources associated with the system simulated.In the 1980s, P. Benioff and R. Feynman introduced the idea of a quantum computer for efficiently implementing quantum physics simulations.Models of quantum computers were developed by D. Deutsch, leading to the formulation of artificial problems that could be solved more efficiently by quantum than by classical computers.The advantages of quantum computers became widely recognized when P.
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
During the last ten years, Quantum Information Processing and Communication (QIPC) has established itself as one of the new hot topic fields in physics, with the potential to revolutionize many areas of science and technology. QIPC replaces the laws of classical physics applied to computation and communication with the more fundamental laws of quantum mechanics. This becomes increasingly important due to technological progress going down to smaller and smaller scales where quantum effects start to be dominant. In addition to its fundamental nature, QIPC promises to advance computing power beyond the capabilities of any classical computer, to guarantee secure communication and establish direct links to emerging quantum technologies, such as, for example, quantum based sensors and clocks. One of the outstanding features of QIPC is its interdisciplinary character: it brings together researchers from physics, mathematics and computer science. In particular, within physics we have seen the emergence of a new QIPC community, which ranges from theoretical to experimental physics, and crosses boundaries of traditionally separated disciplines such as atomic physics, quantum optics, statistical mechanics and solid state physics, all working on different and complementary aspects of QIPC. This publication covers the following topics: introduction to quantum computing; quantum logic, information and entanglement; quantum algorithms; error-correcting codes for quantum computations; quantum measurements and control; quantum communication; quantum optics and cold atoms for quantum information; quantum computing with solid state devices; theory and experiments for superconducting qubits; interactions in many-body systems: quantum chaos, disorder and random matrices; decoherence effects for quantum computing; and flature prospects of quantum information processing.