Journal
SIAM JOURNAL ON COMPUTING
Volume 37, Issue 1, Pages 166-194Publisher
SIAM PUBLICATIONS
DOI: 10.1137/S0097539705447323
Keywords
quantum computation; adiabatic computation; nearest neighbor interactions
Ask authors/readers for more resources
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 allows stating the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of sparse matrices.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available