Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
arXiv:quant-ph/0405098
Abstract
Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models provides a new vantage point from which to tackle the central issues in quantum computation, namely designing new quantum algorithms and constructing fault tolerant quantum computers. In particular, by translating the main open questions in the area of quantum algorithms to the language of spectral gaps of sparse matrices, the result makes these questions accessible to a wider scientific audience, acquainted with mathematical physics, expander theory and rapidly mixing Markov chains.
30 pages, updated version
References in corpus (22)
- Fault-tolerant quantum computation by anyons
- Quantum Mechanics helps in searching for a needle in a haystack
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Measurement of conditional phase shifts for quantum logic
- Exponential algorithmic speedup by quantum walk
- Geometric quantum computation with NMR
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Search by Local Adiabatic Evolution
- Experimental realization of a quantum algorithm
- Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer
- Robustness of adiabatic quantum computation
- Nuclear magnetic resonance spectroscopy: An experimentally accessible paradigm for quantum computing
- Geometric Quantum Computation
- Adiabatic Quantum Computation in Open Systems
- Experimental implementation of an adiabatic quantum optimization algorithm
- Quantum Holonomies for Quantum Computing
- Noise resistance of adiabatic quantum computation using random matrix theory
- Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
- Quantum Adiabatic Evolution Algorithms with Different Paths
- An Elementary Proof of the Quantum Adiabatic Theorem
- Robustness of the adiabatic quantum search
- Improved bounds on the spectral gap above frustration free ground states of quantum spin chains