Is partial quantum search of a database any easier?
| dc.creator | Grover, Lov K. | |
| dc.creator | Radhakrishnan, Jaikumar | |
| dc.date | 2004-07-15 | |
| dc.date | 2005-02-07 | |
| dc.date.accessioned | 2026-07-07T06:10:18Z | |
| dc.date.available | 2026-07-07T06:10:18Z | |
| dc.description | In this paper, we consider the partial database search problem where given a database on N items, we are required to determine the first k bits of an address x such that f(x)=1. We derive an algorithm and a lower bound for this problem in the quantum circuits model. Let q(k,N) be the minimum number of queries needed to find the first k bits of the required address x. We show that there exist constants c_k and d_k such that (pi/4) (1 - d_k/sqrt{K}) sqrt{N} <= q(k,n) <= (pi/4) (1 - c_k/sqrt{K}) sqrt{N}, where K=2^k. Thus, it is always easier to determine a few bits of the target address than to find the entire address, but as k becomes large this advantage reduces rapidly. | |
| dc.description | 15 pages, 4 figures | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0407122 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0407122 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/92223 | |
| dc.subject | Quantum Physics | |
| dc.title | Is partial quantum search of a database any easier? | |
| dc.type | text |