The basic ideas of quantum computation are introduced by a brief discussion of Bennett (1973, 1982) and Fredkin's (1982, 1997) ideas of reversible computation. After some remarks about Deutsch's (1985) pioneering work on quantum complexity and Shor's (1996) factorisation algorithm, quantum logic gates, qubits and registers are discussed. The role of quantum entanglement is stressed and Grover's (1997) quantum search algorithm described in detail. The paper ends with a review of the current experimental status of quantum computers.
The basic ideas of quantum computation are introduced by a brief discussion of Bennett (1973, 1982) and Fredkin's (1982, 1997) ideas of reversible computation. After some remarks about Deutsch's (1985) pioneering work on quantum complexity and Shor's (1996) factorisation algorithm, quantum logic gates, qubits and registers are discussed. The role of quantum entanglement is stressed and Grover's (1997) quantum search algorithm described in detail. The paper ends with a review of the current experimental status of quantum computers.
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.
Quantum computing uses quantum-mechanical principles to enable new models of computation bexond the classical paradigm. This article presents an accessible introduction to the mathematical and conceptual foundations of quantum computing, covering qubits, quantum gates, multi-qubit systems, entanglement, and measurement. The gate-based computation model and quantum circuits are introduced, together with key notations such as universality and reversibility. As an illustrative example, the Deutsch-Josza algorithm is discussed to demonstrate how quantum algorithm can be constucted. The article concludes with a brief overview of the current state and challenges of quantum computing.
This chapter contains an introduction to the main concepts in quantum computation and entanglement. It starts with a brief introduction to computational complexity and then introduces quantum gates and quantum networks, discussing the universality issue in quantum computation. A review on the main known quantum algorithms follows, including Deutsch's, Deutsch-Jozsa's, Grover's and Shor's algorithms. The basic concepts in the theory of quantum error correction are then reviewed. The second part of the chapter is devoted to entanglement. It starts by reminding the basic definitions of entanglement and entanglement criteria for bipartite and multipartite systems, and then discusses the role that entanglement plays in the quantum algorithms described before. The chapter ends with short descriptions of NMR quantum computing, the computational model DQC1, and one-way quantum computing.
Quantum Computing is a new and exciting field at the intersection of mathematics, computer science and physics. It concerns a utilization of quantum mechanics to improve the efficiency of computation. Here we present a gentle introduction to some of the ideas in quantum computing. The paper begins by motivating the central ideas of quantum mechanics and quantum computation with simple toy models. From there we move on to a formal presentation of the small fraction of (finite dimensional) quantum mechanics that we will need for basic quantum computation. Central notions of quantum architecture (qubits and quantum gates) are described. The paper ends with a presentation of one of the simplest quantum algorithms: Deutsch's algorithm. Our presentation demands neither advanced mathematics nor advanced physics.
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.