The Quantum Communication Complexity of Sampling

DOI10.1137/S009753979935476MaRDI QIDQ4441894zbMATH OpenOpenAlexWikidataFDO

Authors Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, A. Wigderson, Andris Ambainis

Publication date 8 January 2004

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s009753979935476

zbMATH Keywords

communication complexityquantum communication complexityquantum information theoryset-disjointnessthe log-rank conjecture in communication complexity

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Combinatorics in computer science (68R05)

Recommendations

• Exponential separation of quantum and classical communication complexity
• Quantum communication complexity of symmetric predicates
• Quantum communication and complexity.
• Interaction in quantum communication and the complexity of \textsc{Set Disjointness}
• scientific article; zbMATH DE number 5568623

Cited in

(16)

• Quantum communication and complexity.
• Multipartite quantum correlation and communication complexities
• Communication complexity with small advantage
• The equivalence of sampling and searching
• The equivalence of sampling and searching
• Bitwise Quantum Min-Entropy Sampling and New Lower Bounds for Random Access Codes
• Sampling in a quantum population, and applications
• Quantum communication complexity of symmetric predicates
• A lower bound for sampling disjoint sets
• Classical algorithms from quantum and Arthur-Merlin communication protocols
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• A hierarchy of constant communication complexity
• Sampling, flowers and communication
• Classical vs quantum advice and proofs under classically-accessible oracle
• Bounded-depth circuits cannot sample good codes
• Quantum communication complexity of linear regression

This page was built for publication: The Quantum Communication Complexity of Sampling

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