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
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
We investigate the quantum advantage that can arise in typical two-party communication scenarios, where the sender and the receiver are allowed to share prior correlations. Focusing on communication tasks constrained by the distinguishability of the sender's inputs, we demonstrate that entanglement-assisted communication with both classical and quantum message can outperform classical communication supplemented with shared randomness. We begin by developing a general framework for communication tasks with pre-shared correlations. Within this framework, we establish an equivalence among entanglement-assisted classical communication, entanglement-assisted quantum communication, and quantum communication, showing that no hierarchy exists between these three paradigms. We then investigate the scenario where the receiver has no input and prove that no advantage can arise in this case. However, an advantage in the entanglement-assisted setting emerges once additional constraints are imposed on the dimension of the communicated message. This further highlights the superiority of entanglement-assisted classical communication over standard quantum communication. Then we demonstrate several tasks where the entanglement-assisted protocol using one-bit communication proves to be advantageous over classical communication. Finally, by constructing an explicit class of communication tasks, we show that a non-maximally entangled states outperform the maximally entangled state as a pre-shared resource between the communicating parties.
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.
In communication complexity-like problems, previous studies have shown either an exponential quantum advantage or an unbounded quantum advantage with an exponentially large input set Θ ( 2 n ) bit with respect to classical communication Θ ( n ) bit. In the former, the quantum and classical separation grows exponentially in input while the latter's quantum communication resource is a constant. Remarkably, it was still open whether an unbounded quantum advantage exists while the inputs do not scale exponentially. Here we answer this question affirmatively using an input size of optimal order. Considering two variants as tasks: (1) distributed computation of relation and (2) , we study the one-way zero-error communication complexity of a relation induced by a distributed clique labeling problem for orthogonality graphs. While we prove no quantum advantage in the first task, we show an in relation reconstruction without public coins. Specifically, for a class of graphs with order m , the quantum complexity is Θ ( 1 ) while the classical complexity is Θ ( log 2 m ) . Remarkably, the input size is Θ ( log 2 m ) bit and the order of its scaling with respect to classical communication is . This is exponentially better compared to previous works. Additionally, we prove a lower bound (linear in the number of maximum cliques) on the amount of classical public coin necessary to overcome the separation in the scenario of restricted communication and connect this to the existence of orthogonal arrays. Finally, we highlight some applications of this task to semi-device-independent dimension witnessing as well as to the detection of mutually unbiased bases.
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.
Quantum mechanics enables information-processing advantages even at the level of a single qubit. A paradigmatic example is the 2$\to$1 random access code (RAC), where a qubit outperforms a classical bit in retrieving encoded information. In the standard form, however, this quantum advantage is restricted to a single receiver, since decoding measurements inevitably destroy the encoded information. Contrary to this, we address how long the information encoded in a single qubit remains accessible even after multiple decoding, each with a quantum advantage. Introducing preparation distinguishability as an operational resource associated with the sender, we show that its interplay with measurement incompatibility on the receiver's side can mitigate measurement-induced disturbance, thereby enabling an arbitrarily long sequence of receivers to each retain a quantum advantage. Our results show that, even under repeated measurements, the information encoded in a qubit need not be entirely exhausted, revealing a stronger communication feature than previously recognised.
Quantum systems are known to offer advantages over their classical counterpart in communication complexity protocols, where the aim is to minimize the amount of information exchange between distant parties to compute global functions of their distributed inputs. In this work, we establish that any one-way communication protocol implemented using a prime-dimensional quantum system -- restricted to stabilizer-state encodings and Clifford-operation decodings -- can be exactly simulated by transmitting a classical system of the same dimension, given access to shared randomness between the sender and receiver. In direct analogy with the Gottesman-Knill theorem, which attributes quantum computational speedup to non-stabilizer resources, commonly known as the magic resources, our result identifies the same non-stabilizer resources as the essential ingredient for the quantum advantage in one-way communication complexity. Furthermore, we present explicit tasks where even a 'minimal magic resource' suffices to achieve a provable quantum advantage, highlighting its efficient use in communication protocols.