Exponential separation of quantum and classical one-way communication complexity

DOI10.1145/1007352.1007379MaRDI QIDQ3580963zbMATH OpenOpenAlexWikidataFDO

Authors Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis

Publication date 15 August 2010

Published in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1007352.1007379

Mathematics Subject Classification ID

Network protocols (68M12) Theory of computing (68Qxx) Quantum computation (81P68)

Recommendations

• Exponential Separation of Quantum and Classical One-Way Communication Complexity
• Exponential separation of quantum and classical communication complexity
• A new exponential separation between quantum and classical one-way communication complexity
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• Exponential separations for one-way quantum communication complexity, with applications to cryptography

Cited in

(31)

• Two party non-local games
• Quantum versus randomized communication complexity, with efficient players
• Quantum pseudo-telepathy
• Two-player conflicting interest Bayesian games and Bell nonlocality
• Nonlocal correlations and noise in different settings of a two-player game
• Quantum one-way versus classical two-way communication in XOR games
• Experimental multipartner quantum communication complexity employing just one qubit
• Exponential separation of quantum and classical communication complexity
• Bounded-error quantum state identification and exponential separations in communication complexity
• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• A new exponential separation between quantum and classical one-way 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 for One-Way Quantum Communication Complexity, with Applications to Cryptography
• Exponential separation of quantum communication and classical information
• scientific article; zbMATH DE number 7204275 (Why is no real title available?)
• Bounded-error quantum state identification and exponential separations in communication complexity
• On approximating matrix norms in data streams
• Quantum one-way communication can be exponentially stronger than classical communication
• Optimal bounds for parity-oblivious random access codes
• scientific article; zbMATH DE number 7651028 (Why is no real title available?)
• Exponential Separation of Information and Communication for Boolean Functions
• Non-uniformity and quantum advice in the quantum random oracle model
• The Power of One Clean Qubit in Communication Complexity
• Streaming Euclidean MST to a constant factor
• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
• Quantum and classical communication complexity of permutation-invariant functions
• Classical vs quantum advice and proofs under classically-accessible oracle
• A qubit, a coin, and an advice string walk into a relational problem
• Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
• Quantum versus randomized communication complexity, with efficient players

This page was built for publication: Exponential separation of 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 Q3580963)