Empirical coordination of separable quantum correlations

1.   Introduction

Shannon theory for point-to-point networks has had a profound influence on communication in the digital age ^[1,2,3]. However, the simplistic model of a single source-destination pair does not capture many critical aspects of real-world networks ^[4]. In practice, networked systems often involve multiple sources and destinations, requiring the network to compute functions or make decisions rather than merely transmit data. The Internet of Things (IoT) introduces additional challenges due to its reliance on a shared medium ^[5]. Furthermore, networks entail intricate tradeoffs between competition for resources ^[6,7], cooperation for collective gain ^[8], and security ^[9]. Network information theory seeks to address fundamental questions of information flow and processing while incorporating these essential characteristics of real-world networks ^{[10,11,12,13]}. Recent advances in IoT have drawn attention to the role of coordination in networks with diverse topologies ^[14].

Coordination is a fundamental framework in network information theory ^[15]. Cuff et al. ^[16] introduced a general information-theoretic model for network coordination where, as opposed to traditional coding tasks, the objective is not to exchange messages between network nodes but rather generate correlation ^[17]. Two types of coordination tasks were introduced in the classical framework ^[16]. In strong coordination, the users produce actions in order to simulate a product distribution. That is, the joint distribution resembles that of a particular memoryless source ^[18]. Empirical coordination imposes a weaker and less stringent condition compared to strong coordination. It requires the type, i.e., the frequency of actions, to converge into a desired distribution ^[19]. There are many information-theoretic tasks that are closely related to coordination, such as channel/source simulation ^{[21,22,23,24]}, randomness extraction ^[25,26], entanglement distribution ^[27], state transformation ^[28,29], state merging ^[30,31], entanglement dilution ^[32,33,34], and compression ^{[35,36,37,38,39,40]}.

Empirical coordination and its variations are widely studied in the classical information theory literature. Le Treust ^[17] considered joint source-channel empirical coordination. Le Treust and Bloch ^[41] further used empirical coordination as a unified perspective for masking, amplification, and parameter estimation at the receiver. Cuff and Zhao ^[42] studied empirical coordination using implicit communication, with information embedding applications, such as digital watermarking, steganography, cooperative communication, and strategic play in team games. Cervia et al. ^[43] devised a polar coding scheme for empirical coordination. Related models can also be found in ^[44,45].

Quantum mechanics enables the calculation of probabilities for experimental outcomes, emphasizing statistical averages rather than detailed descriptions of individual events. For instance, the Heisenberg uncertainty principle states that the standard deviations of position and momentum cannot be minimized simultaneously ^[46]. Some scholars, such as Fuchs and Peres ^[47], contend that quantum theory does not describe physical reality at all but is instead confined to represent statistical correlations ^[48]. Empirical coordination is thus a natural framework for quantum systems.

Empirical coordination also plays a role in quantum data compression ^[49]. Barnum et al. ^[50] addressed a source of commuting density operators, and Kramer and Savari ^[36] developed a rate-distortion theory that unifies the visible and blind approaches (cf. ^[51,52]). Khanian and Winter have recently solved the general problem of a quantum source of mixed states (see also ^{[52,53,54,55,56,57,58]}).

Coordination of separable correlations with classical links is described as follows. Consider a network of $K$ nodes, where Node $k$ performs an encoding operation $\mathcal{E}_k$ on a system $A_k$, for $k\in \{{1, \dots, K}\}$. Some of the nodes are connected by one-way classical links. We denote the rate limit for the link from Node $k$ to Node $l$ by $R_{k, l}$. Before the coordination protocol begins, the nodes may also share common randomness (CR). Furthermore, some of the nodes can have access to side information. The objective in the coordination problem is to establish a specific correlation, i.e., to simulate a desired quantum state $\omega_{A_1\dots A_K}$. Since the links are classical, the correlation is separable. The optimal performance is defined by the communication rates that are necessary and sufficient for simulating the desired correlation on average.

In analogy to the classical framework, we distinguish between two types of coordination tasks: strong coordination and empirical coordination. In strong coordination, the users encode in order to simulate an $n$-fold product state, $\omega_{A_1\dots A_K}^{\otimes n}$. That is, the joint state resembles that of a memoryless quantum source. In our previous work, we have considered strong coordination ^[59,60,61]. In particular, we addressed strong coordination for entanglement generation using quantum links ^[59] and for classical-quantum (c-q) correlations with classical links ^[60]. Strong coordination can be viewed as a unified framework for various models. We list a few examples of related protocols:

1) Channel resolvability: Resolvability aims to approximate the output of a c-q channel using a uniformly distributed codebook ^[62]. This is equivalent to c-q state simulation ^[62]. Resolvability is also referred to as c-q soft covering ^[63]. Quantum soft covering is further studied in ^[64].

2) Entanglement dilution and distillation: In the dilution task, Alice and Bob use a maximally entangled state as well as local operations and classical communication (LOCC) in order to prepare a joint state ^[32,33]. In the other direction, maximal entanglement can be distilled from a bipartite state $\omega_{AB}$ using classical communication at a rate $R_{1, 2}\geq H(A|B)_\omega$ (see ^[65]). A similar rate also appears in the distillation of a secret key [65, Remark 2]. Further work can be found in ^{[65,66,67,68,69,70,71,72,73,74]}.

3) State merging and splitting: In state merging, Alice and Bob share $\omega_{AB}$, and Alice would like to send her part to Bob ^[31,75]. The mother protocol generalizes this task ^[76,77]. Whereas, state splitting is the reverse task, where Alice holds $AB$, and would like to send $B$ to Bob ^[78,79,80].

4) Channel simulation: A classical channel of capacity $C$ can be simulated at a rate of $R_{1, 2}$ if and only if $R_{1, 2}\geq C$, given sufficient common randomness ^[81,82]. The quantum analog is not necessarily true ^[67]. The entanglement cost with LOCC is related to the entanglement of formation ^[20].

Multi-user versions of the protocols above have been studied extensively in recent years. The mother protocol can generate distributed compression protocols for correlated quantum sources ^{[76,83,84,85,86,87,88]}. Simulation of broadcast and multiple-access channels is considered in ^[89,90] and ^[91], respectively. George and Cheng ^[92] have recently studied multipartite state splitting. Multi-user distillation and manipulation were considered in ^{[93,94,95,96,97,98,99]}. Streltsov et al. ^[100] studied multipartite state merging. A more detailed overview is given in ^[61].

Here, we introduce the notion of empirical coordination for separable correlations, imposing a weaker and less stringent condition compared to strong coordination. We require the empirical average state to converge into the desired state $\omega_{A_1\dots A_K}$. Specifically, let $\mathbf{A}(1), \ldots, \mathbf{A}(n)$ denote the output sequence from all network nodes, where $\mathbf{A}(i)\equiv (A_1(i), \ldots, A_K(i))$ is the output, at time $i$, for $i\in \{{1, \dots, n}\}$. Then, we would like the nodes to produce an empirical average state $\frac{1}{n}\sum_{i = 1}^n \rho_{\mathbf{A}(i)}$ that is arbitrarily close to $\omega_{\mathbf{A}}$, where $\mathbf{A}\equiv (A_1, \ldots, A_K)$. That is, we require that the distance,

