Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Authors:
- 23 December 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 50 (02725428) , 42-51
Abstract
The model of adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its exact computational power has been unknown. We settle this question and describe an efficient adiabatic simulation of any given quantum algorithm. This implies that the adiabatic computation model and the standard quantum circuit model are polynomially equivalent. We also describe an extension of this result with implications to physical implementations of adiabatic computation. We believe that our result highlights the potential importance of the adiabatic computation model in the design of quantum algorithms and in their experimental realization.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Fault-tolerant quantum computation by anyonsAnnals of Physics, 2003
- Theory of Quantum Annealing of an Ising Spin GlassScience, 2002
- Quantum search by local adiabatic evolutionPhysical Review A, 2002
- Robustness of adiabatic quantum computationPhysical Review A, 2001
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete ProblemScience, 2001
- QUANTUM HOLONOMIES FOR QUANTUM COMPUTINGInternational Journal of Modern Physics B, 2001
- How powerful is adiabatic quantum computation?2001
- Quantum Mechanics Helps in Searching for a Needle in a HaystackPhysical Review Letters, 1997
- Approximate counting, uniform generation and rapidly mixing markov chains extended abstractLecture Notes in Computer Science, 1988
- On the Adiabatic Theorem of Quantum MechanicsJournal of the Physical Society of Japan, 1950