Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation

Simple item page
dc.creatorAharonov, Dorit
dc.creatorvan Dam, Wim
dc.creatorKempe, Julia
dc.creatorLandau, Zeph
dc.creatorLloyd, Seth
dc.creatorRegev, Oded
dc.date2004-05-18
dc.date2005-03-26
dc.date.accessioned2026-07-07T08:44:20Z
dc.date.available2026-07-07T08:44:20Z
dc.descriptionAdiabatic 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.
dc.description30 pages, updated version
dc.identifierhttps://arxiv.org/abs/quant-ph/0405098
dc.identifierhttp://arxiv.org/abs/quant-ph/0405098
dc.identifierSIAM Journal of Computing, Vol. 37, Issue 1, p. 166-194 (2007), conference version in Proc. 45th FOCS, p. 42-51 (2004)
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/142622
dc.subjectQuantum Physics
dc.titleAdiabatic Quantum Computation is Equivalent to Standard Quantum Computation
dc.typetext

Files

Collections

arXiv