converges to zero as the block length $n$ tends to infinity. In this work, we focus on the quantum empirical coordination of separable correlations. Our networks consist of nodes possessing quantum systems, and are connected with classical links of limited communication rates.

After introducing the definition of empirical coordination for quantum states, we discuss the justification for our definition and its physical interpretation. We focus on the 3-node cascade network and determine the optimal coordination rates, which represent the minimal resources for the empirical simulation of a separable state among multiple parties. The cascade network with $K = 3$ users can be viewed as a building block for larger multiuser systems ^[101,102]. The cascade setting is depicted in Figure 1. Alice, Bob, and Charlie wish to simulate a separable state $\omega_{ABC}$. They are provided with rate-limited communication links, $R_{1 \rightarrow 2}$ from Alice to Bob, and $R_{2 \rightarrow 3}$ from Bob to Charlie.

Our results are summarized below. We show that CR between the network users does not affect the optimal rates for empirical coordination. We begin with the rate characterization for the basic two-node network, and then generalize to a cascade network. The special case of a network with an isolated node is considered as well. The results can be further generalized to other networks as our analysis includes a generic achievability scheme. The characterization involves optimization over a collection of state extensions. This is a unique feature of the quantum setting, as the classical parallel does not include optimization ^[16]. As will be seen in the examples, the performance depends heavily on the choice of decomposition. We further discuss the consequences of our results for cooperative games.

In Section 2, we set our notation conventions. In Section 3, we present the definitions for our model and their physical interpretation. Section 4 is dedicated to the results, including the statement about CR and the capacity theorems for the two-node, cascade, and isolated node networks. Section 5 and Section 6 provide the achievability and converse analysis, respectively. Section 7 concludes with a discussion about the comparison between strong coordination and empirical coordination, as well as the implications of our results on quantum cooperative games.

2.   Notation

We use standard notation in quantum information theory, as in ^[103], $X, Y, Z, \ldots$ are discrete random variables on finite alphabets $\mathcal{X}, \mathcal{Y}, \mathcal{Z}, ...$, respectively, The distribution of $X$ is specified by a probability mass function (PMF) $p_X(x)$ on $\mathcal{X}$. The set of all PMFs over $\mathcal{X}$ is denoted by $\mathcal{P}(\mathcal{X})$. The normalized total variation distance between two PMFs in $\mathcal{P}(\mathcal{X})$ is defined as

for every $p_X$, $q_X\in$ $\mathcal{P}(\mathcal{X})$.

The classical Shannon entropy is then defined as $H(p_X) = \sum_{x\in\mathrm{supp}(p_X)} p_X(x)\log\left(\frac{1}{p_X(x)} \right)$, with logarithm to base $2$. We often use the short notation $H(X)\equiv H(p_X)$ for $X\sim p_X$. Similarly, given a joint PMF $p_{XY}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})$, we write $H(XY)\equiv H(p_{XY})$. The mutual information between $X$ and $Y$ is $I(X; Y) = H(X)+H(Y)-H(XY)$. A classical channel is defined by a probability kernel $\{ p_{Y|X}(y|x) \, :\; x\in\mathcal{X}, y\in\mathcal{Y} \}$. The conditional entropy with respect to $p_X\times p_{Y|X}$ is defined as $H(Y|X) = \sum_{x\in\mathrm{supp}(p_X)} p_X(x)H(Y|X = x)$, where $H(Y|X = x)\equiv H(p_{Y|X}(\cdot|x))$. According to the entropy chain rule, $H(Y|X) = H(XY)-H(X)$.

We use $x^n = (x_i:\, i\in [n])$ for a sequence of letters from $\mathcal{X}$, where $[n]\equiv \{{1, \dots, n}\}$. We define the type of a sequence $x^n$ as the empirical distribution, $\hat{P}_{x^n}(a) = \frac{1}{n}N(a|x^n)$, where $N(a|x^n)$ is the number of occurrences of the letter $a$ in the sequence $x^n$, for $a\in\mathcal{X}$. The $\delta$-typical set for a PMF $p_X$ is defined here as the set of sequences whose type is $\delta$-close to $p_X$ in total variation distance. Formally,

A quantum system is associated with a Hilbert space, $\mathcal{H}$. The dimensions are assumed to be finite throughout. Denote the set of all linear operators $F:\mathcal{H}\to \mathcal{H}$ by $L(\mathcal{H})$. The Hermitian conjugate of $F$ is denoted by $F^\dagger$. The extension of a real-valued function to Hermitian operators is defined in the usual manner. Analogously to the total variation distance between classical PMFs, the normalized trace distance between two Hermitian operators satisfies

for every Hermitian $P$, $Q\in \; L(\mathcal{H})$.

Let System $A$ be associated with $\mathcal{H}_A$. The quantum state of $A$ is described by a density operator $\rho_A\in L(\mathcal{H}_A)$, i.e., a unit-trace positive semidefinite operator. Let $\Delta(\mathcal{H}_A)$ denote the set of all such operators. The probability distribution of a measurement outcome is derived from a positive operator-valued measure (POVM). In finite dimensions, this reduces to a finite set of positive semidefinite operators $\{D_j \, :\; j\in [N] \}$ that satisfy $\sum_{j = 1}^N D_j = \mathbb{1}$, where $\mathbb{1}$ denotes the identity operator. By the Born rule, the probability of a measurement outcome $j$ is given by $p_J(j) = \mathrm{Tr}(D_j \rho_A)$, for $j\in [N]$.

The von Neumann entropy of a quantum state $\rho_A\in\Delta(\mathcal{H}_A)$ is defined as $H(\rho_A) \equiv - \mathrm{Tr}[ \rho_A\log(\rho_A) ]$. We often denote the quantum entropy by $H(A)_\rho\equiv H(\rho_A)$. Similarly, given a joint state $\rho_{AB}\in \Delta(\mathcal{H}_A\otimes \mathcal{H}_B)$, we write $H(AB)_\rho\equiv H(\rho_{AB})$. A pure state has zero entropy, in which case, there exists $\left| {{\psi}} \right\rangle\in\mathcal{H}_A$ such that $\rho = \left| {{\psi} × {\psi}} \right|$, where $\left\langle {{\psi}} \right|\equiv (\left| {{\psi}} \right\rangle)^\dagger$. The conditional quantum entropy is defined by $H(A|B)_{\rho} = H(AB)_\rho-H(B)_\rho$. The conditional mutual information is defined accordingly, as $I(A; B|C)_{\rho}\equiv H(A|C)_\rho+H(B|C)_\rho-H(A, B|C)_\rho$ for $\rho_{ABC}\in\Delta(\mathcal{H}_A\otimes \mathcal{H}_B\otimes \mathcal{H}_C)$.

A bipartite state $\rho_{AB}$ is said to be separable if a set of product states $\{\rho_x\otimes \sigma_x\}$ in $\Delta(\mathcal{H}_A\otimes \mathcal{H}_B)$ can be found such that

for some alphabet $\mathcal{X}$ and PMF $p_X$ on $\mathcal{X}$. Otherwise, $\rho_{AB}$ is called entangled. If the state is entangled, then the conditional entropy $H(A|B)_\rho$ can be negative. The definition can also be extended to a multipartite system. A state $\rho_{A_1\ldots A_K}$ in $\Delta(\mathcal{H}_{A_1}\otimes\cdots\otimes \mathcal{H}_{A_K})$ is said to be separable if

