| Is partial quantum search of a database any easier? (2004) | |||||||||
Abstract | |||||||||
| 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} . Comment: 15 pages, 4 figures | |||||||||
Publication details | |||||||||
| |||||||||