dorsal/arxiv
View SchemaA fast quantum mechanical algorithm for database search
| Authors | Lov K. Grover |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9605043 |
| URL | https://arxiv.org/abs/quant-ph/9605043 |
Abstract
Imagine a phone directory containing N names arranged in completely random order. In order to find someone's phone number with a 50% probability, any classical algorithm (whether deterministic or probabilistic) will need to look at a minimum of N/2 names. 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)) steps. The algorithm is within a small constant factor of the fastest possible quantum mechanical algorithm.
{
"annotation_id": "086a64e7-9301-4a35-b8d2-f25ee89918bb",
"date_created": "2026-03-02T18:02:38.118000Z",
"date_modified": "2026-03-02T18:02:38.118000Z",
"file_hash": "f910ac31ca6e0607c01e845e0deeb6257c338ad088e818b49a58803434d0b1db",
"private": false,
"record": {
"abstract": "Imagine a phone directory containing N names arranged in completely random\norder. In order to find someone\u0027s phone number with a 50% probability, any\nclassical algorithm (whether deterministic or probabilistic) will need to look\nat a minimum of N/2 names. Quantum mechanical systems can be in a superposition\nof states and simultaneously examine multiple names. By properly adjusting the\nphases of various operations, successful computations reinforce each other\nwhile others interfere randomly. As a result, the desired phone number can be\nobtained in only O(sqrt(N)) steps. The algorithm is within a small constant\nfactor of the fastest possible quantum mechanical algorithm.",
"arxiv_id": "quant-ph/9605043",
"authors": [
"Lov K. Grover"
],
"categories": [
"quant-ph"
],
"title": "A fast quantum mechanical algorithm for database search",
"url": "https://arxiv.org/abs/quant-ph/9605043"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "37ee6dee-e2c8-4912-a3b1-58b4cd8e66f2",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}