Quantum Communication Cannot Simulate a Public Coin

Abstract

We study the simultaneous message passing model of communication complexity. Building on the quantum fingerprinting protocol of Buhrman et al., Yao recently showed that a large class of efficient classical public-coin protocols can be turned into efficient quantum protocols without public coin. This raises the question whether this can be done always, i.e. whether quantum communication can always replace a public coin in the SMP model. We answer this question in the negative, exhibiting a communication problem where classical communication with public coin is exponentially more efficient than quantum communication. Together with a separation in the other direction due to Bar-Yossef et al., this shows that the quantum SMP model is incomparable with the classical public-coin SMP model. In addition we give a characterization of the power of quantum fingerprinting by means of a connection to geometrical tools from machine learning, a quadratic improvement of Yao's simulation, and a nearly tight analysis of the Hamming distance problem from Yao's paper.

12 pages LaTeX

References in corpus (1)

• A note on the power of quantum fingerprinting

Cited by in corpus (7)

• The Communication Complexity of the Hamming Distance Problem
• Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models
• Communication Complexities of XOR functions
• Quantum sketching protocols for Hamming distance and beyond
• A Note on Shared Randomness and Shared Entanglement in Communication
• Near log-convexity of measured heat in (discrete) time and consequences
• Linear Sketching over ${\mathbb{F}}_2$