for some ensemble $\{p_X\, ,\; \rho^{(1)}_x\otimes\cdots\otimes \rho^{(K)}_x \, ,\; x\in\mathcal{X}\}$.

A quantum channel is defined by a completely positive trace-preserving map, $\mathcal{N}_{A\to B}: L(\mathcal{H}_A)\to L(\mathcal{H}_B)$. In general, the channel maps a state $\rho\in \Delta(\mathcal{H}_A)$ into a state $\mathcal{N}_{A\to B}(\rho)\in \Delta(\mathcal{H}_B)$. A classical-quantum (c-q) channel $\mathcal{N}_{X\to B}$ is specified by a collection of quantum states $\{\rho_B^{(x)}\, :\; x\in\mathcal{X} \}$ in $\Delta(\mathcal{H}_B)$, where $\rho_B^{(x)}\equiv \mathcal{N}_{X\to B}(x)$ for $x\in\mathcal{X}$.

3.   Model definition and physical interpretation

3.1.   Coding definitions

In this subsection, we introduce the basic definitions for empirical coordination. Consider the cascade network shown in Figure 2, which involves three users, Alice, Bob, and Charlie. Let $\{ p_X(x)\, ,\; \omega_{ABC}^x \, ,\; x\in\mathcal{X} \}$ be a given ensemble, with an average

Suppose that Alice receives a random sequence $X^n$, drawn from a memoryless (i.i.d) source $\sim p_X$. This can be viewed as side information that Alice obtains from a local measurement on her environment. Alice sends a classical message $m_{1 \rightarrow 2}$ to Bob via a noiseless link of limited rate $R_{1 \rightarrow 2}$, and Bob sends $m_{2 \rightarrow 3}$ to Charlie at a limited rate $R_{2 \rightarrow 3}$. Next, Alice, Bob, and Charlie encode their respective quantum outputs $A^n, B^n$, and $C^n$. The objective of the empirical coordination protocol is for the average state to be arbitrarily close to a particular state $\omega_{ABC}$.

Remark 1. Achieving empirical coordination allows the network users to perform local measurements such that the outcome statistics follow a desired behavior.

In other words, the users utilize a coding scheme that simulates, on average, a desired state $\omega_{ABC}$. We are interested in the lowest communication rates $(R_{1 \rightarrow 2}, R_{2 \rightarrow 3})$ that are required in order to achieve this goal.

In the beginning, we assume that Alice, Bob, and Charlie share unlimited common randomness (CR). That is, a random element $S$ is drawn a priori and distributed to Alice, Bob, and Charlie before the protocol begins. Later, we will show that CR does not affect the achievable rates.

Definition 1. A $(2^{nR_{1 \rightarrow 2}}, 2^{nR_{2 \rightarrow 3}}, n)$ empirical coordination code for the cascade network shown in Figure 2 consists of:

● a CR source $p_S$ over a randomization set $\mathfrak{S}_n$,

● a pair of classical encoding channels, $p_{M_{1\rightarrow 2}|X^n S}$ and $p_{M_{2 \rightarrow 3}|M_{1 \rightarrow 2}S}$, over the index sets $\big[2^{nR_{1 \rightarrow 2}}\big]$ and $\big[2^{nR_{2 \rightarrow 3}}\big]$, respectively, and

● c-q encoding channels,

and

for Alice, Bob, and Charlie, respectively, where $\mathfrak{S}_n$ is an unbounded set of realizations for the CR resource that is shared between the users a priori.

The protocol works as follows: Before communication begins, Alice, Bob, and Charlie share a CR element $s$, drawn from the source $p_S$. Alice receives a sequence $x^n$, generated from a memoryless source $p_X$. That is, the random sequence is distributed according to $p_X^n(x^n)\equiv \prod_{i = 1}^n p_X(x_i)$. She selects an index

at random, and sends it through a noiseless classical link at rate $R_{1 \rightarrow 2}$. She then applies the encoding channel $\mathcal{E}_{X S\to A}^{\otimes n}$, to prepare the state of her system $A^n$, hence

As Bob receives the message $m_{1 \rightarrow 2}$ and the CR element $s$, he selects a random index

and sends it through a noiseless classical link at rate $R_{2 \rightarrow 3}$ to Charlie. Bob and Charlie encode their systems, $B^n$ and $C^n$, by

and

respectively.

Given a value $s$, i.e., a realization of the random element, consider the average state $\overline{\rho}_{ABC}(s)\in \Delta(\mathcal{H}_A\otimes \mathcal{H}_B\otimes \mathcal{H}_C)$ that is induced by the code:

We now define achievable rates as rates that are sufficient to encode $\overline{\rho}_{ABC}(s)$ that converges to $\omega_{ABC}$.

Definition 2. A rate pair $\left(R_{1 \rightarrow 2}, R_{2 \rightarrow 3}\right)$ is achievable for the empirical coordination of a desired separable state $\omega_{ABC}$, if for every $\alpha, \varepsilon, \delta > 0$ and a sufficiently large $n$, there exists a $\left(2^{n(R_{1 \rightarrow 2}+\alpha)}, 2^{n(R_{2 \rightarrow 3}+\alpha)}, n\right)$ coordination code that achieves

where the probability is computed with respect to the CR element $S\sim p_S$.

Equivalently, there exists a sequence of empirical coordination codes such that the error converges to zero in probability, i.e.,

Remark 2. Since the communication links are classical, entanglement cannot be generated. Therefore, we only consider separable states $\omega_{ABC}$.

3.2.   Quantum measurements

In this subsection, we discuss the justification and the physical interpretation of our coordination criterion. As mentioned in the Introduction, quantum mechanics enables the calculation of probabilities for experimental outcomes, emphasizing statistical averages rather than detailed descriptions of individual events. For instance, the Heisenberg uncertainty principle states that the standard deviations of position and momentum cannot be minimized simultaneously ^[46]. Some scholars, such as Fuchs and Peres ^[47], contend that quantum theory does not describe physical reality at all but is instead confined to represent statistical correlations ^[48]. Empirical coordination is thus a natural framework for quantum systems. Further justification is provided below.

Consider an observable represented by an Hermitian operator $\hat{O}$ on $\mathcal{H}_A\otimes \mathcal{H}_B\otimes \mathcal{H}_C$. In practice, statistics are collected by performing measurements on $n$ systems $(A_i, B_i, C_i \, :\; i\in [n])$. The expected value of the observable in the $i$th measurement is thus,

for $i\in [n]$. Therefore, the empirical average is

Similarly, consider a POVM $\{D_\ell: \ell\in [L]\}$ on $\mathcal{H}_A\otimes \mathcal{H}_B\otimes \mathcal{H}_C$. The probability that we obtain the measurement outcome $\ell$ in the $i$th measurement is $p_i(\ell) = \mathrm{Tr}(D_\ell \cdot \rho_{A_i B_i C_i})$. Thereby, the average distribution is given by

4.   Main results

4.1.   Common randomness does not help

Theorem 1. Any desired state $\omega_{ABC}$ that can be simulated at rate $(R_{1 \rightarrow 2}, R_{2 \rightarrow 3})$ through empirical coordination in the cascade network with CR assistance can also be simulated with no CR, i.e., with $|\mathfrak{S}_n| = 1$.

We will discuss the interpretation of this result in Subsection 7.4. The proof is provided below.

