  For any function $f: X \times Y \to Z$, we prove that $Q^{*\text{cc}}(f)
\cdot Q^{\text{OIP}}(f) \cdot (\log Q^{\text{OIP}}(f) + \log |Z|) \geq
\Omega(\log |X|)$. Here, $Q^{*\text{cc}}(f)$ denotes the bounded-error
communication complexity of $f$ using an entanglement-assisted two-way qubit
channel, and $Q^{\text{OIP}}(f)$ denotes the number of quantum queries needed
to learn $x$ with high probability given oracle access to the function $f_x(y)
\stackrel{\text{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 $\Omega(\log q)$ lower bound on the
$Q^{*\text{cc}}$ complexity of determining whether $x + y$ is a perfect square,
where Alice holds $x \in \mathbf{F}_q$, Bob holds $y \in \mathbf{F}_q$, and
$\mathbf{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 $\Omega(\log N / \log \log N)$ quantum queries. (It was already known
that $\Theta(\log N)$ queries are required.)
