Quantum versus randomized communication complexity, with efficient players

DOI10.1007/s00037-022-00232-7OpenAlexW3134293981MaRDI QIDQ2099674

Ran Raz, Uma Girish, 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

quantumcommunication complexityrandomizedexponential separation

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fourier analysis for probabilistic communication complexity
• Exponential separation of quantum and classical communication complexity
• BQP and the polynomial hierarchy
• Forrelation
• Exponential separation of quantum and classical one-way communication complexity
• Structure of Protocols for XOR Functions
• Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
• Query-To-Communication Lifting for BPP Using Inner Product
• Query-to-Communication Lifting for BPP
• Analysis of Boolean Functions
• Oracle separation of BQP and PH
• Entangled simultaneity versus classical interactivity in communication complexity
• Quantum one-way communication can be exponentially stronger than classical communication

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