The main ideas behind developments in the theory and technology of quantum computation were formulated in the late 1970s and early 1980s by two physicists in the West and a mathematician in the former Soviet Union. It is not generally known in the West that the subject has roots in the Russian technical literature. The idea, as propagated by Benioff and (especially) Feynman, is reviewed along with the proposition of a foundation for this kind of computation by Manin in the Russian literature. The author hopes to present as impartial a synthesis as possible of the early history of thought on this subject. The role of reversible and irreversible computational processes will be examined briefly as it relates to the origins of quantum computing and the so-called Information Paradox in physics. Information theory and physics, as this paradox shows, have much to communicate to each other.
The main ideas behind developments in the theory and technology of quantum computation were formulated in the late 1970s and early 1980s by two physicists in the West and a mathematician in the former Soviet Union. It is not generally known in the West that the subject has roots in the Russian technical literature. The idea, as propagated by Benioff and (especially) Feynman, is reviewed along with the proposition of a foundation for this kind of computation by Manin in the Russian literature. The author hopes to present as impartial a synthesis as possible of the early history of thought on this subject. The role of reversible and irreversible computational processes will be examined briefly as it relates to the origins of quantum computing and the so-called Information Paradox in physics. Information theory and physics, as this paradox shows, have much to communicate to each other.
Quantum Computing and Quantum Information Science seem very promising and developing rapidly since its inception in early 1980s by Paul Benioff with the proposal of quantum mechanical model of the Turing machine and later By Richard Feynman and Yuri Manin for the proposal of a quantum computers for simulating various problems that classical computer could not. Quantum computers have a computational advantage for some problems, over classical computers and most applications are trying to use an efficient combination of classical and quantum computers like Shor’s factoring algorithm. Other areas that are expected to be benefitted from quantum computing are Machine Learning and deep learning, molecular biology, genomics and cancer research, space exploration, atomic and nuclear research and macro-economic forecasting. This paper represents a brief overview of the state of art of quantum computing and quantum information science with discussions of various theoretical and experimental aspects adopted by the researchers.
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.
After some remarks on the fundamental physical nature of information, Bennett and Fredkin’s ideas reversible computation are introduced. This leads to the suggestions of Benioff and Feynman as to the possibility of a new type of essentially ‘quantum computer’. If we happen to build such devices, Deutsch scientists showed that‘quantum parallelism’ leads to new algorithms and new complexity classes. This is dramatically illustrated by Shor's quantum algorithm for factorization which is polynomial in time in contrast to algorithms for factorization on a classical Turing computer. This discovery has potentially important implications for the security of many modern cryptographic systems. The fundamentals of quantum computing are then introduced - reversible logic gates, qubits and quantum registers. The key quantum property of ‘entanglement’ is described, with due homage to Einstein and Bell. As an illustration of a quantum program, Grover's database search algorithm is described in some detail. After all this theory, the status of experimental attempts to build a quantum computer is reviewed: it will become evident that we have a long way to go before we can factorize even small numbers. Finally, we end with some thoughts about the process of ‘quantum compilation’ - translating a quantum algorithm into actual physical operations on a quantum system - and some comments on prospects for future progress.
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.
In 1994 Peter Shor [65] published a factoring algorithm for a quantum computer that finds the prime factors of a composite integer N more efficiently than is possible with the known algorithms for a classical com puter. Since the difficulty of the factoring problem is crucial for the se curity of a public key encryption system, interest (and funding) in quan tum computing and quantum computation suddenly blossomed. Quan tum computing had arrived. The study of the role of quantum mechanics in the theory of computa tion seems to have begun in the early 1980s with the publications of Paul Benioff [6]' [7] who considered a quantum mechanical model of computers and the computation process. A related question was discussed shortly thereafter by Richard Feynman [35] who began from a different perspec tive by asking what kind of computer should be used to simulate physics. His analysis led him to the belief that with a suitable class of "quantum machines" one could imitate any quantum system.
Modern computer science emerged when the eminent British mathematician Alan Turing invented the concept of Turing machine (TM) in 1936. Though very simple and primitive, TM serves as the universal model for all known physical computation devices. The principles of quantum mechanics, another revolutionary scientific discovery of the 20 th century, had never been incorporated in the theory of computation until the early 1980s. P. Benioff first coined the concept of quantum Turing machine (QTM). Motivated by the problem that classical computers cannot simulate quantum systems efficiently, R. Feynman posed the quantum computer as the solution. The field of quantum computation was born.