dorsal/arxiv
View SchemaIs Quantum Search Practical?
| Authors | George F. Viamontes, Igor L. Markov, John P. Hayes |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0405001 |
| URL | https://arxiv.org/abs/quant-ph/0405001 |
Abstract
Quantum algorithms and circuits can, in principle, outperform the best non-quantum (classical) techniques for some hard computational problems. However, this does not necessarily lead to useful applications. To gauge the practical significance of a quantum algorithm, one must weigh it against the best conventional techniques applied to useful instances of the same problem. Grover's quantum search algorithm is one of the most widely studied. We identify requirements for Grover's algorithm to be useful in practice: (1) a search application S where classical methods do not provide sufficient scalability; (2) an instantiation of Grover's algorithm Q(S) for S that has a smaller asymptotic worst-case runtime than any classical algorithm C(S) for S; (3) Q(S) with smaller actual runtime for practical instances of S than that of any C(S). We show that several commonly-suggested applications fail to satisfy these requirements, and outline directions for future work on quantum search.
{
"annotation_id": "ec90d6c7-d434-4e42-97f3-ce19e5f6be16",
"date_created": "2026-03-02T18:02:06.920000Z",
"date_modified": "2026-03-02T18:02:06.920000Z",
"file_hash": "e876ad9b3dc3ea3f4fd05d0a8b8887304c309aeb5514d256575e65b1bb4a88cd",
"private": false,
"record": {
"abstract": "Quantum algorithms and circuits can, in principle, outperform the best\nnon-quantum (classical) techniques for some hard computational problems.\nHowever, this does not necessarily lead to useful applications. To gauge the\npractical significance of a quantum algorithm, one must weigh it against the\nbest conventional techniques applied to useful instances of the same problem.\nGrover\u0027s quantum search algorithm is one of the most widely studied.\n We identify requirements for Grover\u0027s algorithm to be useful in practice: (1)\na search application S where classical methods do not provide sufficient\nscalability; (2) an instantiation of Grover\u0027s algorithm Q(S) for S that has a\nsmaller asymptotic worst-case runtime than any classical algorithm C(S) for S;\n(3) Q(S) with smaller actual runtime for practical instances of S than that of\nany C(S).\n We show that several commonly-suggested applications fail to satisfy these\nrequirements, and outline directions for future work on quantum search.",
"arxiv_id": "quant-ph/0405001",
"authors": [
"George F. Viamontes",
"Igor L. Markov",
"John P. Hayes"
],
"categories": [
"quant-ph"
],
"title": "Is Quantum Search Practical?",
"url": "https://arxiv.org/abs/quant-ph/0405001"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "0275a7f8-aa9d-4f3e-93f9-035f705bf259",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}