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.
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.
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.
We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on
n bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every
k≥1:
Q∥∗ versus
R2∗: We show that quantum simultaneous protocols with
Θ~(k5log3n) qubits of entanglement can exponentially outperform two-way randomized protocols with
O(k) qubits of entanglement. This resolves an open problem from [Gav08] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gav19, GRT22].
R∥∗ versus
Q∥∗: We show that classical simultaneous protocols with
Θ~(klogn) qubits of entanglement can exponentially outperform quantum simultaneous protocols with
O(k) qubits of entanglement, resolving an open question from [GKRW06, Gav19]. The best result prior to our work was a relational separation against protocols without entanglement [GKRW06].
R∥∗ versus
R1∗: We show that classical simultaneous protocols with
Θ~(klogn) qubits of entanglement can exponentially outperform randomized one-way protocols with
O(k) qubits of entanglement. Prior to our work, only a relational separation was known [Gav08]. Our techniques can also be used to show advantages of quantum communication models over hybrid classical-quantum models, i.e., models that have a large amount of both classical communication and quantum simultaneous communication.
When considering the complexity of communication protocols, the aim is to perform a certain task with the minimum amount of communication resources, such as time and transmitted information. The use of quantum states may lead to an exponential advantage in the use of such resources. Here, we are interested in the task of calculating the Euclidean distance between two vectors representing real data sets. It has been previously shown that it is possible to obtain an advantage for this task based on quantum fingerprinting. This protocol is defined in the simultaneous message passing model of communication complexity, where the two parties do not communicate with each other but send data to a third party, and exploits practical fingerprints generated using trains of coherent state pulses instead of highly entangled qubit states that are hard to generate for large input sizes needed to demonstrate an exponential advantage. We perform a proof-of-principle experimental demonstration of the Euclidean distance protocol using amplitude modulation techniques for encoding non-binary data sets and high-performance superconducting nanowire single-photon detectors required to increase the accessible input size. We show a quantum advantage in transmitted information surpassing the best classical protocol for an input size of
108, for diverse types of data sets, including those corresponding to real grayscale images, and with reasonable precision and error bounds. Our results highlight the potential of quantum communication complexity for use in a broad set of applications.
Communication complexity is a fundamental aspect of information science, concerned with the amount of communication required to solve a problem distributed among multiple parties. The standard quantification of one-way communication complexity relies on the minimal dimension of the communicated systems. In this paper, we measure the communication complexity of a task by the minimal required to accomplish it, while leaving the dimension of the communicated systems unconstrained. Distinguishability is defined as the maximum probability of correctly guessing the sender's input from the message, quantifying the message's distinctiveness relative to the sender's input. This measure becomes especially relevant when maintaining the confidentiality of the sender's input is essential. After establishing the generic framework, we focus on three relevant families of communication complexity tasks—the random access codes, equality problems defined by graphs, and the pair-distinguishability tasks. We derive general lower bounds on the minimal classical distinguishability as a function of the success metric of these tasks. We demonstrate that quantum communication outperforms classical communication presenting explicit protocols and utilizing semidefinite programming methods. In particular, we demonstrate for random access codes and Hadamard graph-based equality problems. Specifically, we show that the classical-to-quantum ratio of minimal distinguishability required to achieve the same success metric escalates polynomially and exponentially with the complexity of these tasks, reaching arbitrarily large values. Published by the American Physical Society 2024
In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games
G when Alice and Bob are allowed to use a limited amount of one-way classical communication
ωo.w.−c(G) (resp. one-way quantum communication
ωo.w.−c∗(G)), where
c denotes the number of bits (resp. qubits). The key quantity here is the quotient
ωo.w.−c∗(G)/ωo.w.−c(G). We provide a universal way to obtain Bell inequality violations of general Bell functionals from XOR games for which the quotient
ωo.w.−c∗(G)/ωo.w.−2c(G) is larger than 1. This allows, in particular, to find (unbounded) Bell inequality violations from communication complexity problems in the same spirit as the recent work by Buhrman et al. (2016). We also provide an example of a XOR game for which the previous quotient is optimal (up to a logarithmic factor) in terms of the amount of information
c. Interestingly, this game has only polynomially many inputs per player. For the related problem of separating the classical vs quantum communication complexity of a function, the known examples attaining exponential separation require exponentially many inputs per party.