dorsal/arxiv
View SchemaQuantum algorithms for subset finding
| Authors | Andrew M. Childs, Jason M. Eisenberg |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0311038 |
| URL | https://arxiv.org/abs/quant-ph/0311038 |
| DOI | 10.26421/QIC5.7 |
| Journal | Quantum Information and Computation 5, 593 (2005) |
Abstract
Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds.
{
"annotation_id": "91b66f3e-2b50-44d8-be71-54781b73b4e0",
"date_created": "2026-03-02T18:02:03.635000Z",
"date_modified": "2026-03-02T18:02:03.635000Z",
"file_hash": "b91cb539b63c5063c088073d64047b2660334579325e7e4cb50d7c92961c736e",
"private": false,
"record": {
"abstract": "Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for\nelement distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for\nfinding L equal numbers. We point out that this algorithm actually solves a\nmuch more general problem, the problem of finding a subset of size L that\nsatisfies any given property. We review the algorithm and give a considerably\nsimplified analysis of its query complexity. We present several applications,\nincluding two algorithms for the problem of finding an L-clique in an N-vertex\ngraph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other\nuses \\tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L \u003c= 5. The\nlatter algorithm generalizes a recent result of Magniez, Santha, and Szegedy,\nwho considered the case L=3 (finding a triangle). We also pose two open\nproblems regarding continuous time quantum walk and lower bounds.",
"arxiv_id": "quant-ph/0311038",
"authors": [
"Andrew M. Childs",
"Jason M. Eisenberg"
],
"categories": [
"quant-ph"
],
"doi": "10.26421/QIC5.7",
"journal_ref": "Quantum Information and Computation 5, 593 (2005)",
"title": "Quantum algorithms for subset finding",
"url": "https://arxiv.org/abs/quant-ph/0311038"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c232a32d-7c38-45b7-9a24-f766efddf4ff",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}