dorsal/arxiv
View SchemaA Quantum Search Algorithm for a Specified Number of Targets
| Authors | Mark A. Rubin |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0104082 |
| URL | https://arxiv.org/abs/quant-ph/0104082 |
Abstract
The quantum search algorithm of Chen and Diao, which finds with certainty a single target item in an unsorted database, is modified so as to be capable of searching for an arbitrary specified number of target items. If the number of targets, nu_0, is a power of four, the new algorithm will with certainty find one of the targets in a database of n items using (1/2)(3(N/nu_0)^{log_base_4(3)}-1) \approx (1/2)(3(N/nu_0)^{0.7925}-1) oracle calls, where N is the smallest power of four greater than or equal to n. If nu_0 is not a power of four, the algorithm will, with a probability of at least one-half, find one of the targets using no more than (1/2)(9(N/nu)^{log_base_4(3)}-1) calls, where nu is the smallest power of four greater than or equal to nu_0.
{
"annotation_id": "6885dc3e-c06f-4984-bbc8-2cbf0c5e92d6",
"date_created": "2026-03-02T18:01:42.545000Z",
"date_modified": "2026-03-02T18:01:42.545000Z",
"file_hash": "afafd455dfd2ce299f17bd4de98a017ca452bac590840a8484b96639c5aa0b02",
"private": false,
"record": {
"abstract": "The quantum search algorithm of Chen and Diao, which finds with certainty a\nsingle target item in an unsorted database, is modified so as to be capable of\nsearching for an arbitrary specified number of target items. If the number of\ntargets, nu_0, is a power of four, the new algorithm will with certainty find\none of the targets in a database of n items using\n(1/2)(3(N/nu_0)^{log_base_4(3)}-1) \\approx (1/2)(3(N/nu_0)^{0.7925}-1) oracle\ncalls, where N is the smallest power of four greater than or equal to n. If\nnu_0 is not a power of four, the algorithm will, with a probability of at least\none-half, find one of the targets using no more than\n(1/2)(9(N/nu)^{log_base_4(3)}-1) calls, where nu is the smallest power of four\ngreater than or equal to nu_0.",
"arxiv_id": "quant-ph/0104082",
"authors": [
"Mark A. Rubin"
],
"categories": [
"quant-ph"
],
"title": "A Quantum Search Algorithm for a Specified Number of Targets",
"url": "https://arxiv.org/abs/quant-ph/0104082"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "82bc17df-4886-4f84-935e-604217ac569b",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}