dorsal/arxiv
View SchemaQuantum Mechanical Square Root Speedup in a Structured Search Problem
| Authors | Edward Farhi, Sam Gutmann |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9711035 |
| URL | https://arxiv.org/abs/quant-ph/9711035 |
Abstract
An unstructured search for one item out of N can be performed quantum mechanically in time of order square root of N whereas classically this requires of order N steps. This raises the question of whether square root speedup persists in problems with more structure. In this note we focus on one example of a structured problem and find a quantum algorithm which takes time of order the square root of the classical time.
{
"annotation_id": "92ec2ed7-c628-4732-a65f-9eea6198924b",
"date_created": "2026-03-02T18:02:41.598000Z",
"date_modified": "2026-03-02T18:02:41.598000Z",
"file_hash": "8afc77c224d9d34ad822dbeacb921e77a0cbf4486260c17736b0fc9ad394947e",
"private": false,
"record": {
"abstract": "An unstructured search for one item out of N can be performed quantum\nmechanically in time of order square root of N whereas classically this\nrequires of order N steps. This raises the question of whether square root\nspeedup persists in problems with more structure. In this note we focus on one\nexample of a structured problem and find a quantum algorithm which takes time\nof order the square root of the classical time.",
"arxiv_id": "quant-ph/9711035",
"authors": [
"Edward Farhi",
"Sam Gutmann"
],
"categories": [
"quant-ph"
],
"title": "Quantum Mechanical Square Root Speedup in a Structured Search Problem",
"url": "https://arxiv.org/abs/quant-ph/9711035"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4e37583f-b4e6-457e-83a4-05a507f8e7d7",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}