Simple Algorithm for Partial Quantum Search
| dc.creator | Korepin, Vladimir E. | |
| dc.creator | Grover, Lov K. | |
| dc.date | 2005-04-20 | |
| dc.date | 2005-04-21 | |
| dc.date.accessioned | 2026-07-07T06:27:26Z | |
| dc.date.available | 2026-07-07T06:27:26Z | |
| dc.description | 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. | |
| dc.description | 3 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0504157 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0504157 | |
| dc.identifier | Quantum Information Processing, vol. 5, number 1, page 5-10, 2006 | |
| dc.identifier | doi:10.1007/s11128-005-0004-z | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/97416 | |
| dc.subject | Quantum Physics | |
| dc.title | Simple Algorithm for Partial Quantum Search | |
| dc.type | text |