dorsal/arxiv
View SchemaQuantum Multi-object Search Algorithm with the Availability of Partial Information
| Authors | Goong Chen, Zijian Diao |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0011019 |
| URL | https://arxiv.org/abs/quant-ph/0011019 |
| DOI | 10.1515/zna-2001-1215 |
Abstract
Consider the unstructured search of an unknown number l of items in a large unsorted database of size N. The multi-object quantum search algorithm consists of two parts. The first part of the algorithm is to generalize Grover's single-object search algorithm to the multi-object case and the second part is to solve a counting problem to determine l. In this paper, we study the multi-object quantum search algorithm (in continuous time), but in a more structured way by taking into account the availability of partial information. The modeling of available partial information is done simply by the combination of several prescribed, possibly overlapping, information sets with varying weights to signify the reliability of each set. The associated statistics is estimated and the algorithm efficiency and complexity are analyzed. Our analysis shows that the search algorithm described here may not be more efficient than the unstructured (generalized) multi-object Grover search if there is ``misplaced confidence''. However, if the information sets have a ``basic confidence'' property in the sense that each information set contains at least one search item, then a quadratic speedup holds on a much smaller data space, which further expedite the quantum search for the first item.
{
"annotation_id": "6513289e-2f89-4545-a8b9-ba261c54304c",
"date_created": "2026-03-02T18:01:42.206000Z",
"date_modified": "2026-03-02T18:01:42.206000Z",
"file_hash": "bec429bd8f080811bcf20ab38373d52a8dd9411b212fa8444daf42a3ee74d04f",
"private": false,
"record": {
"abstract": "Consider the unstructured search of an unknown number l of items in a large\nunsorted database of size N. The multi-object quantum search algorithm consists\nof two parts. The first part of the algorithm is to generalize Grover\u0027s\nsingle-object search algorithm to the multi-object case and the second part is\nto solve a counting problem to determine l.\n In this paper, we study the multi-object quantum search algorithm (in\ncontinuous time), but in a more structured way by taking into account the\navailability of partial information. The modeling of available partial\ninformation is done simply by the combination of several prescribed, possibly\noverlapping, information sets with varying weights to signify the reliability\nof each set. The associated statistics is estimated and the algorithm\nefficiency and complexity are analyzed.\n Our analysis shows that the search algorithm described here may not be more\nefficient than the unstructured (generalized) multi-object Grover search if\nthere is ``misplaced confidence\u0027\u0027. However, if the information sets have a\n``basic confidence\u0027\u0027 property in the sense that each information set contains\nat least one search item, then a quadratic speedup holds on a much smaller data\nspace, which further expedite the quantum search for the first item.",
"arxiv_id": "quant-ph/0011019",
"authors": [
"Goong Chen",
"Zijian Diao"
],
"categories": [
"quant-ph"
],
"doi": "10.1515/zna-2001-1215",
"title": "Quantum Multi-object Search Algorithm with the Availability of Partial Information",
"url": "https://arxiv.org/abs/quant-ph/0011019"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b64eea54-2125-4802-9dd0-8ae529a45745",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}