Quantum versus randomized communication complexity, with efficient players

DOI10.1007/S00037-022-00232-7MaRDI QIDQ2099674zbMATH OpenOpenAlexFDO

Authors Uma Girish, Ran Raz, Avishay Tal

Publication date 24 November 2022

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.02218

zbMATH Keywords

communication complexityexponential separationquantumrandomized

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11) Quantum algorithms and complexity in the theory of computing (68Q12)

Recommendations

• Exponential separation of quantum communication and classical information
• Exponential separation of quantum and classical communication complexity
• Simultaneous communication protocols with quantum and classical messages
• Exponential Separation of Quantum and Classical One-Way Communication Complexity
• Entangled simultaneity versus classical interactivity in communication complexity

Cites work

• Analysis of Boolean Functions
• BQP and the polynomial hierarchy
• Entangled simultaneity versus classical interactivity in communication complexity
• Exponential separation of quantum and classical communication complexity
• Exponential separation of quantum and classical one-way communication complexity
• Exponential separations for one-way quantum communication complexity, with applications to cryptography
• Forrelation: a problem that optimally separates quantum from classical computing
• Fourier analysis for probabilistic communication complexity
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 7250141 (Why is no real title available?)
• Oracle separation of BQP and PH
• Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
• Quantum one-way communication can be exponentially stronger than classical communication
• Query-to-communication lifting for BPP
• Query-to-communication lifting for BPP using inner product
• Structure of protocols for XOR functions

Cited in

(3)

• Classical versus quantum communication in XOR games
• One-way communication complexity of partial XOR functions
• Quantum lower bounds by sample-to-query lifting

This page was built for publication: Quantum versus randomized communication complexity, with efficient players

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