dorsal/arxiv
View SchemaQuantum Mechanics helps in searching for a needle in a haystack
| Authors | Lov K. Grover |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9706033 |
| URL | https://arxiv.org/abs/quant-ph/9706033 |
| DOI | 10.1103/PhysRevLett.79.325 |
| Journal | Phys.Rev.Lett.79:325-328,1997 |
Abstract
Quantum mechanics can speed up a range of search applications over unsorted data. For example imagine a phone directory containing N names arranged in completely random order. To find someone's phone number with a probability of 50%, any classical algorithm (whether deterministic or probabilistic) will need to access the database a minimum of O(N) times. Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. By properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly. As a result, the desired phone number can be obtained in only O(sqrt(N)) accesses to the database.
{
"annotation_id": "f79fd431-b120-468d-90ec-c3bdbc95bcab",
"date_created": "2026-03-02T18:02:40.514000Z",
"date_modified": "2026-03-02T18:02:40.514000Z",
"file_hash": "0409f63a04f647d912f87f1ae1da7c2756dc1cdbbca07156a558bad1127098a8",
"private": false,
"record": {
"abstract": "Quantum mechanics can speed up a range of search applications over unsorted\ndata. For example imagine a phone directory containing N names arranged in\ncompletely random order. To find someone\u0027s phone number with a probability of\n50%, any classical algorithm (whether deterministic or probabilistic) will need\nto access the database a minimum of O(N) times. Quantum mechanical systems can\nbe in a superposition of states and simultaneously examine multiple names. By\nproperly adjusting the phases of various operations, successful computations\nreinforce each other while others interfere randomly. As a result, the desired\nphone number can be obtained in only O(sqrt(N)) accesses to the database.",
"arxiv_id": "quant-ph/9706033",
"authors": [
"Lov K. Grover"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevLett.79.325",
"journal_ref": "Phys.Rev.Lett.79:325-328,1997",
"title": "Quantum Mechanics helps in searching for a needle in a haystack",
"url": "https://arxiv.org/abs/quant-ph/9706033"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "852b91a6-f40e-430e-9979-40f926d52b69",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}