Quantum Computation
arXiv:quant-ph/9812037 · doi:10.1142/9789812815569_0007
Abstract
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.
77 pages, figures included in the ps file. To appear in: Annual Reviews of Computational Physics, ed. Dietrich Stauffer, World Scientific, vol VI, 1998. The paper can be down loaded also from http://www.math.ias.edu/~doria/
References in corpus (16)
- Fault-tolerant quantum computation by anyons
- A Theory of Fault-Tolerant Quantum Computation
- Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
- Grover's quantum searching algorithm is optimal
- Experimental realization of a quantum algorithm
- Experimental Quantum Error Correction
- Quantum computers can search arbitrarily large databases by a single query
- Nuclear magnetic resonance spectroscopy: An experimentally accessible paradigm for quantum computing
- Programmable quantum gate arrays
- An approximate Fourier transform useful in quantum factoring
- Approximate quantum error correction can lead to better codes
- Quantum Computation in Quantum-Hall Systems
- Quantum Lower Bounds by Polynomials
- Fault-tolerant quantum computation
- A nonadditive quantum code
- Quantum computation with phase drift errors
Cited by in corpus (31)
- The Physical Implementation of Quantum Computation
- Information and Computation: Classical and Quantum Aspects
- Quantum speedup of Monte Carlo methods
- Decoherence-Free Subspaces for Multiple-Qubit Errors: (II) Universal, Fault-Tolerant Quantum Computation
- Quantum Computer Emulator
- Scale invariance of entanglement dynamics in Grover's quantum search algorithm
- Grover's Algorithm: Quantum Database Search
- Landauer Principle and Thermodynamics of Computation
- Universal corrections to the entanglement entropy in gapped quantum spin chains: a numerical study
- Semantics and simulation of communication in quantum programming
- Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
- State of the art and prospects for quantum computing
- KMS states on Quantum Grammars
- Robustness of Controlled Quantum Dynamics
- Shor's Algorithm for Factoring Large Integers
- The Significance of Information in Quantum Theory
- An entangling-probe attack on Shor's algorithm for factorization
- Quantum Radio Astronomy: Data Encodings and Quantum Image Processing
- Grover's algorithm and human memory
- Finding Solutions to NP Problems: Philosophical Difference Between Quantum and Evolutionary Search Algorithms
- Quantum Neural Networks
- Detecting Entanglement Generating Circuits in Cloud-Based Quantum Computing
- Superlinear advantage for exact quantum algorithms
- Brain neurons as quantum computers: {\it in vivo} support of background physics
- Computational Complexity for Physicists
- Memory Efficient Quantum Circuit Simulator Based on Linked List Architecture
- Leveraging Unknown Structure in Quantum Query Algorithms
- The parallel Grover as dynamic system
- State-Dependent Quantum Copying: an adaptive ancillary systems and its limitations
- Creating long-range entangled Majorana pairs: from spin-1/2 twisted Kitaev to generalized XY chains
- Improved Quantum Query Complexity on Easier Inputs