  We consider the problem of bounded-error quantum state identification: given
either state \alpha_0 or state \alpha_1, we are required to output `0', `1' or
`?' ("don't know"), such that conditioned on outputting `0' or `1', our guess
is correct with high probability. The goal is to maximize the probability of
not outputting `?'. We prove a direct product theorem: if we're given two such
problems, with optimal probabilities a and b, respectively, and the states in
the first problem are pure, then the optimal probability for the joint
bounded-error state identification problem is O(ab). Our proof is based on
semidefinite programming duality and may be of wider interest.
  Using this result, we present two exponential separations in the simultaneous
message passing model of communication complexity. Both are shown in the
strongest possible sense. First, we describe a relation that can be computed
with O(log n) classical bits of communication in the presence of shared
randomness, but needs Omega(n^{1/3}) communication if the parties don't share
randomness, even if communication is quantum. This shows the optimality of
Yao's recent exponential simulation of shared-randomness protocols by quantum
protocols without shared randomness. Second, we describe a relation that can be
computed with O(log n) classical bits of communication in the presence of
shared entanglement, but needs Omega((n/log n)^{1/3}) communication if the
parties share randomness but no entanglement, even if communication is quantum.
This is the first example in communication complexity of a situation where
entanglement buys you much more than quantum communication does.