Proof. Let $(R_{1 \rightarrow 2}, R_{2 \rightarrow 3})$ be an achievable rate pair for empirical coordination. Consider the setting in Section 3. Let the CR element $S$ and the classical side information $X^n$ be drawn according to $p_S$ and $p_X^n$, respectively. Then, Alice, Bob, and Charlie encode by

Denote the normalized trace distance by

for $s\in\mathfrak{S}_n$.

According to Definition 2, if a rate pair $(R_{1 \rightarrow 2}, R_{2 \rightarrow 3})$ is achievable, then for every $\alpha, \varepsilon, \delta > 0$ and sufficiently large $n$, there exists a sequence of $\left(2^{n(R_{1 \rightarrow 2}+\alpha)}, 2^{n(R_{2 \rightarrow 3}+\alpha)}, n\right)$ empirical coordination codes, for which the following holds:

Averaging over the CR element yields the following average state

By the total expectation formula,

where the second line follows from (4.5), and the last inequality holds by choosing $\delta < \frac{\varepsilon}{2}$. Therefore, there exists $s^*\in\mathfrak{S}_n$ for which $d(s^*)\leq \varepsilon$. We can thus satisfy the coordination requirement with the following encoding maps,

which no longer require CR. □

Next, we characterize the achievable rates for empirical coordination. We begin with a basic two-node network, and then generalize to a cascade network. Based on Theorem 1 above, introducing CR does not affect the achievable rates. Therefore, we will focus our definitions on empirical coordination without CR.

4.2.   Two-node network

Consider the two-node network. See Figure 3. Alice and Bob would like to simulate a separable state $\omega_{AB}$ on average using the following coding scheme. Alice receives classical side information from a memoryless source $p_X$. She encodes $A^n$, and then sends an index $m_{1 \rightarrow 2}$, i.e., a classical message to Bob, at a rate $R_{1 \rightarrow 2}$.

Formally, a $\left(2^{n R_{1 \rightarrow 2}}, n\right)$ empirical coordination code for a separable state $\omega_{AB}$ consists of an input distribution $p_{M_{1 \rightarrow 2}|X^n}$ over an index set $\big[2^{nR_{1 \rightarrow 2}}\big]$, and two c-q encoding channels $\mathcal{E}_{X\to A}$, and $\mathcal{F}_{M_{1 \rightarrow 2}\to B^n}$. The protocol works as follows. Alice receives $x^n$, drawn according to $p_X^n$. She selects a random index

and sends it through a noiseless link. Furthermore, she encodes $A^n$ by

As Bob receives the message $m_{1 \rightarrow 2}$, he prepares the state

Hence, the resulting average (joint) state is

Definition 3. A rate $R_{1 \rightarrow 2}\geq 0$ is achievable for the empirical coordination of $\omega_{AB}$ if for every $\varepsilon, \alpha > 0$ and sufficiently large $n$, there exists a $\left(2^{n(R_{1 \rightarrow 2}+\alpha)}, n\right)$ code that achieves

Definition 4. The empirical coordination capacity for the simulation of a separable state $\omega_{AB}$ over the two-node network is defined as the infimum of achievable rates. We denote the capacity by $C_{\text{2-node}}(\omega)$.

The optimal rate for empirical coordination is established below. Consider the extended c-q state,

Here, $X$ plays the role of a classical register. Furthermore, let $\mathscr{S}_{\text{2-node}}(\omega)$ be the set of all c-q extensions

such that

Notice that given a classical pair $(X, Y) = (x, y)$, there is no correlation between $A$ and $B$. We also note that if $\omega_{AB}$ is entangled, then $\mathscr{S}_{\text{2-node}}(\omega)$ is an empty set.

Theorem 2. Let $\omega_{AB}$ be a bipartite state in $\Delta(\mathcal{H}_A\otimes \mathcal{H}_B)$. If the set $\mathscr{S}_{\mathit{\text{2-node}}}(\omega)$ is nonempty, then the empirical coordination capacity for the two-node network in Figure 3 is given by

Otherwise, if $\mathscr{S}_{\mathit{\text{2-node}}}(\omega) = \emptyset$, then coordination is impossible.

The achievability proof for Theorem 2 is given in Subsection 5.2, and the converse in Subsection 6.1.

Remark 3. The set $\mathscr{S}_{\text{2-node}}(\omega)$ is empty if and only if $\omega_{AB}$ is entangled. As mentioned in Remark 2, classical links cannot generate entanglement, hence, coordination is impossible in this case.

Remark 4. The characterization involves optimization over a collection of separable states, $\mathscr{S}_{\text{2-node}}(\omega)$. This is a unique feature of the quantum setting. In the classical setting, there is no optimization. As will be seen in Examples 1 and 2, the performance depends heavily on the chosen decomposition.

Remark 5. In the special case of orthonormal sets, $\{ \left| {{\sigma_A^x}} \right\rangle\}$ and $\{ \left| {{\sigma_B^y}} \right\rangle\}$, the coordination capacity satisfies $C_{\text{2-node}}(\omega) = I(A; B)_\omega$. This case is essentially classical.

Remark 6. One may always find a decomposition of a separable state into a combination of pure states. In particular, consider

By inserting spectral decompositions,

we obtain

where $W_1\equiv (X, V_1)$ and $W_2\equiv (Y, V_2)$. If one uses this pure-state decomposition, then the coordination rate would be $R_{1 \rightarrow 2} > I(W_1;W_2)_\sigma$. Nevertheless, the theorem shows that this can be suboptimal, since $I(XV_1;Y V_2)_\sigma\geq I(X; Y)_\sigma$.

Remark 7. Based on our previous result ^[60], strong coordination can be achieved at the same rate if Alice and Bob share sufficient CR before communication begins. Here, however, we assume that CR is not available to Alice and Bob. Yet, they can perform the coordination task at this rate, since the requirement of empirical coordination is less strict.

Example 1. Let $A$ and $B$ be a qubit pair, i.e., $\mathrm{dim}(\mathcal{H}_A) = \mathrm{dim}(\mathcal{H}_B) = 2$. Consider the state

where $\{\left| {{0}} \right\rangle, \left| {{1}} \right\rangle\}$ and $\{\left| {{+}} \right\rangle, \left| {{-}} \right\rangle\}$ are the computational basis and conjugate basis, respectively. Such decomposition can be associated with a joint distribution $p_{XY}$, where $Y = X$ with probability $1$, an alphabet of size $\left| {{\mathcal{X}}} \right| = 3$, and

Based on Theorem 2, we can achieve the rate $R_{1\rightarrow 2} = I(X; Y)_\sigma = 1.5$. The coordination rate can be significantly improved by using the decomposition below instead.

where $\eta$ is the BB84 state,

This yields the improved rate of $R_{1\rightarrow 2} = I(X; Y)_\sigma = 0.3112$.

Example 2. Consider the following qubit state,

where the second qubit can be viewed as the output of a phase-flip channel, $p\in (0, 1)$. In this case, we obtain

where $h(x) = -(1-x)\log(1-x)-x\log(x)$ is the binary entropy function on $(0, 1)$. For $p = \frac{1}{2}$, we have a product state $\omega_{AB} = \frac{ \mathbb{1}}{2}\otimes \frac{ \mathbb{1}}{2}$. Hence, communication is not necessary and the coordination capacity is $C_{\text{2-node}}(\omega) = 0$.

