|
|
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.
|