We study the communication complexity variant "Simultaneous Message Passing" introduced by Yao in 1979. In this model there are three players Alice, Bob and a referee. Both Alice and Bob have an input string of n bits, say x and y. Alice and Bob are only allowed to send messages to the referee who has to compute some Boolean function f(x,y). The goal is to minimize the number of bits transmitted.

In the randomized version of this model where Alice and Bob possess private random coins it was shown by Ambainis (96) that for the EQUALITY function O(\srqt(n)) bits suffice. Newman and Szegedy (96) showed that the EQUALITY function needs \Omega(\srqt(n)) bits. Their result was improved by Babai and Kimmel (97) who showed that for any Boolean function the randomized and the deterministic complexity can be at most quadratically far apart.

We consider the quantum version of this model where Alice and Bob can send qubits to the referee. We show that in the quantum world Alice and Bob can compute the EQUALITY function with high probability by sending only O(log(n)) qubits to the referee.

In this talk we will review the basic "quantum computing" tools and no prior knowledge of these is necessary.