2019/11/06 by Uma Girish, Girish, Uma, Ran Raz +3 · 6 citations
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1911.02218
arxiv created 2019/11/06 · openalex publication_date 2019/11/06 · arxiv updated 2019/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a new type of separation between quantum and classical communication complexity which is obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits with oracle access to their inputs. More precisely, we give an explicit partial Boolean function that can be computed in the quantum-simultaneous-with-entanglement model of communication, however, every interactive randomized protocol is of exponentially larger cost. Furthermore, all the parties in the quantum protocol can be implemented by quantum circuits of small size with blackbox access to the inputs. Our result qualitatively matches the strongest known separation between quantum and classical communication complexity and is obtained using a quantum protocol where all parties are efficient.