Quantum Communication-Query Tradeoffs

For any function $f \colon 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 \mathbb{F}_q$, Bob holds $y \in \mathbb{F}_q$, and $\mathbb{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.)

Quantum algorithms are algorithms that exploit quantum effects, requiring special hardware that, broadly speaking, nobody has managed to build yet. In this paper, we study quantum algorithms for two types of problems. In the first type of problem, Alice has some data $x$, Bob has some data $y$, and the two of them would like to figure out whether the pair $(x, y)$ has some property $P$ using as little communication as possible. For example, maybe $x$ and $y$ are numbers between 1 and a million, and $P$ is the property that $x > y$. The second type of problem is similar to the game 20 Questions. Alice chooses $x$. If Bob specifies $y$, then Alice tells him whether $(x, y)$ has property $P$. Bob's goal is to learn $x$ by making as few queries as possible. We prove that if the same property $P$ is used to formulate each problem, then the two problems can't both have extremely efficient quantum algorithms.