Exponential separation of quantum and classical communication complexity

DOI10.1145/301250.301343zbMath1345.68134OpenAlexW1991730713MaRDI QIDQ2819566

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 computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Experimental multipartner quantum communication complexity employing just one qubit, Quantum entanglement as a new information processing resource, An Optimal Separation of Randomized and Quantum Query Complexity, Classical versus quantum communication in XOR games, Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness, Forrelation: A Problem That Optimally Separates Quantum from Classical Computing, Small ball probability and Dvoretzky's Theorem, Quantum weakly nondeterministic communication complexity, Towards characterizing the non-locality of entangled quantum states, Quantum one-way versus classical two-way communication in XOR games, Quantum communication complexity advantage implies violation of a Bell inequality, Parity decision tree in classical-quantum separations for certain classes of Boolean functions, Query-to-Communication Lifting for BPP, Unbounded-Error Classical and Quantum Communication Complexity, On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity, Noise and the Mermin-GHZ Game, Quantum branching programs and space-bounded nonuniform quantum complexity, Unnamed Item, Unnamed Item, Unnamed Item, Noisy Interactive Quantum Communication, The complexity of quantum disjointness, Optimal bounds for parity-oblivious random access codes, Quantum communication and complexity., Quantum versus randomized communication complexity, with efficient players, Almost-everywhere superiority for quantum polynomial time, PSPACE has constant-round quantum interactive proof systems