Consider a decentralized partially-observed Markov decision problem (POMDP) with multiple cooperative agents aiming to maximize a long-term-average reward criterion. We observe that the availability, at a fixed rate, of entangled states of a product quantum system between the agents, where each agent has access to one of the component systems, can result in strictly improved performance even compared to the scenario where common randomness is provided to the agents, i.e. there is a quantum advantage in decentralized control. This observation comes from a simple reinterpretation of the conclusions of the well-known Mermin-Peres square, which underpins the Mermin-Peres game. While quantum advantage has been demonstrated earlier in one-shot team problems of this kind, it is notable that there are examples where there is a quantum advantage for the one-shot criterion but it disappears in the dynamical scenario. The presence of a quantum advantage in dynamical scenarios is thus seen to be a novel finding relative to the current state of knowledge about the achievable performance in decentralized control problems. This paper is dedicated to the memory of Pravin P. Varaiya.
It is known in the context of decentralised control that there exist control strategies consistent with the requirements of a given information structure, yet physically unimplementable through any amount of passive common randomness. This imposes a natural set of limitations on what is achievable through common randomness in both cooperative and competitive settings. We show that it is possible to breach these limitations with the use of quantum-physical architectures. In particular, we present a class of stochastic strategies that leverage quantum entanglement to produce strategic distributions which compose a strict superclass of strategies implemented through passive common randomness. We investigate numerically, the `quantum advantage' offered by this new class over a parametric family of cooperative decision problems with static information structure. We demonstrate through variations across the parametric family that fundamental decision theoretic elements such as information and the cost determine the manifestation of quantum advantage in a given control problem. Our work motivates a novel decision and control paradigm with an enlarged space of control policies achievable by means of quantum architectures.
The inability to communicate poses a major challenge to coordination in multi-agent reinforcement learning (MARL). Prior work has explored correlating local policies via shared randomness, sometimes in the form of a correlation device, as a mechanism to assist in decentralized decision-making. In contrast, this work introduces the first framework for training MARL agents to exploit shared quantum entanglement as a coordination resource, which permits a larger class of communication-free correlated policies than shared randomness alone. This is motivated by well-known results in quantum physics which posit that, for certain single-round cooperative games with no communication, shared quantum entanglement enables strategies that outperform those that only use shared randomness. In such cases, we say that there is quantum advantage. Our framework is based on a novel differentiable policy parameterization that enables optimization over quantum measurements, together with a novel policy architecture that decomposes joint policies into a quantum coordinator and decentralized local actors. To illustrate the effectiveness of our proposed method, we first show that we can learn, purely from experience, strategies that attain quantum advantage in single-round games that are treated as black box oracles. We then demonstrate how our machinery can learn policies with quantum advantage in an illustrative multi-agent sequential decision-making problem formulated as a decentralized partially observable Markov decision process (Dec-POMDP).
Ananthram and Borkar [1] showed that there exist strategies that are consistent with the requirements of a decentralized information structure but are unattainable through the use of common randomness. This opens the question of discovering physically realisable mechanisms that provide access to this region of the strategic space. In our previous work we introduced a class of quantum strategies that allow such access in a two-agent setting. In this paper, we consider the problem of optimal allocation of a
k-partite quantum resource amongst
nagents,
k<n. We study the problem of decentralized estimation of a binary source by agents that are informed through independent binary symmetric channels, and face a cost that is homogeneous in their actions. We show a
k-partite quantum resource produces the maximum advantage over classical strategies when allocated to the agents with the
kmost reliable channels.
We present an empirical evaluation of quantum entanglement in agent coordination within quantum multi agent reinforcement learning (QMARL). While QMARL has attracted growing interest recently, most prior work evaluates quantum policies without provable baselines, making it impossible to rigorously distinguish quantum advantage from algorithmic coincidence. We address this directly by evaluating a decentralized QMARL framework with variational quantum circuit (VQC) actors with shared entangled states. In the CHSH game, which has a mathematically proven classical performance ceiling of 0.75 win rate, we show that entangled QMARL agents approach the Tsirelson limit of 0.854, providing clear evidence of their quantum advantage. We show that unentangled quantum circuits match the classical baseline, confirming that entanglement and not the quantum circuit itself is the active coordination mechanism. We also explore the effect of specific entanglement structures, as some Bell states enable coordination gains while others actively harm performance. On cooperative navigation (CoopNav), QMARL without entanglement achieves
∼2× improvement in success rate over classical MAA2C ($\sim$0.85 versus $\sim$0.40), with the hybrid configuration, quantum actor paired with a classical centralised critic, outperforming both fully classical and fully quantum solutions. We present our experimental analysis and discuss future work.
This work considers the non-interactive source simulation problem (NISS). In the standard NISS scenario, a pair of distributed agents observe a distributed binary memoryless source (
Xd,Yd) generated based on the joint distribution
PX,Y. The agents wish to produce a pair of discrete random variables
(Ud,Vd)with joint distribution
PUd,Vd, such that
PUd,Vdconverges in total variation distance to a target distribution
QU,V. Two variations of the standard NISS scenario are considered. In the first variation, in addition to
(Xd,Yd), the agents have access to a shared Bell state. They each measure their respective state, using a measurement of their choice, and use its classical output along with
(Xd,Yd)to simulate the target distribution. This scenario is called the entanglement-assisted NISS (EA-NISS). In the second variation, the agents have access to a classical common random bit
Z, in addition to (
Xd,Yd). This scenario is called the common randomness NISS (CR-NISS). It is shown that for binary output NISS scenarios, the set of simulatable distributions for EA-NISS and CR-NISS are equal with each other. Hence, there is no quantum advantage in these EA-NISS scenarios. For non-binary output NISS, it is shown that in a specific class of scenarios, the set of CR-NISS simulatable distributions forms a measure zero subset of EA-NISS simulatable distributions. A numerical example is provided, where the set of EA-NISS simulatable distributions strictly contains the set of CR-NISS simulatable distributions. This shows that there is a quantum advantage in non-binary output EA-NISS.
We have shown that entanglement assisted stochastic strategies allow access to strategic measures beyond the classically correlated measures accessible through passive common randomness, and thus attain a quantum advantage in decentralised control. In this two part series of articles, we investigate the decision theoretic origins of the quantum advantage within a broad superstructure of problem classes. Each class in our binary team superstructure corresponds to a parametric family of cost functions with a distinct algebraic structure. In this part, identify the only problem classes that benefit from quantum strategies. We find that these cost structures admit a special decision-theoretic feature -- `the coordination dilemma'. Our analysis hence reveals some intuition towards the utility of non-local quantum correlations in decentralised control.