This article provide the first example of a communication model and a distributed task, for which there exists a realistic quantum protocol which is asymptotically more efficient than any classical protocol, both in the communication and the information resources.