Quantum Communication Cannot Simulate a Public Coin
<|reference_start|>Quantum Communication Cannot Simulate a Public Coin: 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.<|reference_end|>
@article{gavinsky2004quantum,
    title={Quantum Communication Cannot Simulate a Public Coin},
    author={Dmytro Gavinsky (U Calgary), Julia Kempe (LRI Paris), Ronald de Wolf
  (CWI Amsterdam)},
    journal={arXiv preprint arXiv:quant-ph/0411051},
    year={2004},
    archivePrefix={arXiv},
    eprint={quant-ph/0411051},
    primaryClass={quant-ph cs.CC}
}