4.3.   Cascade network

Consider the cascade network (see Figure 4).

Alice, Bob, and Charlie wish to simulate a separable state $\omega_{ABC}$ using the following scheme. Alice receives classical side information from a memoryless source $p_X$. She encodes $A^n$, and she sends an index $m_{1 \rightarrow 2}$, i.e., a classical message to Bob, at a rate $R_{1 \rightarrow 2}$. Then Bob uses the message $m_{1 \rightarrow 2}$ to encode his systems $B^n$, and sends a message $m_{2 \rightarrow 3}$ to Charlie who uses it to encode his systems $C^n$.

Formally, a $\left(2^{n R_{1 \rightarrow 2}}, 2^{n R_{2 \rightarrow 3}}, n\right)$ empirical coordination code for the simulation of a separable state $\omega_{ABC}$ in the cascade network consists of two input distributions $p_{M_{1 \rightarrow 2}|X^n}$ and $p_{M_{2 \rightarrow 3}|X^nM_{1 \rightarrow 2}}$ over index sets $\big[2^{nR_{1 \rightarrow 2}}\big]$ and $\big[2^{nR_{2 \rightarrow 3}}\big]$, and three c-q encoding channels $\mathcal{E}_{X\to A}$, $\mathcal{F}_{M_{1 \rightarrow 2}\to B^n}$, and $\mathcal{D}_{M_{2 \rightarrow 3}\to C^n}$. The protocol works as follows:

Alice selects a random index,

and sends it through a noiseless link. Furthermore, she encodes $A^n$ by

As Bob receives the message $m_{1 \rightarrow 2}$, he generates $m_{2 \rightarrow 3}$ according to $p_{M_{2 \rightarrow 3}|X^nM_{1 \rightarrow 2}}(\cdot|x^n, m_{1\rightarrow 2})$, sends $m_{2 \rightarrow 3}$ to Charlie, and prepares the state

Having received the classical message $m_{2 \rightarrow 3}$, Charlie applies his c-q encoding map and prepares

Hence, the resulting average (joint) state is

Definition 5. A rate pair $(R_{1 \rightarrow 2}, R_{2 \rightarrow 3})$ is achievable for the empirical coordination of $\omega_{ABC}$ if for every $\varepsilon, \delta > 0$ and a sufficiently large $n$, there exists a $\left(2^{n(R_{1 \rightarrow 2}+\delta)}, 2^{n(R_{2 \rightarrow 3}+\delta)}, n\right)$ code that achieves

Definition 6. The empirical coordination capacity region for the simulation of a separable state $\omega_{ABC}$ over the cascade network is defined as the closure of all the achievable rate pairs $(R_{1, 2}, R_{2, 3})$.

We denote the capacity region by $\mathcal{C}_{\text{Cascade}}(\omega)$.

The main result for the cascade network is established below. Consider the extended c-q state,

Furthermore, let $\mathscr{S}_{\text{Cascade}}(\omega)$ be the set of all c-q extensions

such that

As before, coordination with classical links is limited to separable states (see Remarks 2 and 3).

Theorem 3. Let $\omega_{ABC}$ be a tripartite state in $\Delta(\mathcal{H}_A\otimes \mathcal{H}_B\otimes \mathcal{H}_C)$. If the set $\mathscr{S}_{\mathit{\text{Cascade}}}(\omega)$ is nonempty, then the empirical coordination capacity region for the cascade network in Figure 4 is

Otherwise, if $\mathscr{S}_{\mathit{\text{Cascade}}}(\omega) = \emptyset$, then coordination is impossible.

The achievability proof for Theorem 3 is provided in Subsection 5.3, and the converse part is provided in Subsection 6.2. We note that based on the Caratheodory's ^[104], we may limit the union to auxiliary variables of cardinality $\left| {{\mathcal{Y}}} \right|\leq \left| {{\mathcal{X}}} \right|+ \left| {{\mathcal{X}}} \right|^2 \mathrm{dim}(\mathcal{H}_A)^2\mathrm{dim}(\mathcal{H}_B)^2 \mathrm{dim}(\mathcal{H}_C)^2-1$ and $\left| {{\mathcal{Z}}} \right|\leq \left| {{\mathcal{X}}} \right|+ \left| {{\mathcal{X}}} \right|^2 \mathrm{dim}(\mathcal{H}_A)^2\mathrm{dim}(\mathcal{H}_B)^2 \mathrm{dim}(\mathcal{H}_C)^2$ (see also [105, App. B]).

Remark 8. The cascade model has a Markov structure in the sense that given the message $m_{2\to 3}$ from Bob, Charlie's state $\rho_{C^n}^{m_{2\to 3}}$ has no correlation with Alice. Nevertheless, the correlation that Alice, Bob, and Charlie simulate does not satisfy a Markov chain property. In particular, the auxiliary random variables $X$, $Y$, and $Z$ may follow a general Bayesian rule, and do not necessarily form a Markov chain.

4.3.1.   Isolated node

Consider the isolated node network in Figure 5. This is a special case of a cascade network with $R_{2\rightarrow 3} = 0$. The coordination capacity $C_{\text{Isolated}}(\omega)$ is defined similarly as in Definition 4, and can be established as a consequence of Theorem 3. Consider the extended c-q state,

Let $\mathscr{S}_{\text{Isolated}}(\omega)$ be the set of all c-q extensions $\sigma_{XYZABC}$ of the form

such that

and

Corollary 4. Let $\omega_{ABC}$ be as in Theorem 3. If the set $\mathscr{S}_{\mathit{\text{Isolated}}}(\omega)$ is nonempty, then the empirical coordination capacity for the isolated node network in Figure 5 is given by

Otherwise, if $\mathscr{S}_{\mathit{\text{Isolated}}}(\omega) = \emptyset$, then coordination is impossible.

In this case, coordination is only possible for a separable state $\omega_{ABC}$ such that $\omega_{AC} = \omega_A\otimes \omega_C$.

Remark 9. Notice that $B$ and $C$ can still be correlated, see Example 3. Given unlimited CR, it is clear that we may generate such a correlation. Even in the extreme case of no communication, we can generate $Y^n$ from a memoryless source, treat $Y^n$ as the CR element, and let $Z^n = Y^n$ (see discussion in [16, Sec. III-B]). We have seen that CR does not affect the coordination capacity, and thus, the same rates can be achieved without CR. Further intuition is given in the discussion in Subsection 7.4.

In the following example, we consider empirical coordination in the isolated node network with a tripartite state $\omega_{ABC}$, in which $B$ and $C$ are correlated.

Example 3. Consider the following qubit state,

with $\alpha, p\in (0, 1)$. In this case, $I(X; Y|Z)_{\sigma} = H(X) = h(\alpha)$.

5.   Achievability

To show the direct part of our coordination capacity theorems, we will use the generic lemma below. Consider the generic two-node network in Figure 6, where Alice receives $x^n$ and $y^n$ as input to her encoder and encodes a quantum system $A^n$. Whereas, Bob receives $y^n$ and $z^n$ as input and encodes a quantum system $B^n$. In this case, Alice has encoding maps of the form $p_{M_{1 \rightarrow 2}|X^n Y^n S }$ and $\mathcal{E}_{X^n Y^n S \to A^n}$, and Bob encodes by $\mathcal{F}_{M_{1 \rightarrow 2} Y^n Z^n S\to B^n}$. The resulting average state is

