Lower Bounds for Quantum Communication Complexity
From MaRDI portal
Abstract: We prove new lower bounds for bounded error quantum communication complexity. Our methods are based on the Fourier transform of the considered functions. First we generalize a method for proving classical communication complexity lower bounds developed by Raz to the quantum case. Applying this method we give an exponential separation between bounded error quantum communication complexity and nondeterministic quantum communication complexity. We develop several other lower bound methods based on the Fourier transform, notably showing that sqrt{�ar{s}(f)/log n}, for the average sensitivity �ar{s}(f) of a function f, yields a lower bound on the bounded error quantum communication complexity of f(x AND y XOR z), where x is a Boolean word held by Alice and y,z are Boolean words held by Bob. We then prove the first large lower bounds on the bounded error quantum communication complexity of functions, for which a polynomial quantum speedup is possible. For all the functions we investigate, the only previously applied general lower bound method based on discrepancy yields bounds that are O(log n).
Recommendations
Cited in
(37)- The landscape of communication complexity classes
- Fourier analysis for probabilistic communication complexity
- The hardest halfspace
- Upper bounds on communication in terms of approximate rank
- Lower bounds on the deterministic and quantum communication complexity of Hamming-distance problems
- Lower bounds for quantum oblivious transfer
- Hellinger volume and number-on-the-forehead communication complexity
- Fooling one-sided quantum protocols
- On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
- The pattern matrix method
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- Composition theorems in communication complexity
- Quantum multiparty communication complexity and circuit lower bounds
- scientific article; zbMATH DE number 5568623 (Why is no real title available?)
- Hadamard tensors and lower bounds on multiparty communication complexity
- Quantum weakly nondeterministic communication complexity
- scientific article; zbMATH DE number 1775389 (Why is no real title available?)
- Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
- scientific article; zbMATH DE number 2086394 (Why is no real title available?)
- Limits on alternation trading proofs for time-space lower bounds
- Approximate degree and the complexity of depth three circuits
- A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
- A lifting theorem with applications to symmetric functions
- Conditional disclosure of secrets: amplification, closure, amortization, lower-bounds, and separations
- The large-error approximate degree of \(\mathrm{AC}^0\)
- Efficient quantum protocols for XOR functions
- Unbounded-Error Classical and Quantum Communication Complexity
- Quantum Multiparty Communication Complexity and Circuit Lower Bounds
- A Lower Bound on Entanglement-Assisted Quantum Communication Complexity
- Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Rectangles are nonnegative juntas
- Lower bounds in communication complexity based on factorization norms
- Unbounded-error quantum query complexity
- Upper bounds on communication in terms of approximate rank
- A hierarchy of constant communication complexity
- Separation of the factorization norm and randomized communication complexity
This page was built for publication: Lower Bounds for Quantum Communication Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5454242)
