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.
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.
In communication complexity, a number of distant parties have the task of calculating a distributed function of their inputs, while minimizing the amount of communication between them. It is known that with quantum resources, such as entanglement and quantum channels, one can obtain significant reductions in the communication complexity of some tasks. In this work, we study the role of the quantum superposition of the direction of communication as a resource for communication complexity. We present a tripartite communication task for which such a superposition allows for an exponential saving in communication, compared to one-way quantum (or classical) communication; the advantage also holds when we allow for protocols with bounded error probability.
Abstract In a variant of communication tasks, players cooperate in choosing their local strategies to compute a given task later, working separately. Utilizing quantum bits for communication and sharing entanglement between parties is a recognized method to enhance performance in these situations. In this work, we introduce the game for which three parties, Alice, Bob and Charlie, would like to discover the hidden order in which they make the moves. We show the advantage of quantum strategies that use shared entanglement and local operations over classical setups for discriminating operations’ composition order. The role of quantum resources improving the probability of successful discrimination is also investigated. Our research provides a basis for examining computational model featuring a specific gate set while examining the diverse operations achievable through permutations of its elements.
Quantum communication can outperform classical communication in a variety of information-processing tasks, but such advantages are typically established for a fixed communication network. Here we introduce topology-independent quantum advantage, in which a quantum protocol outperforms every classical protocol subject to the same communication constraint, irrespective of how the classical communication resource is distributed among the parties or which communication topology is employed, even when the parties may share unlimited classical randomness. We first demonstrate this phenomenon through a simple three-party equality task: two senders receive ternary classical inputs, while an input-free receiver determines whether the inputs are equal. We then formulate a general framework for topology-independent communication and completely characterize the corresponding classical correlation polytope in the minimal three-party scenario. Its facet inequalities reveal several instances of topology-independent quantum advantage. Remarkably, one of these inequalities enables the semi-device-independent certification of a nonunitary quantum channel, while another certifies a sequential quantum network topology without any prior assumption about the network configuration. Finally, we extend the framework to four-party networks, characterize the relevant classical communication structures, and identify a communication task exhibiting quantum advantages against all admissible classical topologies. Our results establish topology independence as a genuine and robust form of quantum advantage in communication networks.
Finding exponential separation between quantum and classical information tasks is like striking gold in quantum information research. Such an advantage is believed to hold for quantum computing but is proven for quantum communication complexity. Recently, a novel quantum resource called the quantum switch-which creates a coherent superposition of the causal order of events, known as quantum causality-has been harnessed theoretically in a new protocol providing provable exponential separation. We experimentally demonstrate such an advantage by realizing a superposition of communication directions for a two-party distributed computation. Our photonic demonstration employs d-dimensional quantum systems, qudits, up to d=2^{13} dimensions and demonstrates a communication complexity advantage, requiring less than (0.696±0.006) times the communication of any causally ordered protocol. These results elucidate the crucial role of the coherence of communication direction in achieving the exponential separation for the one-way processing task, and open a new path for experimentally exploring the fundamentals and applications of advanced features of indefinite causal structures.
Abstract A series of recent works has shown that placing communication channels in a coherent superposition of alternative configurations can boost their ability to transmit information. Instances of this phenomenon are the advantages arising from the use of communication devices in a superposition of alternative causal orders, and those arising from the transmission of information along a superposition of alternative trajectories. The relation among these advantages has been the subject of recent debate, with some authors claiming that the advantages of the superposition of orders could be reproduced, and even surpassed, by other forms of superpositions. To shed light on this debate, we develop a general framework of resource theories of communication. In this framework, the resources are communication devices, and the allowed operations are (a) the placement of communication devices between the communicating parties, and (b) the connection of communication devices with local devices in the parties’ laboratories. The allowed operations are required to satisfy the minimal condition that they do not enable communication independently of the devices representing the initial resources. The resource-theoretic analysis reveals that the aforementioned criticisms on the superposition of causal orders were based on an uneven comparison between different types of quantum superpositions, exhibiting different operational features.
Entanglement is known to boost the efficiency of classical communication. In distributed computation, for instance, exploiting entanglement can reduce the number of communicated bits or increase the probability to obtain a correct answer. Entanglement-assisted classical communication protocols usually consist of two successive rounds: first, a Bell test round, in which the parties measure their local shares of the entangled state, and then a communication round, where they exchange classical messages. Here, we go beyond this standard approach and investigate adaptive uses of entanglement: we allow the receiver to wait for the arrival of the sender's message before measuring their share of the entangled state. We first show that such adaptive protocols improve the success probability in random access codes. Second, we show that once adaptive measurements are used, an entanglement-assisted bit becomes a strictly stronger resource than a qubit in prepare-and-measure scenarios. We briefly discuss the extension of these ideas to scenarios involving quantum communication and we identify resource inequalities.