Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation

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.

Authors

• Dorit Aharonov
• Wim van Dam
• Julia Kempe
• Zeph Landau
• Seth Lloyd
• Oded Regev 0001

Keywords

• Quantum computing
• Computer science
• Computational modeling
• Stationary state
• Physics computing
• Quantum mechanics
• Polynomials
• Power engineering computing
• Eigenvalues and eigenfunctions
• Mathematics
• Adiabatic Quantum Computing
• Power Calculation
• Standard Model
• Efficient Simulation
• Quantum Circuit
• Quantum Algorithms
• Markov Chain
• Largest Eigenvalue
• Quantum System
• Calculation Of Yield
• Hermitian Matrix
• Two-dimensional Lattice
• Left Eigenvectors
• Qubit State
• Quantum Gates
• Lowest Eigenvalue
• Two-qubit Gates