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

DOI10.1007/978-3-642-22006-7_5MaRDI QIDQ3012791zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• New bounds on classical and quantum one-way communication complexity
• Lower Bounds for Quantum Communication Complexity
• The Power of One Clean Qubit in Communication Complexity
• Lower bounds for one-way probabilistic communication complexity
• A new exponential separation between quantum and classical one-way communication complexity
• scientific article; zbMATH DE number 1759400
• A Lower Bound on Entanglement-Assisted Quantum Communication Complexity
• Exponential separations for one-way quantum communication complexity, with applications to cryptography
• Exponential Separation of Quantum and Classical One-Way Communication Complexity
• Exponential separation of quantum and classical one-way communication complexity

Cites work

• Communication Complexity
• Data Streams: Algorithms and Applications
• Dense quantum coding and quantum finite automata
• Depth through breadth, or why should we attend talks in other areas?
• Exponential separation of quantum and classical communication complexity
• Exponential separation of quantum and classical one-way communication complexity
• Exponential separations for one-way quantum communication complexity, with applications to cryptography
• scientific article; zbMATH DE number 5485519 (Why is no real title available?)
• scientific article; zbMATH DE number 5485520 (Why is no real title available?)
• scientific article; zbMATH DE number 2038718 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 5485573 (Why is no real title available?)
• Limitations of Quantum Advice and One-Way Communication
• Lower Bounds for Quantum Communication Complexity
• Lower bounds in communication complexity based on factorization norms
• New bounds on classical and quantum one-way communication complexity
• On the distributional complexity of disjointness
• Quantum and classical message protect identification via quantum channels
• Quantum communication complexity of symmetric predicates
• Quantum one-way communication can be exponentially stronger than classical communication
• Quantum search of spatial regions
• Queries revisited.
• The learnability of quantum states
• The Probabilistic Communication Complexity of Set Intersection

Cited in

(9)

• New bounds on classical and quantum one-way communication complexity
• Dense quantum coding and a lower bound for 1-way quantum automata
• On quantum and probabilistic communication: Las Vegas and one-way protocols
• Sample complexity bounds on differentially private learning via communication complexity
• Boolean nested canalizing functions: a comprehensive analysis
• One-Way Communication Complexity and the Nečiporuk Lower Bound on Formula Size
• Unbounded-Error One-Way Classical and Quantum Communication Complexity
• The Power of One Clean Qubit in Communication Complexity
• On the power of quantum distributed proofs

This page was built for publication: On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity

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