A Lower Bound on Entanglement-Assisted Quantum Communication Complexity

DOI10.1007/978-3-540-73420-8_13MaRDI QIDQ5428803zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ashley Montanaro, Andreas Winter

Publication date 28 November 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Abstract: We prove a general lower bound on the bounded-error entanglement-assisted quantum communication complexity of Boolean functions. The bound is based on the concept that any classical or quantum protocol to evaluate a function on distributed inputs can be turned into a quantum communication protocol. As an application of this bound, we give a very simple proof of the statement that almost all Boolean functions on n+n bits have linear communication complexity, even in the presence of unlimited entanglement.

Recommendations

• Quantum entanglement and the communication complexity of the inner product function
• scientific article; zbMATH DE number 1406113
• Lower Bounds for Quantum Communication Complexity
• Lower bounds in communication complexity based on factorization norms
• Quantum communication and complexity.

Cited in

(8)

• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• Quantum entanglement and the communication complexity of the inner product function
• scientific article; zbMATH DE number 1406113 (Why is no real title available?)
• Universality of EPR pairs in entanglement-assisted communication complexity, and the communication cost of state conversion
• Lower Bounds for Quantum Communication Complexity
• Lower bounds in communication complexity based on factorization norms
• More assistance of entanglement, less rounds of classical communication
• Exponential quantum enhancement for distributed addition with local nonlinearity

This page was built for publication: A Lower Bound on Entanglement-Assisted Quantum Communication Complexity

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