  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 the first semi-device-independent
certification of the absence of a definite order of communication.
