Sharing correlated random variables is a resource for a number of information theoretic tasks such as privacy amplification, simultaneous message passing, secret sharing and many more. In this article, we show that to establish such a resource called shared randomness, quantum systems provide an advantage over their classical counterpart. Precisely, we show that appropriate albeit fixed measurements on a shared two-qubit state can generate correlations which cannot be obtained from any possible state on two classical bits. In a resource theoretic set-up, this feature of quantum systems can be interpreted as an advantage in winning a two players co-operative game, which we call the `non-monopolize social subsidy' game. It turns out that the quantum states leading to the desired advantage must possess non-classicality in the form of quantum discord. On the other hand, while distributing such sources of shared randomness between two parties via noisy channels, quantum channels with zero capacity as well as with classical capacity strictly less than unity perform more efficiently than the perfect classical channel. Protocols presented here are noise-robust and hence should be realizable with state-of-the-art quantum devices.
Sharing correlated random variables is a resource for a number of information theoretic tasks such as privacy amplification, simultaneous message passing, secret sharing and many more. In this article, we show that to establish such a resource called shared randomness, quantum systems provide an advantage over their classical counterpart. Precisely, we show that appropriate albeit fixed measurements on a shared two-qubit state can generate correlations which cannot be obtained from any possible state on two classical bits. In a resource theoretic set-up, this feature of quantum systems can be interpreted as an advantage in winning a two players co-operative game, which we call the `non-monopolize social subsidy' game. It turns out that the quantum states leading to the desired advantage must possess non-classicality in the form of quantum discord. On the other hand, while distributing such sources of shared randomness between two parties via noisy channels, quantum channels with zero capacity as well as with classical capacity strictly less than unity perform more efficiently than the perfect classical channel. Protocols presented here are noise-robust and hence should be realizable with state-of-the-art quantum devices.
Randomness appears both in classical stochastic physics and in quantum mechanics. A number of communication models and other information protocols entail sharing randomness among distant parties. Here we report a computational scenario of shared randomness processing where quantum sources manifest clear-cut precedence over the corresponding classical counterparts. The advantage is established in a resource theoretic set-up which we formalize in this work. The classical mutual information turns out to be a faithful resource quantifier of shared randomness although it does not sufficiently characterize all possible transitions among the resources. Quantum theory exhibits advantage in shared randomness processing in the sense that the set of resourceful states obtained under free operation from a bipartite quantum system is strictly larger than the set obtained from an analogous classical system. Interestingly, the quantum advantage can be manifested in the optimal payoff of a two players co-operative game -- the `non-monopolize social subsidy' game. We also show that the quantum states resulting to the desired advantage necessitates nonclassicality in the form of quantum discord. We then address the task of distributing shared randomness between two parties. Quite interestingly, it turns out that noisy quantum channel can exhibit advantage even when it has zero quantum capacity and classical capacity much less than the corresponding classical channel. The imperfect channel examples facilitates and welcomes experiment to achieve the reported quantum advantage with presently available quantum devices.
Coordination is a fundamental primitive in communication and information theory, in which distributed systems must collectively generate correlated behavior rather than merely exchange messages. In quantum networks, the nature of entanglement, quantum measurements, and nonclassical correlations introduces coordination possibilities unavailable classically. This article reviews recent advances in coordination over classical and quantum communication networks, focusing on empirical and strong coordination in multi-user settings.
We consider the implications of coordination for nonlocal games, showing how it provides a natural framework for understanding the correlations that enable spatially separated players to improve their probability of winning. We present a unified framework for coordination using classical or quantum communication and pre-shared correlation resources. The review covers simulation of both entanglement and separable correlations across a variety of network architectures, including two-node, cascade, broadcast, and multiple-access networks. We study the operational differences between empirical and strong coordination, and the tradeoffs between communication and correlation resources, such as pre-shared randomness and entanglement.
Coordination plays a major role in device-independent quantum key distribution (DI-QKD) schemes, in which parties can generate a secret key even if the devices used in the process have been prepared by an adversary. Furthermore, we examine the role of coordination in quantum repeaters, where distributed entanglement serves as a resource for long-distance quantum communication. The review highlights connections between coordination theory and applications such as distributed quantum systems, quantum internet architectures, and future communication networks.
We analyze utility of communication channels in absence of any short of quantum or classical correlation shared between the sender and the receiver. To this aim, we propose a class of two-party communication games, and show that the games cannot be won given a noiseless 1 -bit classical channel from the sender to the receiver. Interestingly, the goal can be perfectly achieved if the channel is assisted with classical shared randomness. This resembles an advantage similar to the quantum superdense coding phenomenon where pre-shared entanglement can enhance the communication utility of a perfect quantum communication line. Quite surprisingly, we show that a qubit communication without any assistance of classical shared randomness can achieve the goal, and hence establishes a novel quantum advantage in the simplest communication scenario. In pursuit of a deeper origin of this advantage, we show that an advantageous quantum strategy must invoke quantum interference both at the encoding step by the sender and at the decoding step by the receiver. We also study communication utility of a class of non-classical toy systems described by symmetric polygonal state spaces. We come up with communication tasks that can be achieved neither with 1 -bit of classical communication nor by communicating a polygon system, whereas 1 -qubit communication yields a perfect strategy, establishing quantum advantage over them. To this end, we show that the quantum advantages are robust against imperfect encodings-decodings, making the protocols implementable with presently available quantum technologies.
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.
We implement an experiment on a photonic quantum processor establishing efficacy of the elementary quantum system in classical information storage. The advantage is established by considering a class of simple bipartite games played with the communication resource qubit and classical bit (c bit), respectively. Conventional wisdom, supported by the no-go theorems of Holevo and Frenkel-Weiner, suggests that such a quantum advantage is unattainable when the sender and receiver share randomness or classical correlations. However, our results reveal a quantum advantage in a scenario devoid of any shared randomness. Our experiment involves the development of a variational triangular polarimeter, enabling the realization of positive operator value measurements crucial for establishing the targeted quantum advantage. Beyond showcasing a robust communication advantage with a single qubit, our work paves the way for immediate applications in near-term quantum technologies. It provides a semi-device-independent certification scheme for quantum encoding-decoding systems and offers an efficient method for information loading and transmission in quantum networks.
We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space.