Is partial quantum search of a database any easier

Abstract

We consider the partial database search problem where given a quantum database {0, 1}ⁿ→^ƒ {0, 1} with the condition that ƒ(x) = 1 for a unique x ∈ {0, 1}ⁿ, we are required to determine only the first k bits of the address x. We derive an algorithm and a lower bound for this problem. Let q(k, n) be the minimum number of queries needed to find the first k bits of the required address x with certainty (or with very high probability, say 1-O(N-¼). We show that there exist constants ck (corresponding to the algorithm) and d_k (corresponding to the lower bound) such that π/4(1-d_k/√K) √N ≤ q(k, n) ≤ π/4 (1-c_k/√K) √N, where K = 2^k and N = 2ⁿ. Our algorithm returns the correct answer with probability 1- O(1/√N), and can be easily modified to give the correct answer with certainty. The lower bound for algorithms that return the correct answer with certainty is proved by reducing the usual database search problem to this partial search problem, and invoking Zalka's lower bound showing that Grovers algorithm is optimal for the usual database search problem. We then derive a lower bound that is applicable for database search algorithms that err with small probability, and use it to show that our lower bound also applies to partial search algorithms that return the correct answer with probability at least 1 - O(N-¼). Thus, it is easier to determine some k bits of the target address than to find the entire address, but as k becomes large this advantage reduces rapidly.