where $\rho_{A^n}^{(x^n, y^n, s)} = \mathcal{E}_{ X^n Y^n S\to A^n}(x^n, y^n, s)$ and $\rho_{B^n}^{(m_{1 \rightarrow 2}, y^n, z^n, s)} = \mathcal{F}_{M_{1 \rightarrow 2} Y^n Z^nS\to B^n}(m_{1 \rightarrow 2}, y^n, z^n, s)$.

Lemma 5. Consider a state ensemble, $\{p_{XYZ}\, p_{U|XY} \, ,\; \sigma_A^{x, y}\otimes \sigma_B^{y, z, u}\}$. Let

For every $\delta > 0$, if

then there exists a sequence of randomized $(2^{nR_{1 \rightarrow 2}}, n)$ empirical coordination codes such that

uniformly for all $(x^n, y^n, z^n)\in T_{\delta}^{(n)}(p_{XYZ})$, where the probability is computed with respect to the CR element $S$, and $\gamma(\delta)$ tends to zero as $\delta \to 0$.

5.1.   Generic scheme: Proof of Lemma 5

The proof for Lemma 5 is provided below. Consider the extended c-q state,

where $X$, $Y$, $Z$, and $U$ are classical registers. We note that $Z ⦵ (X, Y) ⦵ U$ forms a Markov chain.

By Theorem 1, we may assume that Alice and Bob share unlimited CR. Therefore, they can generate the codebook jointly using their random element.

Classical codebook construction Select $2^{nR_0}$ sequences $u^n(\ell)$, $\ell\in \big[2^{nR_0}\big]$, independently at random, each i.i.d. according to $p_U$, where

Assign each sequence with a bin index $b\left(u^n(\ell) \right)$, where $b:\mathcal{U}^n\to \big[2^{nR_{1 \rightarrow 2}}\big]$, independently at random. We thus identify the CR element $S$ as the random codebook $\{u^n(\cdot), b(\cdot)\}$.

Encoding First, consider the classical encoding function $\mathcal{M}_{1\rightarrow2}:\mathcal{X}^n\times \mathcal{Y}^n\to \big[2^{nR_{1 \rightarrow 2}}\big]$. Given a pair $(x^n, y^n)\in \mathcal{X}^n\times \mathcal{Y}^n$, find an index $\ell\in \big[2^{nR_0}\big]$ such that $(x^n, y^n, u^n(\ell))\in T_{2\delta}^{(n)}(p_{XYU})$. If there is none, set $\ell = 1$. If there is more than one, choose the smallest. Send the corresponding bin index, i.e., $m_{1 \rightarrow 2}(x^n, y^n) = b\left(u^n(\ell) \right)$.

Then, prepare

Decoding Given $(y^n, z^n)$ and $m_{1 \rightarrow 2}$, find an index $\hat{\ell}\in \big[2^{nR_0}\big]$ such that

If there is none, set $\hat{\ell} = 1$. If there is more than one, choose the smallest. Prepare the state

This results in an average state,

with $u^n\equiv u^n(\hat{\ell})$.

Error analysis Given $U^n(\hat{\ell}) = u^n$, we have

For every $u^n$ such that $(x^n, y^n, z^n, u^n)\in T^{(n)}_{\gamma(\delta)}(p_{XYZU})$,

where

Consider the event

Based on the classical result due to Cuff et al. ^[16],

for all $(x^n, y^n, z^n)\in T^{(n)}_\delta(p_{XYZ})$, where $\gamma\equiv \gamma(\delta)$ tends to zero as $\delta\to 0$, and $\alpha_n$ tends to zero as $n\to\infty$, provided that

Therefore,

This completes the proof of Lemma 5.

We are now in a position to give the achievability proofs for the two-node and cascade networks.

5.2.   Two-node network: Achievability proof for Theorem 2

The proof essentially follows from Lemma 5, with the following addition. If Alice receives a random sequence $X^n$ that is not $\delta$-typical, then she sends an arbitrary transmission. Otherwise, she encodes using the encoder in Lemma 5. Since $\Pr\left(X^n\in T_\delta^{(n)}(p_X)\right)$ tends to $1$ as $n\to\infty$, achievability for the two-node network follows.

5.3.   Cascade network: Achievability proof for Theorem 3

We use rate splitting, where Alice's message consists of two components $m_{1 \rightarrow 2}'$ and $m_{1 \rightarrow 2}''$, at rates $R_{1 \rightarrow 2}'$ and $R_{1 \rightarrow 2}''$, respectively, where $R_{1 \rightarrow 2} = R_{1 \rightarrow 2}'+R_{1 \rightarrow 2}''$.

