  We prove that the fidelity of two exemplary 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 outperforms the best classical protocol, making it the candidate
for multi-party quantum communication applications.
