A new exponential separation between quantum and classical one-way communication complexity

MaRDI QIDQ3104210zbMATH OpenFDO

Authors Ashley Montanaro

Publication date 19 December 2011

Full work available at URL https://arxiv.org/abs/1007.3587

zbMATH Keywords

Fourier analysisquantum communication complexitysubgroup membership

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Recommendations

• Exponential separation of quantum and classical one-way communication complexity
• Exponential Separation of Quantum and Classical One-Way Communication Complexity
• Exponential separation of quantum and classical communication complexity
• Quantum one-way communication can be exponentially stronger than classical communication
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography

Cited in

(15)

• Experimental multipartner quantum communication complexity employing just one qubit
• Exponential separation of quantum and classical communication complexity
• On the Power of Lower Bound Methods for One-Way 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
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• Exponential separation of quantum communication and classical information
• The one-way communication complexity of subgroup membership
• Quantum one-way communication can be exponentially stronger than classical communication
• scientific article; zbMATH DE number 7651028 (Why is no real title available?)
• The Power of One Clean Qubit in Communication Complexity
• Quantum and classical communication complexity of permutation-invariant functions
• Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
• The asymptotic induced matching number of hypergraphs: balanced binary strings

This page was built for publication: A new exponential separation between quantum and classical one-way communication complexity

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