dorsal/arxiv
View SchemaSimple Algorithm for Partial Quantum Search
| Authors | Vladimir E. Korepin, Lov K. Grover |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0504157 |
| URL | https://arxiv.org/abs/quant-ph/0504157 |
| DOI | 10.1007/s11128-005-0004-z |
| Journal | Quantum Information Processing, vol. 5, number 1, page 5-10, 2006 |
Abstract
Quite often in database search, we only need to extract portion of the information about the satisfying item. Recently Radhakrishnan & Grover [RG] considered this problem in the following form: the database of $N$ items was divided into $K$ equally sized blocks. The algorithm has just to find the block containing the item of interest. The queries are exactly the same as in the standard database search problem. [RG] invented a quantum algorithm for this problem of partial search that took about $0.33\sqrt{N/K}$ fewer iterations than the quantum search algorithm. They also proved that the best any quantum algorithm could do would be to save $0.78 \sqrt(N/K)$ iterations. The main limitation of the algorithm was that it involved complicated analysis as a result of which it has been inaccessible to most of the community. This paper gives a simple analysis of the algorithm. This analysis is based on three elementary observations about quantum search, does not require a single equation and takes less than 2 pages.
{
"annotation_id": "b6358000-084d-405a-9856-0c5dcb8b07f6",
"date_created": "2026-03-02T18:02:16.794000Z",
"date_modified": "2026-03-02T18:02:16.794000Z",
"file_hash": "e67e8da86df29649d4bb3817bb17e5cc5a56f6d2992fe4633cbbfc87c7d95034",
"private": false,
"record": {
"abstract": "Quite often in database search, we only need to extract portion of the\ninformation about the satisfying item. Recently Radhakrishnan \u0026 Grover [RG]\nconsidered this problem in the following form: the database of $N$ items was\ndivided into $K$ equally sized blocks. The algorithm has just to find the block\ncontaining the item of interest. The queries are exactly the same as in the\nstandard database search problem. [RG] invented a quantum algorithm for this\nproblem of partial search that took about $0.33\\sqrt{N/K}$ fewer iterations\nthan the quantum search algorithm. They also proved that the best any quantum\nalgorithm could do would be to save $0.78 \\sqrt(N/K)$ iterations. The main\nlimitation of the algorithm was that it involved complicated analysis as a\nresult of which it has been inaccessible to most of the community. This paper\ngives a simple analysis of the algorithm. This analysis is based on three\nelementary observations about quantum search, does not require a single\nequation and takes less than 2 pages.",
"arxiv_id": "quant-ph/0504157",
"authors": [
"Vladimir E. Korepin",
"Lov K. Grover"
],
"categories": [
"quant-ph"
],
"doi": "10.1007/s11128-005-0004-z",
"journal_ref": "Quantum Information Processing, vol. 5, number 1, page 5-10, 2006",
"title": "Simple Algorithm for Partial Quantum Search",
"url": "https://arxiv.org/abs/quant-ph/0504157"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "414be374-af6e-4733-bf49-70480a3c660a",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}