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 . 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/ɛ) IP and EQ queries, whereas any classical algorithm requires Ω(n/ɛ2) such queries. Also, the quantum algorithm requires only O(n/ɛ) 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, Ω(1/ɛ) EQ queries are necessary, and Ω(1/ɛ) IP queries are necessary if the number of EQ queries is .