Experimental quantum communication complexity
Pavel Trojek, Christian Schmid, Mohamed Bourennane, Časlav Brukner, Marek Żukowski, Harald Weinfurter · Physical Review A · 2005
We prove that by communicating $N\ensuremath{-}1$ times a single qubit, instead of $N\ensuremath{-}1$ classical bits, the success probability for solving some $N$ partner communication complexity tasks is strongly enhanced. The superiority, as measured by the quantum-to-classical fidelity ratio, of the quantum scheme grows exponentially with $N$. We report an experimental implementation of these tasks for $N=5$. Even without correcting for any inefficiencies of the state-of-the-art setup, our multiparty quantum protocol still outperforms the best classical protocols.