dorsal/arxiv
View SchemaLimitations of some simple adiabatic quantum algorithms
| Authors | Lawrence M. Ioannou, Michele Mosca |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0702241 |
| URL | https://arxiv.org/abs/quant-ph/0702241 |
| Journal | International Journal of Quantum Information, Vol. 6, No. 3 (June 2008) |
Abstract
Let $H(t)=(1-t/T)H_0 + (t/T)H_1$, $t\in [0,T]$, be the Hamiltonian governing an adiabatic quantum algorithm, where $H_0$ is diagonal in the Hadamard basis and $H_1$ is diagonal in the computational basis. We prove that $H_0$ and $H_1$ must each have at least two large mutually-orthogonal eigenspaces if the algorithm's running time is to be subexponential in the number of qubits. We also reproduce the optimality proof of Farhi and Gutmann's search algorithm in the context of this adiabatic scheme; because we only consider initial Hamiltonians that are diagonal in the Hadamard basis, our result is slightly stronger than the original.
{
"annotation_id": "dbc6e902-30cf-47b2-9790-da7a60eca6a1",
"date_created": "2026-03-02T18:02:33.708000Z",
"date_modified": "2026-03-02T18:02:33.708000Z",
"file_hash": "2043d4b699df48f3611110f1137575adfaa4412f584afc02244484b4c14bbd75",
"private": false,
"record": {
"abstract": "Let $H(t)=(1-t/T)H_0 + (t/T)H_1$, $t\\in [0,T]$, be the Hamiltonian governing\nan adiabatic quantum algorithm, where $H_0$ is diagonal in the Hadamard basis\nand $H_1$ is diagonal in the computational basis. We prove that $H_0$ and $H_1$\nmust each have at least two large mutually-orthogonal eigenspaces if the\nalgorithm\u0027s running time is to be subexponential in the number of qubits. We\nalso reproduce the optimality proof of Farhi and Gutmann\u0027s search algorithm in\nthe context of this adiabatic scheme; because we only consider initial\nHamiltonians that are diagonal in the Hadamard basis, our result is slightly\nstronger than the original.",
"arxiv_id": "quant-ph/0702241",
"authors": [
"Lawrence M. Ioannou",
"Michele Mosca"
],
"categories": [
"quant-ph"
],
"journal_ref": "International Journal of Quantum Information, Vol. 6, No. 3 (June\n 2008)",
"title": "Limitations of some simple adiabatic quantum algorithms",
"url": "https://arxiv.org/abs/quant-ph/0702241"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6046be33-a990-4bab-80c5-fc7dd29f89be",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}