Exponential separation of quantum and classical communication complexity

DOI10.1145/301250.301343MaRDI QIDQ2819566zbMATH OpenOpenAlexFDO

Authors Ran Raz

Publication date 29 September 2016

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

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

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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 communication and classical information
• A new exponential separation between quantum and classical one-way communication complexity
• scientific article; zbMATH DE number 1775389

Cited in

(58)

• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 5953454 (Why is no real title available?)
• The complexity of quantum disjointness
• Quantum Weakly Nondeterministic Communication Complexity
• Euclidean distance matrices and separations in communication complexity theory
• Experimental multipartner quantum communication complexity employing just one qubit
• Quantum communication based on an algorithm of determining a matrix
• Small ball probability and Dvoretzky's Theorem
• Generalizations of the distributed Deutsch-Jozsa promise problem
• Noise and the Mermin-GHZ game
• Unbounded-Error Classical and Quantum Communication Complexity
• scientific article; zbMATH DE number 7651028 (Why is no real title available?)
• Parity decision tree in classical-quantum separations for certain classes of Boolean functions
• Exponential separation of quantum communication and classical information
• Quantum entanglement as a new information processing resource
• Quantum one-way communication can be exponentially stronger than classical communication
• Exponential separation of quantum and classical online space complexity
• Exponential separations for one-way quantum communication complexity, with applications to cryptography
• Quantum communication and complexity.
• scientific article; zbMATH DE number 7559369 (Why is no real title available?)
• Bounded-error quantum state identification and exponential separations in communication complexity
• Bounded-error quantum state identification and exponential separations in communication complexity
• Simultaneous communication protocols with quantum and classical messages
• An Optimal Separation of Randomized and Quantum Query Complexity
• Almost-everywhere superiority for quantum polynomial time
• Quantum communication complexity of linear regression
• PSPACE has constant-round quantum interactive proof systems
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• Quantum versus randomized communication complexity, with efficient players
• Quantum branching programs and space-bounded nonuniform quantum complexity
• Classical versus quantum communication in XOR games
• A new exponential separation between quantum and classical one-way communication complexity
• New bounds on the classical and quantum communication complexity of some graph properties
• Noisy interactive quantum communication
• Query-to-communication lifting for BPP
• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• Quantum versus randomized communication complexity, with efficient players
• Forrelation: a problem that optimally separates quantum from classical computing
• scientific article; zbMATH DE number 7559046 (Why is no real title available?)
• scientific article; zbMATH DE number 1954386 (Why is no real title available?)
• Entangled simultaneity versus classical interactivity in communication complexity
• Quantum one-way versus classical two-way communication in XOR games
• scientific article; zbMATH DE number 7204275 (Why is no real title available?)
• Exponential Separation of Information and Communication for Boolean Functions
• Exponential separation of quantum and classical one-way communication complexity
• Quantum communication complexity advantage implies violation of a Bell inequality
• Quantum and classical communication complexity of permutation-invariant functions
• Classical vs quantum advice and proofs under classically-accessible oracle
• Exponential Separation of Quantum and Classical One-Way Communication Complexity
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• The Quantum Communication Complexity of Sampling
• Round elimination in exact communication complexity
• scientific article; zbMATH DE number 7559121 (Why is no real title available?)
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Quantum weakly nondeterministic communication complexity
• Towards characterizing the non-locality of entangled quantum states
• Optimal bounds for parity-oblivious random access codes
• On quantum and probabilistic communication: Las Vegas and one-way protocols

This page was built for publication: Exponential separation of quantum and classical communication complexity

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