Exponential separation of quantum and classical communication complexity

From MaRDI portal
Publication:2819566

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



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