dorsal/arxiv
View SchemaQuantum Search by Local Adiabatic Evolution
| Authors | Jeremie Roland, Nicolas J. Cerf |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0107015 |
| URL | https://arxiv.org/abs/quant-ph/0107015 |
| DOI | 10.1103/PhysRevA.65.042308 |
| Journal | Phys. Rev. A 65, 042308 (2002) |
Abstract
The adiabatic theorem has been recently used to design quantum algorithms of a new kind, where the quantum computer evolves slowly enough so that it remains near its instantaneous ground state which tends to the solution [Farhi et al., quant-ph/0001106]. We apply this time-dependent Hamiltonian approach to the Grover's problem, i. e., searching a marked item in an unstructured database. We find that, by adjusting the evolution rate of the Hamiltonian so as to keep the evolution adiabatic on each infinitesimal time interval, the total running time is of order $\sqrt{N}$, where $N$ is the number of items in the database. We thus recover the advantage of Grover's standard algorithm as compared to a classical search, scaling as $N$. This is in contrast with the constant-rate adiabatic approach developed by Farhi et al., where the requirement of adiabaticity is expressed only globally, resulting in a time of order $N$.
{
"annotation_id": "6f859e55-c62d-4d47-bac3-02f13719e1ca",
"date_created": "2026-03-02T18:01:46.081000Z",
"date_modified": "2026-03-02T18:01:46.081000Z",
"file_hash": "a09413ffae6d878eb22bfea5e42efa6d1dc02a6b83aefc6b5aa9ae42b5b2e9a2",
"private": false,
"record": {
"abstract": "The adiabatic theorem has been recently used to design quantum algorithms of\na new kind, where the quantum computer evolves slowly enough so that it remains\nnear its instantaneous ground state which tends to the solution [Farhi et al.,\nquant-ph/0001106]. We apply this time-dependent Hamiltonian approach to the\nGrover\u0027s problem, i. e., searching a marked item in an unstructured database.\nWe find that, by adjusting the evolution rate of the Hamiltonian so as to keep\nthe evolution adiabatic on each infinitesimal time interval, the total running\ntime is of order $\\sqrt{N}$, where $N$ is the number of items in the database.\nWe thus recover the advantage of Grover\u0027s standard algorithm as compared to a\nclassical search, scaling as $N$. This is in contrast with the constant-rate\nadiabatic approach developed by Farhi et al., where the requirement of\nadiabaticity is expressed only globally, resulting in a time of order $N$.",
"arxiv_id": "quant-ph/0107015",
"authors": [
"Jeremie Roland",
"Nicolas J. Cerf"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.65.042308",
"journal_ref": "Phys. Rev. A 65, 042308 (2002)",
"title": "Quantum Search by Local Adiabatic Evolution",
"url": "https://arxiv.org/abs/quant-ph/0107015"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e2b51140-98f7-49ba-8595-9d8fbf828a14",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}