dorsal/arxiv
View SchemaAn information-theoretic analysis of Grover's algorithm
| Authors | Erdal Arikan |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0210068 |
| URL | https://arxiv.org/abs/quant-ph/0210068 |
Abstract
Grover discovered a quantum algorithm for identifying a target element in an unstructured search universe of N items in approximately square-root of N queries to a quantum oracle, thus achieving a square-root speed-up over classical algorithms. We present an information-theoretic analysis of Grover's algorithm and show that the square-root speed-up is the best attainable result using Grover's oracle.
{
"annotation_id": "42b891f1-6e44-4122-a527-f86222fa9d60",
"date_created": "2026-03-02T18:01:53.170000Z",
"date_modified": "2026-03-02T18:01:53.170000Z",
"file_hash": "bf07d1b0684c8213d592b3da4d620d2fe87cf0902351eef3756b3efe92d3677b",
"private": false,
"record": {
"abstract": "Grover discovered a quantum algorithm for identifying a target element in an\nunstructured search universe of N items in approximately square-root of N\nqueries to a quantum oracle, thus achieving a square-root speed-up over\nclassical algorithms. We present an information-theoretic analysis of Grover\u0027s\nalgorithm and show that the square-root speed-up is the best attainable result\nusing Grover\u0027s oracle.",
"arxiv_id": "quant-ph/0210068",
"authors": [
"Erdal Arikan"
],
"categories": [
"quant-ph"
],
"title": "An information-theoretic analysis of Grover\u0027s algorithm",
"url": "https://arxiv.org/abs/quant-ph/0210068"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "3b677f9e-ab50-403c-8f86-fa461606b50d",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}