Classical codebook construction Select $2\cdot 2^{nR_0}$ sequences $y^n(\ell')$, $z^n(\ell'')$, $\ell', \ell''\in \big[2^{nR_0}\big]$, independently at random, each i.i.d. according to $p_Y$ and $p_Z$, where

Assign each sequence with a bin index $b\left(y^n(\ell') \right)$ and $c\left(z^n(\ell'') \right)$, where $b:\mathcal{Y}^n\to [2^{nR_{1 \rightarrow 2}'}]$ and $c:\mathcal{Z}^n\to [2^{nR_{1 \rightarrow 2}''}]$, independently at random.

Alice's encoder As before, if Alice receives $x^n\notin T_\delta^{(n)}(p_X)$, she sends an arbitrary transmission. Otherwise, consider the classical encoding function $\mathcal{M}_{1\rightarrow2}:\mathcal{X}^n\to [2^{nR_{1 \rightarrow 2}'}]\times [2^{nR_{1 \rightarrow 2}''}]$ below. Given $x^n\in T_\delta^{(n)}(p_X)$, find an index pair $(\ell', \ell'')\in \big[2^{nR_0}\big]\times \big[2^{nR_0}\big]$ such that $(x^n, y^n(\ell'), z^n(\ell''))\in T_{2\delta}^{(n)}(p_{XYZ})$. If there is none, set $(\ell', \ell'') = (1, 1)$. If there is more than one, choose the first. Send the corresponding bin indices, i.e., $m_{1 \rightarrow 2}'(x^n) = b\left(y^n(\ell') \right)$ and $m_{1 \rightarrow 2}''(x^n) = c\left(z^n(\ell'') \right)$.

Then, prepare

Bob's encoder Bob receives $m_{1 \rightarrow 2} = (m_{1 \rightarrow 2}', m_{1 \rightarrow 2}'')$, and encodes in three stages:

(i) Given $m_{1 \rightarrow 2}''$, find an index $\hat{\ell}''\in \big[2^{nR_0}\big]$ such that

If there is none, set $\hat{\ell}'' = 1$. If there is more than one, choose the smallest. Send $m_{2 \rightarrow 3} = m_{1 \rightarrow 2}''$ to Charlie.

(ii) Now given $m_{1 \rightarrow 2}'$ and $\hat{\ell}''$, find an index $\hat{\ell}'\in \big[2^{nR_0}\big]$ such that

If there is none, set $\hat{\ell}' = 1$. If there is more than one, choose the smallest.

(iii) Prepare the state

where $\bar{Z}^n$ is an auxiliary system for Bob.

Charlie's encoder Given $m_{2 \rightarrow 3} = m_{1 \rightarrow 2}''$, find an index $\tilde{\ell}''\in \big[2^{nR_0}\big]$ such that

If there is none, set $\tilde{\ell}'' = 1$. If there is more than one, choose the smallest.

Prepare the state

This results in an average state,

with $y^n\equiv y^n(\hat{\ell}')$, $\bar{z}^n\equiv z^n(\hat{\ell}'')$, and $z^n\equiv z^n(\tilde{\ell}'')$. Based on the analysis in the proof of Lemma 5 (see Section 5.1), Alice, Bob, and Charlie achieve empirical coordination of $\sigma_{ABZC}$, provided that

which requires $R_{1 \rightarrow 2} = R_{1 \rightarrow 2}'+R_{1 \rightarrow 2}'' > I(X; YZ)$. □

6.   Converse part analysis

We now show the converse part of the coordination capacity theorems.

6.1.   Two-node network: Converse proof for Theorem 2

Consider the two-node network in Figure 3. Let $R_{1 \rightarrow 2}$ be an achievable rate for empirical coordination with a desired state $\omega_{AB}$. Then, there exists a sequence of $\left(2^{n{R_{1 \rightarrow 2}}}, n\right)$ empirical coordination codes that achieves an error,

where $\varepsilon_n$ tends to zero as $n\to\infty$. Now, suppose that Bob performs a projective measurement in a particular basis, say, $\{\left| {{y}} \right\rangle\}$. This yields a sequence $Y^n$ as the measurement outcome, with some distribution $p_{ Y^n|X^n}(y^n|x^n)$.

Then, consider the classical variables $X_J$ and $Y_J$, where $J$ is a uniformly distributed random variable, over the index set $[n]$, drawn independently of $X^n$, $Y^n$. Their joint distribution is

where $p_{X_i Y_i}$ is the marginal distribution of $p_X^n\times p_{Y^n|X^n}$. Based on (6.1), we have the following total variation bound:

where $\pi_{X Y}$ is defined as

for $(x, y)\in\mathcal{X}\times\mathcal{Y}$.

Next, consider that

where the third inequality holds by the data processing inequality and the following equalities by the chain rule. Since $X^n$ is i.i.d., it follows that $X_J$ and $J$ are statistically independent, hence,

Based on entropy continuity ^[106],

where $\alpha_n = -3\varepsilon_n \log(\varepsilon_n\left| {{\mathcal{X}}} \right|\left| {{\mathcal{Y}}} \right|)$ [107, Lemm. 2.7], which tends to zero as $n\to\infty$. This concludes the converse proof for the two-node network.

6.2.   Cascade network: Converse proof for Theorem 3

Consider the cascade network in Figure 4. If $(R_{1 \rightarrow 2}, R_{2 \rightarrow 3})$ is achievable, then there exists a sequence of $\left(2^{n{R_{1 \rightarrow 2}}}, 2^{n{R_{2 \rightarrow 3}}}, n\right)$ codes such

where $\varepsilon_n$ tends to zero as $n\to\infty$. Suppose that Bob and Charlie perform projective measurements in a particular basis, say, $\{\left| {{y}} \right\rangle\}$ and $\{\left| {{z}} \right\rangle\}$, respectively. This yields a sequence $(Y^n, Z^n)$ as the measurement outcomes, with some distribution $p_{ Y^n Z^n|X^n}(y^n, z^n|x^n)$.

Then, consider the classical variables $X_J$, $Y_J$, and $Z_J$, where $J$ is uniform over $[n]$, independent of $X^n$, $Y^n$, and $Z^n$. Their joint distribution is

where $p_{X_i Y_i Z_i}$ is the marginal distribution of $p_X^n\times p_{Y^n Z^n|X^n}$. By (6.8),

where

for $(x, y, z)\in\mathcal{X}\times\mathcal{Y}\times \mathcal{Z}$.

Consider Alice's communication rate, $R_{1 \rightarrow 2}$. Now, we may view the overall encoding operation of Bob and Charlie as a "black box" with $M_{1 \rightarrow 2}$ as input and $(B^n, C^n)$ as output, as shown in Figure 7. Thus,

based on the same arguments as in (6.5). Since $X_J$ and $J$ are statistically independent, we have

Following similar steps, we also have

Based on entropy continuity ^[106],

where $\alpha_n = -3\varepsilon_n \log(\varepsilon_n\left| {{\mathcal{X}}} \right|\left| {{\mathcal{Y}}} \right|\left| {{\mathcal{Z}}} \right|)$ [107, Lemma 2.7], which tends to zero as $n\to\infty$. □

7.   Summary and discussion

7.1.   Summary

We have introduced the notion of empirical coordination for quantum correlations. Quantum mechanics enables the calculation of probabilities for experimental outcomes, emphasizing statistical averages rather than detailed descriptions of individual events. Empirical coordination is thus a natural framework for quantum systems. Focusing on the cascade network, we established the optimal coordination rates, indicating the minimal resources for the empirical simulation of a quantum state. As we consider a network with classical communication links, superposition cannot be maintained, hence the quantum correlations are separable. This precludes entanglement. We have shown that providing the users with shared randomness, before communication begins, does not affect the optimal rates for empirical coordination (see Theorem 1). We began with the rate characterization for the basic two-node network (Theorem 2), and then generalized to a cascade network (Theorem 3). The special case of a network with an isolated node was addressed as well (see Corollary 4). The results generalize to other networks as our analysis includes a generic achievability scheme (see Lemma 5). Nonetheless, we do not claim to have solved all coordination scenarios or network topologies.

Next, we discuss the consequences of our results for quantum cooperative games.

7.2.   Game-theoretic implications

In many cooperative games, the payoff is associated with the correlation between the players. In the penny matching game, as introduced by Gossner et al. ^[108], Alice receives a classical sequence $x^n$ from an i.i.d source; thereafter, Alice and Bob produce sequences $a^n$ and $b^n$ that should be close to one another and to $x^n$ as well. In other words, Alice and Bob try to guess the source sequence one bit at a time. They gain a point for every bit they both guess correctly. Alice's action $a^n$ is referred to as a guess, even though she knows the original source sequence $x^n$. As it turns out, an optimal strategy could let Alice guess wrong, i.e., $a_i\neq x_i$, for some of the time ^[108]. Cuff and Zhao ^[42] analyzed a generalized version of the game through the classical two-node network. Here, we introduce a quantum version of the game.

Suppose that Alice receives a classical sequence $x^n$ from an i.i.d source $p_X$, as depicted in the two-node network 3. The quantum encoding of each user is viewed as the actions ^[109]. The game is specified by a payoff map

Given a joint strategy $\omega_{AB}$, the payoff to Alice and Bob is $G(\omega_{AB})$.

Suppose that Alice uses an empirical coordination code and sends $nR_{1 \rightarrow 2}$ bits to Bob. Furthermore, let $\mathrm{SEP}(\gamma)$ be the set of all separable strategies $\omega_{AB}$ for which Alice and Bob receive a payoff $\gamma = G(\omega_{AB})$. Alice and Bob can then reach an average payoff $\gamma\geq 0$ asymptotically, if and only if Alice can send a message to Bob at rate $R_{1 \rightarrow 2} > C_{\text{2-node}}(\omega)$ for some $\omega_{AB}\in \mathrm{SEP}(\gamma)$. The optimal rate $C_{\text{2-node}}(\omega)$ is characterized by Theorem 2.

7.3.   Strong coordination vs. empirical coordination

Analogously to the classical framework, we distinguish between two types of coordination tasks: Strong coordination and empirical coordination.

7.3.1.   Strong coordination

In the classical setting, strong coordination means that a statistician cannot reliably distinguish between the constructed sequence of actions $X_1^n, \ldots, X_K^n$, and random samples from the desired distribution ^[16]. This requires the joint distribution $p_{X_1^n \dots X_K^n}$ that the code induces to be arbitrarily close to the desired source $\pi\equiv \pi_{X_1 \dots X_K}$ in total variation distance. That is, strong coordination is achieved if there exists a code sequence such that

where $\pi^n$ denotes the i.i.d. distribution corresponding to the desired source.

Consider a network of $K$ quantum nodes, where the users have access to classical communication links with limited rates $R_{i, j}$ and may share common randomness (CR) at a limited rate $R_0$. We say that strong coordination is achieved if there exists a code sequence such that the joint state $\rho_{A_1^n \dots A_K^n}$ that is the code induces converges to the desired state, i.e.,

where $\omega\equiv \omega_{A_1 \dots A_K}$ is the desired state. In our previous work ^[60], we have considered strong coordination for classical-quantum (c-q) correlations with classical links.

7.3.2.   Empirical coordination

In the classical description, empirical coordination uses network communication in order to construct a sequence of actions that have an empirical joint distribution closely matching the desired distribution ^[16]. In this case, the error criterion sets a weaker requirement, given in terms of the joint type, i.e., the empirical distribution of the actions in the network. Formally, the requirement for empirical coordination is that for every $\varepsilon > 0$,

where $X_1^n, \dots, X_K^n$ are the encoded actions, and the probability is computed with respect to the CR distribution.

We say that empirical coordination is achieved in a quantum coordination network if there exists a sequence of coordination codes of length $n$, such that the time-average state $\frac{1}{n}\sum_{i = 1}^n\rho_{A_{1}(i) \dots A_{K}(i)}$ that is induced by the code converges in probability to the desired source $\omega_{A_1 \dots A_K}$, i.e.,

where $\omega\equiv \omega_{A_1 \dots A_K}$ is the desired state, and the probability is computed with respect to the CR distribution. We note that the quantum definition differs in nature from the classical one (c.f. (7.4) and (7.5)).

Remark 10. To see that strong coordination is indeed a stronger condition, note that by trace monotonicity, strong coordination implies $\left\| {{ \rho_{A_{1}(i) \dots A_{K}(i)}-\omega}} \right\|_1\to 0$ as $n\to\infty$, for every $i\in [n]$. Hence, by the triangle inequality,

which also tends to zero as $n\to\infty$.

We have discussed the justification and the physical interpretation of our coordination criterion in Subsection 3.2. Consider an observable represented by an Hermitian operator $\hat{O}$ on $\mathcal{H}_{A_1}\otimes\cdots \otimes \mathcal{H}_{A_K}$. In practice, statistics are collected by performing measurements on $n$ systems $(A_{1}(i), \ldots, A_{K}(i) \, :\; i\in [n])$. The expected value of the observable in the $i$th measurement is thus,

for $i\in [n]$. Roughly speaking, our coordination criterion guarantees that the empirical average is close to the expected value with respect to a desired state, i.e.,

with high probability.

7.4.   Common randomness does not help

We have shown that CR does not improve the coordination capacity. That is, if $R_{\ell\rightarrow j}$ is achievable with CR, it is also achievable without CR. We provide an intuitive explanation below. Suppose we use a coding scheme where the CR element is a sequence $U^n$, drawn from a memoryless source $p_U$ over $\mathcal{U}$, and each user encodes by a collection of maps $\{\mathcal{E}^{(u)}\}$, taking $u = U_i$ at time $i$. Then, this CR-assisted coding scheme can be replaced with a code based on a fixed agreed-upon sequence $\tilde{u}^n$ of type $\hat{P}_{\tilde{u}^n}\approx p_U$.

Since our coding scheme uses binning and not an encoder of the form $\mathcal{E}^{(u_i)}$, the description above is only a rough explanation to gain intuition.

7.5.   Applications

Recent advances in machine-to-machine communication ^[19] and the Internet of Things (IoT) ^[14] have raised interest in networks with various topologies ^[5]. These network topologies are relevant for various applications, such as distributed computing ^[110], autonomous vehicles ^[111], embedded sensors ^[112], players in a cooperative game ^[42], and quantum-enhanced IoT ^[114]. Coordination with classical links is motivated by quantum-enhanced IoT networks in which the communication links are classical ^{[113,114,115,116]}. The problem at hand is to find the optimal transmission rates required in order to establish a desired correlation. Empirical coordination also plays a role in quantum data compression ^[49,50,52]. The optimal compression rate for a quantum source of pure states was first established by Schumacher ^[117] for a quantum source of pure states (see also ^[118,119]). Empirical coordination is thus a natural framework for quantum systems.

Empirical coordination also plays a role in quantum data compression ^[49]. Barnum et al. ^[50] addressed a source of commuting density operators, and Kramer and Savari ^[36] developed a rate-distortion theory that unifies the visible and blind approaches (cf. ^[51] and ^[52]). Khanian and Winter have recently solved the general problem of a quantum source of mixed states (see also ^{[52,53,54,55,56,57,58]}). Rate distortion can be viewed as a special case of empirical coordination.

7.6.   Future directions

In another work by the authors ^[59], we have also considered strong coordination in a network with quantum links. This allows for the generation of multipartite entanglement and is closely related to tasks such as quantum channel/source simulation ^{[21,22,23,24,89,120]}, state merging ^[30,31], state redistribution ^[77,121], zero-communication state transformation ^[28,29], entanglement dilution ^{[32,33,34,98]}, randomness extraction ^[25,26], source coding ^{[35,36,37,38,39,40]}, and many others. An interesting avenue for future research is to study empirical coordination in such networks. There are many other coordination scenarios and network topologies that could be studied further, e.g., empirical coordination with entanglement assistance. Other interesting directions include the one-shot setting ($n = 1$) and coordination with two-way communication.

Author contributions

The authors made equal contributions.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgements

The authors would like to thank Ian George (National University of Singapore), Eric Chitambar (University of Illinois at Urbana-Champaign), and Marius Junge (University of Illinois at Urbana-Champaign) for useful discussions during the conference "Beyond IID in Information Theory, " held at the University of Illinois Urbana-Champaign from July 29 to August 2, 2024, supported by NSF Grant n. 2409823.

H. Natur and U. Pereg were supported by the Israel Science Foundation (ISF), Grants n. 939/23 and 2691/23, German-Israeli Project Cooperation (DIP) within the Deutsche Forschungsgemeinschaft (DFG) under Grant n. 2032991, Ollendorff Minerva Center (OMC) of the Technion n. 86160946, and Nevet Program of the Helen Diller Quantum Center at the Technion n. 2033613. U. Pereg was also supported by the Junior Faculty Program for Quantum Science and Technology of Israel Planning and Budgeting Committee of the Council for Higher Education (VATAT) under Grant 86636903, and the Chaya Career Advancement Chair through Grant n. 8776026.

Conflict of interest

The authors declare no conflict of interest.