dorsal/arxiv
View SchemaQuantum search for multiple items using parallel queries
| Authors | Lov K. Grover, Jaikumar Radhakrishnan |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0407217 |
| URL | https://arxiv.org/abs/quant-ph/0407217 |
Abstract
In the quantum database search problem we are required to search for an item in a database. In this paper, we consider a generalization of this problem, where we are provided d identical copes of a database each with N items which we can query in parallel. Then, given k items, we are required to determine the locations where these items are stored. We show that any quantum algorithm for this task must perform Omega(sqrt{Nk/d min{d,k}}) parallel queries. We also design an algorithm whose performance comes within a factor O(log d) of this lower bound.
{
"annotation_id": "b2b3ba5f-fe6b-4ea8-adab-861b3f7aee51",
"date_created": "2026-03-02T18:02:10.185000Z",
"date_modified": "2026-03-02T18:02:10.185000Z",
"file_hash": "21e16fce2649a1989c9d47707e095cdac415b8a4d96b9d8fc5545dbb8e89ae23",
"private": false,
"record": {
"abstract": "In the quantum database search problem we are required to search for an item\nin a database. In this paper, we consider a generalization of this problem,\nwhere we are provided d identical copes of a database each with N items which\nwe can query in parallel. Then, given k items, we are required to determine the\nlocations where these items are stored. We show that any quantum algorithm for\nthis task must perform Omega(sqrt{Nk/d min{d,k}}) parallel queries. We also\ndesign an algorithm whose performance comes within a factor O(log d) of this\nlower bound.",
"arxiv_id": "quant-ph/0407217",
"authors": [
"Lov K. Grover",
"Jaikumar Radhakrishnan"
],
"categories": [
"quant-ph"
],
"title": "Quantum search for multiple items using parallel queries",
"url": "https://arxiv.org/abs/quant-ph/0407217"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "5e80310c-68b3-47d0-9463-70383a60fce8",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}