Abstract
For any function f: X × Y → Z, we prove that Q^*cc(f) · Q^OIP(f) · (log Q^OIP(f) + log |Z|) ≥ Ω(log |X|). Here, Q^*cc(f) denotes the bounded-error communication complexity of f using an entanglement-assisted two-way qubit channel, and Q^OIP(f) denotes the number of quantum queries needed to learn x with high probability given oracle access to the function f_x(y) def= f(x, y). We show that this tradeoff is close to the best possible. We also give a generalization of this tradeoff for distributional query complexity. As an application, we prove an optimal Ω(log q) lower bound on the Q^*cc complexity of determining whether x + y is a perfect square, where Alice holds x ∈ F_q, Bob holds y ∈ F_q, and F_q is a finite field of odd characteristic. As another application, we give a new, simpler proof that searching an ordered size-N database requires Ω(log N / log log N) quantum queries. (It was already known that Θ(log N) queries are required.)