Quantum lower bounds for the Goldreich-Levin problem

At the heart of the Goldreich-Levin theorem is the problem of determining an n-bit string a by making queries to two oracles, referred to as IP (inner product) and EQ (equivalence). The IP oracle, on input x, returns a bit that is biased towards a (.) x (the modulo two inner product of a with x) in the following sense. For a random x, the probability that IP(x) = a (.) x is at least 1/2(1 + epsilon). The EQ oracle, on input x, returns a bit specifying whether or not x = a. It has been shown that a quantum algorithm can solve this problem with O(1/epsilon) IP and EQ queries, whereas any classical algorithm requires Omega(n/epsilon(2)) such queries. Also, the quantum algorithm requires only O(n/epsilon) auxiliary one- and two-qubit gates in addition to its queries. We show that the above quantum algorithm is optimal in terms of both EQ and IP queries. Specifically, Omega(1/epsilon) EQ queries are necessary, and Omega(1/epsilon) IP queries are necessary if the number of EQ queries is o(root 2(n)). (c) 2005 Elsevier B.V. All rights reserved.