Quantum communication complexity of symmetric predicates

Abstract

We completely (that is, up to a logarithmic factor) characterize the bounded-error quantum communication complexity of every predicate $f(x,y)$ depending only on $|x\cap y|$ ($x,y\subseteq [n]$). Namely, for a predicate $D$ on $\{0,1,...,n\}$ let $\ell_0(D)\df \max\{\ell : 1\leq\ell\leq n/2\land D(\ell)\not\equiv D(\ell-1)\}$ and $\ell_1(D)\df \max\{n-\ell : n/2\leq\ell < n\land D(\ell)\not\equiv D(\ell+1)\}$. Then the bounded-error quantum communication complexity of $f_D(x,y)=D(|x\cap y|)$ is equal (again, up to a logarithmic factor) to $\sqrt{n{\ell }_0(D)}+{\ell }_1(D)$. In particular, the complexity of the set disjointness predicate is $\Omega (\sqrt{n})$. This result holds both in the model with prior entanglement and without it.

20 pages

References in corpus (2)

• Improved Quantum Communication Complexity Bounds for Disjointness and Equality
• Lower bounds for quantum communication complexity

Cited by in corpus (56)

• Non-locality and Communication Complexity
• A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
• Multiparty Communication Complexity of Disjointness
• The Communication Complexity of the Hamming Distance Problem
• Communication Lower Bounds Using Dual Polynomials
• Interaction in Quantum Communication
• Lower bounds for quantum communication complexity
• Quantum Computing: Lecture Notes
• Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
• Exponential Separation of Quantum and Classical Online Space Complexity
• On quantum and approximate privacy
• Limits on Efficient Computation in the Physical World
• Multiplayer XOR games and quantum communication complexity with clique-wise entanglement
• Generalizations of the distributed Deutsch-Jozsa promise problem
• Unbounded-error One-way Classical and Quantum Communication Complexity
• Composition theorems in communication complexity
• The Garden-Hose Model
• Separating NOF communication complexity classes RP and NP
• Efficient unitary designs and pseudorandom unitaries from permutations
• Efficient Unitary T-designs from Random Sums
• Strengths and Weaknesses of Quantum Fingerprinting
• Communication Complexities of XOR functions
• Robust Bell inequalities from communication complexity
• Quantum Proofs for Classical Theorems
• Quantum Distributed Complexity of Set Disjointness on a Line
• A lower bound for bounded round quantum communication complexity of set disjointness
• Unbounded Error Quantum Query Complexity
• On Arthur Merlin Games in Communication Complexity
• Fooling One-Sided Quantum Protocols
• A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions
• Spectral Norm of Symmetric Functions
• On the Spectral Properties of Symmetric Functions
• Linear gate bounds against natural functions for position-verification
• Bounds on oblivious multiparty quantum communication complexity
• Communication complexity of promise problems and their applications to finite automata
• Quantum advantage in temporally flat measurement-based quantum computation
• Classical lower bounds from quantum upper bounds
• Quantum Proofs of Proximity
• Quantum Communication-Query Tradeoffs
• Quantum Chebyshev's Inequality and Applications
• Correlation in Hard Distributions in Communication Complexity
• Can Quantum Communication Speed Up Distributed Computation?
• The layer complexity of Arthur-Merlin-like communication
• An approximation algorithm for approximation rank
• Complexity of Eccentricities and All-Pairs Shortest Paths in the Quantum CONGEST Model
• Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
• Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information
• A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
• Sensitivity, Affine Transforms and Quantum Communication Complexity
• Quantum Communication Complexity of Distributed Set Joins
• Quantum Search of Spatial Regions
• A Separation of NP and coNP in Multiparty Communication Complexity
• Better Gap-Hamming Lower Bounds via Better Round Elimination
• New bounds on the classical and quantum communication complexity of some graph properties
• Hellinger volume and number-on-the-forehead communication complexity
• On the Degree of Boolean Functions as Polynomials over ${\mathbb{Z}}_m$