Improved Quantum Communication Complexity Bounds for Disjointness and Equality
arXiv:quant-ph/0109068 · doi:10.1007/3-540-45841-7_24
Abstract
We prove new bounds on the quantum communication complexity of the disjointness and equality problems. For the case of exact and non-deterministic protocols we show that these complexities are all equal to n+1, the previous best lower bound being n/2. We show this by improving a general bound for non-deterministic protocols of de Wolf. We also give an O(sqrt{n}c^{log^* n})-qubit bounded-error protocol for disjointness, modifying and improving the earlier O(sqrt{n}log n) protocol of Buhrman, Cleve, and Wigderson, and prove an Omega(sqrt{n}) lower bound for a large class of protocols that includes the BCW-protocol as well as our new protocol.
11 pages LaTeX
References in corpus (2)
Cited by in corpus (21)
- Quantum communication complexity of symmetric predicates
- Quantum Network Coding
- Quantum Search on Bounded-Error Inputs
- A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
- Lower bounds for quantum communication complexity
- Exponential Separation of Quantum and Classical Online Space Complexity
- Limits on Efficient Computation in the Physical World
- Extended formulations, non-negative factorizations and randomized communication protocols
- Quantum Advantage for the LOCAL Model in Distributed Computing
- Classical and quantum partition bound and detector inefficiency
- A lower bound for bounded round quantum communication complexity of set disjointness
- Unbounded Error Quantum Query Complexity
- Fooling One-Sided Quantum Protocols
- Practical Quantum Appointment Scheduling
- Quantum communication complexity of block-composed functions
- Communication complexity of promise problems and their applications to finite automata
- Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
- Quantum Weakly Nondeterministic Communication Complexity
- Quantum Search of Spatial Regions
- Capacity Approaching Coding for Low Noise Interactive Quantum Communication, Part I: Large Alphabets
- Quantum Zero-Error Algorithms Cannot be Composed