SciTes
7
0807.2758[abs pdf]
Title: Simultaneous Communication Protocols with Quantum and Classical Messages
Authors: Oded Regev, Ronald de Wolf

We study the simultaneous message passing model of communication complexity, for the case where one party is quantum and the other is classical. We show that in a protocol where the first party sends q qubits and the second party sends c classical bits, the quantum message can be replaced by a randomized message of O(qc) classical bits, as well as by a deterministic message of O(q c log q) classical bits. In particular, our results imply that quantum-classical protocols need to send Omega(\sqrt{n/\log n}) bits/qubits to compute equality, and hence are not significantly better than classical-classical protocols (and are much worse than quantum-quantum protocols such as quantum fingerprinting). This essentially answers a recent question of Wim van Dam. Our proofs rely heavily on earlier results due to Scott Aaronson.

Comments


Comments (0)

Login to Coment
Username:
Password:
Remember me next time
Register yourself