Quantum Communication-Query Tradeoffs
arXiv:1703.07768
Abstract
For any function , we prove that . Here, denotes the bounded-error communication complexity of using an entanglement-assisted two-way qubit channel, and denotes the number of quantum queries needed to learn with high probability given oracle access to the function . 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 lower bound on the complexity of determining whether is a perfect square, where Alice holds , Bob holds , and is a finite field of odd characteristic. As another application, we give a new, simpler proof that searching an ordered size- database requires quantum queries. (It was already known that queries are required.)
arXiv comment20 pages, 3 figures. Strengthened the results in Section 5, fixed small mistakes, improved presentation
References in corpus (10)
- Strengths and Weaknesses of Quantum Computing
- Quantum Algorithms Revisited
- Substituting Quantum Entanglement for Communication
- Quantum communication complexity of symmetric predicates
- A Limit on the Speed of Quantum Computation in Determining Parity
- Improved Bounds on Quantum Learning Algorithms
- Improved quantum algorithms for the ordered search problem via semidefinite programming
- Quantum Entanglement and the Communication Complexity of the Inner Product Function
- Quantum Algorithms for Weighing Matrices and Quadratic Residues
- Quantum Search in an Ordered List via Adaptive Learning