Quantum communication complexity of symmetric predicates

DOI10.1070/IM2003V067N01ABEH000422zbMATH Open1088.68052arXivquant-ph/0204025OpenAlexW2053590396MaRDI QIDQ4674584FDOQ4674584

Authors: Alexander Razborov 

Publication date: 17 May 2005

Published in: Izvestiya: Mathematics (Search for Journal in Brave)

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 $|xcapy|$ ($x,ysubseteq[n]$). Namely, for a predicate $D$ on $0,1,\mathrm{...},n$ let $el{l}_0(D)dfmaxell:1leqellleqn/2landD(ell)otequivD(ell-1)$ and $el{l}_1(D)dfmaxn-ell:n/2leqell<nlandD(ell)otequivD(ell+1)$. Then the bounded-error quantum communication complexity of $f_D(x,y)=D(|xcapy|)$ is equal (again, up to a logarithmic factor) to $sqrtnel{l}_0(D)+el{l}_1(D)$. In particular, the complexity of the set disjointness predicate is $Omega(sqrtn)$. This result holds both in the model with prior entanglement and without it.

Full work available at URL: https://arxiv.org/abs/quant-ph/0204025

Recommendations

• scientific article; zbMATH DE number 2086394
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• Quantum communication and complexity.
• The Quantum Communication Complexity of Sampling
• Interaction in quantum communication and the complexity of \textsc{Set Disjointness}

zbMATH Keywords

set disjointness predicate

Mathematics Subject Classification ID

Quantum computation (81P68)

Cited In (32)

• The complexity of quantum disjointness
• The hardest halfspace
• Algorithmic Polynomials
• Generalizations of the distributed Deutsch–Jozsa promise problem
• Kolmogorov complexity and combinatorial methods in communication complexity
• Title not available (Why is that?)
• The communication complexity of the Hamming distance problem
• Polynomial degree vs. quantum query complexity
• Bounds on oblivious multiparty quantum communication complexity
• Unbounded-error quantum query complexity
• Exponential separation of quantum and classical online space complexity
• Rectangles are nonnegative juntas
• Quantum communication and complexity.
• Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs
• The unbounded-error communication complexity of symmetric functions
• Hellinger volume and number-on-the-forehead communication complexity
• Upper bounds on communication in terms of approximate rank
• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• Title not available (Why is that?)
• Sensitivity, affine transforms and quantum communication complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• The NOF multiparty communication complexity of composed functions
• Upper bounds on communication in terms of approximate rank
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• Lower bounds in communication complexity based on factorization norms
• Approximate Degree in Classical and Quantum Computing
• A Lifting Theorem with Applications to Symmetric Functions
• The Quantum Communication Complexity of Sampling
• Title not available (Why is that?)
• The multiparty communication complexity of set disjointness
• Communication complexities of symmetric XOR functions

This page was built for publication: Quantum communication complexity of symmetric predicates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4674584)