Interaction in quantum communication and the complexity of \textsc{Set Disjointness}

DOI10.1145/380752.380786MaRDI QIDQ5175960zbMATH OpenOpenAlexDBLPWikidataFDO

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

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 algorithms and complexity in the theory of computing (68Q12) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum computation (81P68)

Recommendations

• Interaction in Quantum Communication
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• Quantum communication and complexity.
• scientific article; zbMATH DE number 2086394
• scientific article; zbMATH DE number 1954386

Cites work

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

Cited in

(21)

• Quantum communication and complexity.
• A new protocol and lower bounds for quantum coin flipping
• Lower bounds for predecessor searching in the cell probe model
• Equality, revisited
• A direct product theorem for two-party bounded-round public-coin communication complexity
• Interactive Information Complexity
• scientific article; zbMATH DE number 1954386 (Why is no real title available?)
• The Quantum Communication Complexity of Sampling
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• Interactive information complexity
• scientific article; zbMATH DE number 6851887 (Why is no real title available?)
• Quantum communication complexity of symmetric predicates
• The complexity of quantum disjointness
• Entangled Simultaneity Versus Classical Interactivity in Communication Complexity
• Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test
• Round elimination in exact communication complexity
• Quantum distributed complexity of set disjointness on a line
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• Classical and Quantum Computations with Restricted Memory
• A hierarchy of constant communication complexity
• Pointer chasing with unlimited interaction

This page was built for publication: Interaction in quantum communication and the complexity of \textsc{Set Disjointness}

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