Abstract
In 1979 Yao published a paper that started the field of communication complexity and asked, in particular, what was the randomized complexity of the Equality function in the Simultaneous Message Passing (SMP) model. The tight lower bound was given only in 1996 by Newman and Szegedy.
In this work we develop a new lower bound method for analyzing the complexity of Equality in SMP.
Our technique allows us to obtain the the following new results:
- It allows to show a tight lower bound for the quantum-classical case.
- It leads to tight lower bounds for both Equality and its complement in all non-deterministic versions of quantum-classical SMP, where Merlin may also be quantum. Previous methods do not seem to work in this case.
Our characterization leads to tight trade-offs between the message lengths needed for players Alice, Bob, Merlin, not just the maximum message length among them, and highlights that the complement of Equality is easier than Equality in the case of classical proofs, but not for quantum proofs.
Along the way, we give tight analysis of a new quantum communication primitive, where a honest classical and an untrusted quantum party help a third party to obtain an approximate copy of a quantum state.