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.
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.
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
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.
We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement.
We first introduce XOR Equality, a total Boolean function in which each of k players receives an unrestricted string xj∈{0,1}n, and the referee must decide whether x1⊕⋯⊕xk=0n. For k≥8 and worst-case error at most 1/3, we prove quantum lower bounds of Ω(min{n,k2}) on total communication and Ω(min{n/k,k}) on maximum message length. A classical public-coin protocol uses two bits per player with error at most 1/4. For n=k2 and worst-case error at most 1/3, we prove that quantum protocols require maximum message length Ω(n) qubits, whereas two public-coin bits per player suffice.
We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a k-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of Ω(n1−1/k) on maximum message length, matched by a classical private-coin protocol. For any fixed error ε∈(0,1/8), we also prove a bounded-error quantum lower bound of Ω(n(k−1)/(k+1)) while we show that public-coin protocols solve the relation unambiguously with maximum message length O(logn), giving exponential separations in both regimes. The implicit constants are independent of k, and both quantum lower bounds become linear when k≥clogn for any fixed c>0.
A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions fn:{0,1}n×{0,1}n→{0,1} that can be computed with O(logn) bits of one-way classical communication given prior entanglement, but that require Ω(n1/3) qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.
Despite the conceptual importance of contextuality in quantum mechanics, there is a hitherto limited number of applications requiring contextuality but not entanglement. Here, we show that for any quantum state and observables of sufficiently small dimensions producing contextuality, there exists a communication task with quantum advantage. Conversely, any quantum advantage in this task admits a proof of contextuality whenever an additional condition holds. We further show that given any set of observables allowing for quantum state-independent contextuality, there exists a class of communication tasks wherein the difference between classical and quantum communication complexities increases as the number of inputs grows. Finally, we show how to convert each of these communication tasks into a semi-device-independent protocol for quantum key distribution.
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.