  We study the power of quantum fingerprints in the simultaneous message
passing (SMP) setting of communication complexity. Yao recently showed how to
simulate, with exponential overhead, classical shared-randomness SMP protocols
by means of quantum SMP protocols without shared randomness
($Q^\parallel$-protocols). Our first result is to extend Yao's simulation to
the strongest possible model: every many-round quantum protocol with unlimited
shared entanglement can be simulated, with exponential overhead, by
$Q^\parallel$-protocols. We apply our technique to obtain an efficient
$Q^\parallel$-protocol for a function which cannot be efficiently solved
through more restricted simulations. Second, we tightly characterize the power
of the quantum fingerprinting technique by making a connection to arrangements
of homogeneous halfspaces with maximal margin. These arrangements have been
well studied in computational learning theory, and we use some strong results
obtained in this area to exhibit weaknesses of quantum fingerprinting. In
particular, this implies that for almost all functions, quantum fingerprinting
protocols are exponentially worse than classical deterministic SMP protocols.
