dorsal/arxiv
View SchemaAdiabatic Quantum Computation is Equivalent to Standard Quantum Computation
| Authors | Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0405098 |
| URL | https://arxiv.org/abs/quant-ph/0405098 |
| Journal | SIAM Journal of Computing, Vol. 37, Issue 1, p. 166-194 (2007), conference version in Proc. 45th FOCS, p. 42-51 (2004) |
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.
{
"annotation_id": "18e0c56f-64a2-40e8-b75a-0f3e1ad857d3",
"date_created": "2026-03-02T18:02:06.145000Z",
"date_modified": "2026-03-02T18:02:06.145000Z",
"file_hash": "4b08a849dc502f759999b13004408680aef00149e1a1490b4e6d05c8752d1aa7",
"private": false,
"record": {
"abstract": "Adiabatic quantum computation has recently attracted attention in the physics\nand computer science communities, but its computational power was unknown. We\ndescribe an efficient adiabatic simulation of any given quantum algorithm,\nwhich implies that the adiabatic computation model and the conventional quantum\ncomputation model are polynomially equivalent. Our result can be extended to\nthe physically realistic setting of particles arranged on a two-dimensional\ngrid with nearest neighbor interactions. The equivalence between the models\nprovides a new vantage point from which to tackle the central issues in quantum\ncomputation, namely designing new quantum algorithms and constructing fault\ntolerant quantum computers. In particular, by translating the main open\nquestions in the area of quantum algorithms to the language of spectral gaps of\nsparse matrices, the result makes these questions accessible to a wider\nscientific audience, acquainted with mathematical physics, expander theory and\nrapidly mixing Markov chains.",
"arxiv_id": "quant-ph/0405098",
"authors": [
"Dorit Aharonov",
"Wim van Dam",
"Julia Kempe",
"Zeph Landau",
"Seth Lloyd",
"Oded Regev"
],
"categories": [
"quant-ph"
],
"journal_ref": "SIAM Journal of Computing, Vol. 37, Issue 1, p. 166-194 (2007),\n conference version in Proc. 45th FOCS, p. 42-51 (2004)",
"title": "Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation",
"url": "https://arxiv.org/abs/quant-ph/0405098"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "efc8a0ac-8fe0-49a4-8177-4077354203f0",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}