Interaction in quantum communication and the complexity of set disjointness

DOI10.1145/380752.380786zbMath1323.68287OpenAlexW2044344951WikidataQ62398493 ScholiaQ62398493MaRDI QIDQ5175960

Ashwin Nayak, Hartmut Klauck, David Zuckerman, Amnon Ta-Shma

Publication date: 27 February 2015

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

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

Mathematics Subject Classification ID

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

Related Items

A new protocol and lower bounds for quantum coin flipping ⋮ Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ Equality, Revisited ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Lower bounds for predecessor searching in the cell probe model ⋮ Exponential lower bound for 2-query locally decodable codes via a quantum argument ⋮ Quantum communication and complexity.

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)