dorsal/arxiv
View SchemaHow fast can a quantum computer search?
| Authors | Lov K. Grover |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9809029 |
| URL | https://arxiv.org/abs/quant-ph/9809029 |
Abstract
This paper gives a simple proof of why a quantum computer, despite being in all possible states simultaneously, needs at least 0.707 sqrt(N) queries to retrieve a desired item from an unsorted list of items. The proof is refined to show that a quantum computer would need at least 0.785 sqrt(N) queries. The quantum search algorithm needs precisely this many queries.
{
"annotation_id": "80952b88-597d-4da1-aa55-05b4af4ba6a8",
"date_created": "2026-03-02T18:02:44.403000Z",
"date_modified": "2026-03-02T18:02:44.403000Z",
"file_hash": "82bba5a590b65ecf52f21238b8fa70b520fa4924d71bd5c93cad1e462e7ed130",
"private": false,
"record": {
"abstract": "This paper gives a simple proof of why a quantum computer, despite being in\nall possible states simultaneously, needs at least 0.707 sqrt(N) queries to\nretrieve a desired item from an unsorted list of items. The proof is refined to\nshow that a quantum computer would need at least 0.785 sqrt(N) queries. The\nquantum search algorithm needs precisely this many queries.",
"arxiv_id": "quant-ph/9809029",
"authors": [
"Lov K. Grover"
],
"categories": [
"quant-ph"
],
"title": "How fast can a quantum computer search?",
"url": "https://arxiv.org/abs/quant-ph/9809029"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4bc6db53-05e4-4da3-b884-8bfdef6dc847",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}