On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity

DOI10.1007/978-3-642-22006-7_5zbMath1332.68054OpenAlexW1844039599MaRDI QIDQ3012791

Shengyu Zhang

Publication date: 6 July 2011

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

Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_5

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Sample Complexity Bounds on Differentially Private Learning via Communication Complexity, Boolean nested canalizing functions: a comprehensive analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New bounds on classical and quantum one-way communication complexity
• On the distributional complexity of disjointness
• Queries revisited.
• Exponential separation of quantum and classical communication complexity
• Limitations of Quantum Advice and One-Way Communication
• Dense quantum coding and quantum finite automata
• The learnability of quantum states
• Data Streams: Algorithms and Applications
• Exponential separation of quantum and classical one-way communication complexity
• Depth through breadth, or why should we attend talks in other areas?
• The Probabilistic Communication Complexity of Set Intersection
• Quantum communication complexity of symmetric predicates
• Communication Complexity
• Quantum one-way communication can be exponentially stronger than classical communication
• Lower Bounds for Quantum Communication Complexity
• Lower bounds in communication complexity based on factorization norms