Quantum Communication-Query Tradeoffs

Abstract

For any function $f:X\times Y\to Z$, we prove that $Q^{\ast \text{cc}}(f)\cdot Q^{\text{OIP}}(f)\cdot (\log Q^{\text{OIP}}(f)+\log |Z|)\ge \Omega (\log |X|)$. Here, $Q^{\ast \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^{\ast \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.)

20 pages, 3 figures. Strengthened the results in Section 5, fixed small mistakes, improved presentation

References in corpus (2)

• Improved Bounds on Quantum Learning Algorithms
• Improved quantum algorithms for the ordered search problem via semidefinite programming

Cited by in corpus (1)

• Classical lower bounds from quantum upper bounds