dorsal/arxiv
View SchemaBounding Run-Times of Local Adiabatic Algorithms
| Authors | M. V. Panduranga Rao |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0701147 |
| URL | https://arxiv.org/abs/quant-ph/0701147 |
Abstract
A common trick for designing faster quantum adiabatic algorithms is to apply the adiabaticity condition locally at every instant. However it is often difficult to determine the instantaneous gap between the lowest two eigenvalues, which is an essential ingredient in the adiabaticity condition. In this paper we present a simple linear algebraic technique for obtaining a lower bound on the instantaneous gap even in such a situation. As an illustration, we investigate the adiabatic unordered search of van Dam et al. (How powerful is adiabatic quantum computation? Proc. IEEE FOCS, pp. 279-287, 2001) and Roland and Cerf (Physical Review A 65, 042308, 2002) when the non-zero entries of the diagonal final Hamiltonian are perturbed by a polynomial (in $\log N$, where $N$ is the length of the unordered list) amount. We use our technique to derive a bound on the running time of a local adiabatic schedule in terms of the minimum gap between the lowest two eigenvalues.
{
"annotation_id": "85ed12a6-bec8-43ea-9a22-93c12179ed55",
"date_created": "2026-03-02T18:02:34.529000Z",
"date_modified": "2026-03-02T18:02:34.529000Z",
"file_hash": "32f50bab70a4b6d66362ff4667baf23bf48ed6e7081f41a458aae9c0b1ccea51",
"private": false,
"record": {
"abstract": "A common trick for designing faster quantum adiabatic algorithms is to apply\nthe adiabaticity condition locally at every instant. However it is often\ndifficult to determine the instantaneous gap between the lowest two\neigenvalues, which is an essential ingredient in the adiabaticity condition. In\nthis paper we present a simple linear algebraic technique for obtaining a lower\nbound on the instantaneous gap even in such a situation. As an illustration, we\ninvestigate the adiabatic unordered search of van Dam et al. (How powerful is\nadiabatic quantum computation? Proc. IEEE FOCS, pp. 279-287, 2001) and Roland\nand Cerf (Physical Review A 65, 042308, 2002) when the non-zero entries of the\ndiagonal final Hamiltonian are perturbed by a polynomial (in $\\log N$, where\n$N$ is the length of the unordered list) amount. We use our technique to derive\na bound on the running time of a local adiabatic schedule in terms of the\nminimum gap between the lowest two eigenvalues.",
"arxiv_id": "quant-ph/0701147",
"authors": [
"M. V. Panduranga Rao"
],
"categories": [
"quant-ph"
],
"title": "Bounding Run-Times of Local Adiabatic Algorithms",
"url": "https://arxiv.org/abs/quant-ph/0701147"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "be4f8c57-f595-49d9-b90e-156a66fb2f14",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}