Experimental multipartner quantum communication complexity employing just one qubit

Most proposals for quantum solutions of information-theoretic problems rely on the usage of multi-partite entangled states which are still difficult to produce experimentally with current state-of-the-art technology. Here, we analyze a scheme to simplify a particular kind of multiparty communication protocols for the experiment. We prove that the fidelity of two communication complexity protocols, allowing for an N − 1 bit communication, can be exponentially improved by N − 1 (unentangled) qubit communication. Taking into account, for a fair comparison, all inefficiencies of state-of-the-art set-up, the experimental implementation for N = 5 outperforms the best classical protocol, making it the candidate for multi-party quantum communication applications.