We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a prior quantum entanglement cannot be used to simulate a communication channel, it can reduce the communication complexity of functions in some cases. Specifically, we show that, for a particular function among three parties (each of which possesses part of the function's input), a prior quantum entanglement enables them to learn the value of the function with only three bits of communication occurring among the parties, whereas, without quantum entanglement, four bits of communication are necessary. We also show that, for a particular two-party probabilistic communication complexity problem, quantum entanglement results in less communication than is required with only classical random correlations (instead of quantum entanglement). These results are a noteworthy contrast to the well-known fact that quantum entanglement cannot be used to actually simulate communication among remote parties.
For a tripartite pure state of three qubits, it is well known that there are two inequivalent classes of genuine tripartite entanglement, namely the Greenberger-Horne-Zeilinger (GHZ) class and the W class. Any two states within the same class can be transformed into each other with stochastic local operations and classical communication with a nonzero probability. The optimal conversion probability, however, is only known for special cases. Here, lower and upper bounds are derived for the optimal probability of transformation from a GHZ state to other states of the GHZ class. A key idea in the derivation of the upper bounds is to consider the action of the local operations and classical communications (LOCC) protocol on a different input state, namely $1/\sqrt{2}[|000\ensuremath{\rangle}\ensuremath{-}|111\ensuremath{\rangle}]$, and to demand that the probability of an outcome remains bounded by 1. We also find an upper bound for more general cases by using the constraints of the so-called interference term and 3-tangle. Moreover, some of the results are generalized to the case in which each party holds a higher dimensional system. In particular, the GHZ state generalized to three qutrits; that is, $|{\mathrm{GHZ}}_{3}\ensuremath{\rangle}=1/\sqrt{3}[|000\ensuremath{\rangle}+|111\ensuremath{\rangle}+|222\ensuremath{\rangle}]$ shared among three parties can be transformed to any tripartite three-qubit pure state with probability 1 via LOCC. Some of our results can also be generalized to the case of a multipartite state shared by more than three parties.
Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of
k parties hold some partial input data to some fixed
k-variable function
f. The communication complexity of
f is the minimum number of classical bits required to be broadcasted for every party to know the value of
f on their inputs. We construct a function
G such that for the one-round communication model and three parties,
G can be computed with
n+1 bits of communication when the parties share prior entanglement. We then show that without entangled particles, the one-round communication complexity of
G is
(3/2)n+1. Next we generalize this function to a function
F. We show that if the parties share prior quantum entanglement, then the communication complexity of
F is exactly
k. We also show that, if no entangled particles are provided, then the communication complexity of
F is roughly
klog2k. These two results prove communication complexity separations better than a constant number of bits.
The states of three-qubit systems split into two inequivalent types of genuine tripartite entanglement, namely, the Greenberger-Horne-Zeilinger (GHZ) type and the
W type. A state belonging to one of these classes can be stochastically transformed only into a state within the same class by local operations and classical communications. We provide local quantum operations, consisting of the most general two-outcome measurement operators, for the deterministic transformations of three-qubit pure states in which the initial and the target states are in the same class. We explore these transformations, originally having standard GHZ and standard
W states, under the local measurement operations carried out by a single party and
p (
p=2,3) parties (successively). We find a notable result that the standard GHZ state cannot be deterministically transformed to a GHZ-type state in which all its bipartite entanglements are nonzero, i.e., a transformation can be achieved with unit probability when the target state has at least one vanishing bipartite concurrence.