Quantum superposition of the order of parties as a communication resource

In a variant of communication complexity tasks, two or more separated parties cooperate to compute a function of their local data, using a limited amount of communication. It is known that communication of quantum systems and shared entanglement can increase the probability for the parties to arrive at the correct value of the function, compared to classical resources. Here we show that quantum superpositions of the direction of communication between parties can also serve as a resource to improve the probability of success. We present a tripartite task for which such a superposition provides an advantage compared to the case where the parties communicate in a fixed order. In a more general context, our result also provides semi-device-independent certification of the absence of a definite order of communication.

Figure 1

Examples of quantum circuits (in red) mapping two CPTP maps ${\mathcal{M}}_A,{\mathcal{M}}_B$ and two states ${\sigma }_C,{\rho }_T$ to a state ${\rho }_{CT}^{\prime }$. The order of applying gates is well defined—$A⪯B$ for the left circuit and $B⪯A$ for the right one.

Figure 2

Tripartite $(n{log}_{2}3,m)$-Hamming game where Alice and Bob receive input strings of the length $n{log}_{2}3$ bits, and Charlie has to compute $f(x,y)$. The total communication is $m$ bits or qubits; no entanglement is preshared.

Figure 3

Optimal causally separable protocol for the equality game, where no entanglement is shared among the parties.

Figure 4

Linear optical implementation of the protocol using the quantum switch [9, 29]. The control state ${|\varphi \rangle }_C$ is encoded in polarization and the target state ${|\psi \rangle }_T$ in another photonic degree of freedom. Alice and Bob apply Pauli operators on the target system depending on their input $x$ and $y$. Charlie performs a measurement in the $|x\pm \rangle$ basis on the outgoing control system $C$ and consequently outputs ${\delta }_{x,y}$. Note that in the experiment of Ref. [10], the control state was instead encoded in path.