On quantum and probabilistic communication

Abstract

We investigate the power of quantum communication protocols compared to classical probabilistic protocols. In our first result we describe a total Boolean function that has a quantum Las Vegas protocol communicating at most O(N 1/11+~) qubits for all e > 0, while any classical probabilistic protocol (with bounded error) needs ~(N/log N) bits. Then we investigate quantum one-way communication complexity. First we show that the VC-dimension lower bound on one-way probabilistic communication of [26] holds for quantum protocols, too. Then we prove that for oneway protocols computing total functions quantum Las Vegas communication is asymptotically as efficient as exact quantum communication, which is exactly as efficient as deterministic communication. We describe applications of the lower bounds for one-way communication complexity to quantum finite automata and quantum formulae.