  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.
