Remote Sampling with Applications to General Entanglement Simulation

Let $\mathbb{X}$ be a nonempty finite set containing n elements and $p={\left(p_x\right)}_{x\in \mathbb{X}}$ be a probability vector parameterized by some vector $\theta =({\theta }_1,\dots ,{\theta }_m)\in {\mathsf{\Theta }}^m$ for an integer $m\ge 2$. For instance, the set $\mathsf{\Theta }$ can be the real interval $[0,1]$ or the set of Hermitian semi-definite positive matrices as it is the case for the simulation of entanglement. The probability vector p defines a random variable X such that $\mathbf{P}\{X=x\}\stackrel{\mathrm{def}}{=}{p}_x$ for $x\in \mathbb{X}$. To sample exactly the probability vector p means to produce an output x such that $\mathbf{P}\{X=x\}=p_x$. The problem of sampling probability distributions has been studied and is still studied extensively within different random and computational models. Here, we are interested in sampling exactly a discrete distribution whose defining parameters are distributed among m different parties. The ${\theta }_i$’s for $i\in \{1,\dots ,m\}$ are stored in m different locations where the ith party holds ${\theta }_i$. In general, any communication topology between the parties would be allowed, but, in this work, we concentrate for simplicity on a model in which we add a designated party known as the leader, whereas the m other parties are known as the custodians because each of them is sole keeper of the corresponding parameter $\theta$—hence there are $m+1$ parties in total. The leader communicates in both directions with the custodians, who do not communicate among themselves. Allowing inter-custodian communication would not improve the communication efficiency of our scheme and can, at best, halve the number of bits communicated in any protocol. However, it could dramatically improve the sampling time in a realistic model in which each party is limited to sending and receiving a fixed number of bits at any given time step, as demonstrated in our previous work [1] concerning a special case of the problem considered here. The communication scheme is illustrated in Figure 1.

It may seem paradoxical that the leader can sample exactly the probability vector p with a finite expected number of bits sent by the custodians, who may hold continuous parameters that define p. However, this counterintuitive possibility has been known to be achievable for more than a quarter-century in earlier work on the simulation of quantum entanglement by classical communication, starting with Refs. [2,3,4,5,6,7], continuing with Refs. [8,9,10,11,12,13,14], etc. for the bipartite case and Refs. [15,16,17], etc. for the multipartite case, and culminating with our own Ref. [1].

Our protocol to sample remotely a given probability vector is presented in Section 2. For this purpose, the von Neumann rejection algorithm [18] is modified to produce an output $x\in \mathbb{X}$ with exact probability $p_x$ using mere approximations of those probabilities, which are computed based on partial knowledge of the parameters transmitted on demand by the custodians to the leader. For the sake of simplicity, and to concentrate on the new techniques, we assume initially that algebraic operations on real numbers can be carried out with infinite precision and that continuous random variables can be sampled. Later, in Section 4, we build on techniques developed in Ref. [1] to obtain exact sampling in a realistic scenario in which all computations are performed with finite precision and the only source of randomness comes from flipping independent fair coins.

In the intervening Section 3, we study our motivating application of remote sampling, which is the simulation of quantum entanglement using classical resources and classical communication. Readers who may not be interested in quantum information can still benefit from Section 2 and most of Section 4, which make no reference to quantum theory in order to explain our general remote sampling strategies. A special case of remote sampling has been used by the authors [1], in which the aim was to sample a specific probability distribution appearing often in quantum information science, namely the m-partite Greenberger–Horne–Zeilinger (GHZ) distribution [19]. More generally, consider a quantum system of dimension $d=d_1\cdots d_m$ represented by a density matrix $\rho$ known by the leader (surprisingly, the custodians have no need to know $\rho$). Suppose that there are m generalized measurements (povms) acting on quantum systems of dimensions $d_1,\dots ,d_m$ whose possible outcomes lie in sets ${\mathbb{X}}_1,\dots ,{\mathbb{X}}_m$ of cardinality $n_1,\dots ,n_m$, respectively. Each custodian knows one and only one of the povms and nothing else about the others. The leader does not know initially any information about any of the povms. Suppose in addition that the leader can generate independent identically distributed uniform random variables on the real interval $[0,1]$. We show how to generate a random vector $X=(X_1,\dots ,X_m)\in \mathbb{X}={\mathbb{X}}_1\times \dots \times {\mathbb{X}}_m$ sampled from the exact joint probability distribution that would be obtained if each custodian i had the ith share of $\rho$ (of dimension $d_i$) and measured it according to the ith povm, producing outcome $x_i\in {\mathbb{X}}_i$. This task is defined formally in Section 3, where we prove that the total expected number of bits transmitted between the leader and the custodians using remote sampling is $O\left(m^2\right)$ provided all the $d_i$’s and $n_i$’s are bounded by some constant. The exact formula, involving m as well as the $d_i$’s and $n_i$’s, is given as Equation (14) in Section 3, where d and n denote the product of the $d_i$’s and the $n_i$’s, respectively. In Section 4, we obtain the same asymptotic result in the more realistic scenario in which the only source of randomness comes from independent identically distributed uniform random bits. This result subsumes that of Ref. [1] since all $d_i$’s and $n_i$’s are equal to 2 for projective measurements on individual qubits of the m-partite GHZ state.

As explained in the Introduction, we show how to sample remotely a discrete probability vector $p={\left(p_x\right)}_{x\in \mathbb{X}}$. The task of sampling is carried by a leader ignorant of some parameters $\theta =({\theta }_1,\dots ,{\theta }_m)$ that come in the definition of the probability vector, where each ${\theta }_i$ is known by the ith custodian only, with whom the leader can communicate. We strive to minimize the amount of communication required to achieve this task.

To solve our conundrum, we modify the von Neumann rejection algorithm [18,20]. Before explaining those modifications, let us review the original algorithm. Let $q={\left(q_x\right)}_{x\in \mathbb{X}}$ be a probability vector that we know how to sample on the same set $\mathbb{X}$, and let $C\ge 1$ be such that $p_x\le C{q}_x$ for all $x\in \mathbb{X}$. The classical von Neumann rejection algorithm is shown as Algorithm 1. It is well known that the expected number of times round the repeat loop is exactly C.

If only partial knowledge about the parameters defining p is known, it would seem that the condition in line 4 cannot be decided. Nevertheless, the strategy is to build a sequence of increasingly accurate approximations that converge to the left and right sides of the test. As explained below, the number of bits transmitted depends on the number of bits needed to compute q, and on the accuracy in p required to accept or reject. This task can be achieved either in the random bit model, in which only i.i.d. random bits are generated, or in the less realistic uniform model, in which uniform continuous random variables are needed. The random bit model was originally suggested by von Neumann [18], but only later given this name and formalized by Knuth and Yao [21]. In this section, we concentrate for simplicity on the uniform model, leaving the more practical random bit model for Section 4.

Note that we assume without loss of generality that approximations of probabilities are always constrained to be real numbers between 0 and 1, which can be enforced by snapping any out-of-bound approximation (even if it is a complex number) to the closest valid value.

Consider an integer $t_0>0$ to be determined later. Our strategy is for the leader to compute the probability vector $q={\left(q_x\right)}_{x\in \mathbb{X}}$ defined below, based on $t_0$-bit approximations $p_x\left(t_0\right)$ of the probabilities $p_x$ for each $x\in \mathbb{X}$. For this purpose, the leader receives sufficient information from the custodians to build the entire vector q at the outset of the protocol. This makes q the “easy-to-sample” distribution required in von Neumann’s technique, which is easy not from a computational viewpoint, but in the sense that no further communication is required for the leader to sample it as many times as needed.

Let and Noting that ${\sum }_x{q}_x=1$, these $q_x$ define a proper probability vector $q={\left(q_x\right)}_{x\in \mathbb{X}}$. Using the definition of a t-bit approximation and the definition of $q_x$ from Equation (2), we have that Taking the sum over the possible values for x and recalling that set $\mathbb{X}$ is of cardinality n,

Consider any $x\in \mathbb{X}$ sampled according to q and U sampled uniformly in $[0,1]$ as in lines 2 and 3 of Algorithm 1. Should x be accepted because $UC{q}_x\le p_x$, this can be certified by any t-bit approximation $p_x\left(t\right)$ of $p_x$ such that $UC{q}_x\le p_x\left(t\right)-2^{-t}$ for some positive integer t since $p_x\left(t\right)\le p_x+2^{-t}$. Conversely, any integer t such that $UC{q}_x>p_x\left(t\right)+2^{-t}$ certifies that x should be rejected because it implies that $UC{q}_x>p_x$ since $p_x\left(t\right)\ge p_x-2^{-t}$. On the other hand, no decision can be made concerning $UC{q}_x$ versus $p_x$ if $-2^{-t}<UC{q}_x-p_x\left(t\right)\le 2^{-t}$. It follows that one can modify Algorithm 1 above into Algorithm 2 below, in which a sufficiently precise approximation of $p_x$ suffices to make the correct decision to accept or reject an x sampled according to distribution q. A well-chosen value of $t_0$ must be input into this algorithm, as discussed later.

Let S be the random variable that represents the number of times variable X is sampled according to q at line 3, and let $T_i$ be the random variable that represents the value of variable T upon termination of the ith instance of the for loop starting at line 5, for $i\in \{1,\dots ,S\}$. The random variables $T_i$ are independently and identically distributed as the random variable T in Theorem 1 and the expected value of S is C. Let $X_1,\dots ,X_S$ be the random variables chosen at successive passes at line 3, so that $X_1,\dots ,X_{S-1}$ are rejected, whereas $X_S$ is returned as the final result of the algorithm.

To analyse the communication complexity of Algorithm 2, we introduce function ${\gamma }_x\left(t\right)$ for each $x\in \mathbb{X}$ and $t>t_0$, which denotes the incremental number of bits that the leader must receive from the custodians in order to compute $p_x\left(t\right)$, taking account of the information that may already be available if he had previously computed $p_x(t-1)$. For completeness, we include in ${\gamma }_x\left(t\right)$ the cost of the communication required for the leader to request more information from the custodians. We also introduce function $\delta \left(t\right)$ for $t\ge 0$, which denotes the number of bits that the leader must receive from the custodians in order to compute $p_x\left(t\right)$ for all $x\in \mathbb{X}$ in a “simultaneous” manner. Note that it could be much less expensive to compute those n values than n times the cost of computing any single one of them because some of the parameters held by the custodians may be relevant to more than one of the $p_x$’s. The total number of bits communicated in order to implement Algorithm 2 is therefore given by random variable For simplicity, let us define function $\gamma \left(t\right)\stackrel{\mathrm{def}}{=}{max}_{x\in \mathbb{X}}{\gamma }_x\left(t\right)$. We then have whose expectation, according to Wald’s identity, is Assuming the value of $\gamma \left(t\right)$ is upper-bounded by some $\gamma$, because $\mathbf{E}\left(S\right)=C$ and using Equations (4) and (3).

Depending on the specific application, which determines $\gamma$ and function $\delta \left(t\right)$, Equation (7) is key to a trade-off that can lead to an optimal choice of $t_0$ since a larger $t_0$ decreases $2^{1-t_0}$ but is likely to increase $\delta \left(t_0\right)$. The value of $\gamma$ may play a rôle in the balance. The next section, in which we consider the simulation of quantum entanglement by classical communication, gives an example of this trade-off in action.

Before introducing the simulation of entanglement, let us establish some notation and mention the mathematical objects that we shall need. It is assumed that the reader is familiar with linear algebra, in particular the notion of a semi-definite positive matrix, Hermitian matrix, trace of a matrix, tensor product, etc. For a discussion about the probabilistic and statistical nature of quantum theory, see Ref. [22]. For convenience, we use $\left[n\right]$ to denote the set $\{1,2,\dots ,n\}$ for any integer n.

Consider integers $m,d_1,d_2,\dots ,d_m,n_1,n_2,\dots ,n_m$, all greater than or equal to 2. Define $d={\prod }_{i=1}^m{d}_i$ and $n={\prod }_{i=1}^m{n}_i$. Let $\rho$ be a $d\times d$ density matrix. Recall that any density matrix is Hermitian, semi-definite positive and unit-trace, which implies that its diagonal elements are real numbers between 0 and 1. For each $i\in \left[m\right]$ and $j\in \left[n_i\right]$, let $M_{ij}$ be a $d_i\times d_i$ Hermitian semi-definite positive matrix such that where $I_{d_i}$ is the $d_i\times d_i$ identity matrix. In other words, each set ${\left\{M_{ij}\right\}}_{j\in \left[n_i\right]}$ is a povm (positive-operator valued measure) [22].

As introduced in Section 1, we consider one leader and m custodians. The leader knows density matrix $\rho$ and the ith custodian knows the ith povm, meaning that he knows the matrices $M_{ij}$ for all $j\in \left[n_i\right]$. If a physical system of dimension d in state $\rho$ were shared between the custodians, in the sense that the ith custodian had possession of the ith subsystem of dimension $d_i$, each custodian could perform locally his assigned povm and output the outcome, an integer between 1 and $n_i$. The joint output would belong to $\mathbb{X}\stackrel{\mathrm{def}}{=}\left[n_1\right]\times \left[n_2\right]\times \cdots \times \left[n_m\right]$, a set of cardinality n, sampled according to the probability distribution stipulated by the laws of quantum theory, which we review below.

Our task is to sample $\mathbb{X}$ with the exact same probability distribution even though there is no physical system in state $\rho$ available to the custodians, and in fact all parties considered are purely classical! We know from Bell’s Theorem [23] that this task is impossible in general without communication, even when $m=2$, and our goal is to minimize the amount of communication required to achieve it. Special cases of this problem have been studied extensively for expected [1,2,4,5,6], etc. and worst-case [3,8], etc. communication complexity, but here we solve it in its essentially most general setting, albeit only in the expected sense. For this purpose, the leader will centralize the operations while requesting as little information as possible from the custodians on their assigned povms. Once the leader has successfully sampled $X=(X_1,\dots ,X_m)$, he transmits each $X_i$ to the ith custodian, who can then output it as would have been the case had quantum measurements actually taken place.

We now review the probability distribution $\mathbb{X}$ that we need to sample, according to quantum theory. For each vector $x=(x_1,\dots ,x_m)\in \mathbb{X}$, let $M_x$ be the $d\times d$ tensor product of matrices $M_{i{x}_i}$ for each $i\in \left[m\right]$: The set ${\left\{M_x\right\}}_{x\in \mathbb{X}}$ forms a global povm of dimension d, which applied to density matrix $\rho$ defines a joint probability vector on $\mathbb{X}$. The probability $p_x$ of obtaining any $x=(x_1,\dots ,x_m)\in \mathbb{X}$ is given by

For a matrix A of size $s\times s$ and any pair of indices r and c between 0 and $s-1$, we use ${\left(A\right)}_{rc}$ to denote the entry of A located in the $r^{\mathrm{th}}$ row and $c^{\mathrm{th}}$ column. Matrix indices start at 0 rather than 1 to facilitate Fact 2 below. We now state various facts for which we provide cursory justifications since they follow from elementary linear algebra and quantum theory, or they are lifted from previous work.

After all these preliminaries, we are now ready to adapt the general template of Algorithm 2 to our entanglement-simulation conundrum, yielding Algorithm 3. We postpone the choice of $t_0$ until after the communication complexity analysis of this new algorithm.

To analyse the expected number of bits of communication required by this algorithm, we apply Equation (7) from Section 2 after defining explicitly the cost parameters $\delta \left(t_0\right)$ for the initial computation of $p_x\left(t_0\right)$ for all $x\in \mathbb{X}$ at lines 3 and 4, and $\gamma$ for the upgrade from a specific $p_X\left(t\right)$ to $p_X(t+1)$ at lines 19 and 20. For simplicity, we shall ignore the negligible amount of communication entailed at line 1 (which is ${\sum }_{i=1}^m\lceil lg{n}_i\rceil \le m+lgn$ bits), line 2 ($\lceil lg{t}_0\rceil$ bits), line 10 (also ${\sum }_{i=1}^m\lceil lg{n}_i\rceil$ bits, but repeated $\mathbf{E}\left(S\right)\le 1+2^{1-t_0}n$ times) and line 25 (m bits) because they are not taken into account in Equation (7) since they are absent from Algorithm 2. If we counted it all, this would add $O((1+2^{1-t_0}n)lgn+lg{t}_0)$ bits to Equation (13) below, which would be less than $10lgn$ bits added to Equation (14), with no effect at all on Equation (15).

According to Fact 13, The cost of line 19 is very modest because we use truncations rather than general approximations in line 3 for the leader to compute $p_x\left(t_0\right)$ for all $x\in \mathbb{X}$. Indeed, it suffices to obtain a single additional bit of precision in the real and imaginary parts of each entry defining matrix $M_{i{X}_i}$ from each custodian $i\in \left[m\right]$. The cost of this update is simply bits of communication, where the addition of m is to account for the leader needing to request new bits from the custodians. This is a nice example of what we meant by “it could be that bits previously communicated can be reused” in line 11 of Algorithm 2.

Putting it all together in Equation (7), the total expected number of bits communicated in Algorithm 3 in order to sample exactly according to the quantum probability distribution is

We are finally in a position to choose the value of parameter $t_0$. First note that $n={\prod }_{i=1}^m{n}_i\ge 2^m$. Therefore, any constant choice of $t_0$ will entail an expected amount of communication that is exponential in m because of the right-hand term in Equation (13). At the other extreme, choosing $t_0=n$ would also entail an expected amount of communication that is exponential in m, this time because of the left-hand term in Equation (13). A good compromise is to choose $t_0=\lceil lgn\rceil$, which results in $1\le C\le 3$ according to Equation (3), because in that case $2^{t_0}\ge n$ and therefore so that Equation (13) becomes In case all the $n_i$’s and $d_i$’s are upper-bounded by some constant $\xi$, we have that $n={\prod }_{i=1}^m{n}_i\le {\xi }^m$, hence $lgn\le mlg\xi$, similarly $lgd\le mlg\xi$, and also ${\sum }_{i=1}^m{n}_i{d}_i^2\le m{\xi }^3$. It follows that which is on the order of $m^2$, thus matching with our most general method the result that was already known for the very specific case of simulating the quantum m-partite GHZ distribution [1].

In practice, we cannot work with continuous random variables since our computers have finite storage capacities and finite precision arithmetic. Furthermore, the generation of uniform continuous random variables does not make sense computationally speaking and we must adapt Algorithms 2 and 3 to work in a finite world.

For this purpose, recall that U is a uniform continuous random variable on $[0,1]$ used in all the algorithms seen so far. For each $i\ge 1$, let $U_i$ denote the ith bit in the binary expansion of U, so that We acknowledge the fact that the $U_i$’s are not uniquely defined in case $U=j/2^k$ for integers $k>0$ and $0<j<2^k$, but we only mention this phenomenon to ignore it since it occurs with probability 0 when U is uniformly distributed on $[0,1]$. We denote the t-bit truncation of U by $U\left[t\right]$:

For all $t\ge 1$, we have that

We modify Algorithm 2 into Algorithm 4 as follows, leaving to the reader the corresponding modification of Algorithm 3, thus yielding a practical protocol for the simulation of general entanglement under arbitrary measurements.

The similarity between Theorems 1 and 2 means that there is no significant additional cost in the amount of communication required to achieve remote sampling in the random bit model. i.e., if we consider a realistic scenario in which the only source of randomness comes from i.i.d. unbiased bits, compared to an unrealistic scenario in which continuous random variables can be drawn. For instance, the reasoning that led to Equation (7) applies mutatis mutandis to conclude that the expected number Z of bits that needs to be communicated to achieve remote sampling in the random bit model is where $\delta$ and $\gamma$ have the same meaning as in Section 2.

If we use the random bit approach for the general simulation of quantum entanglement studied in Section 3, choosing $t_0=\lceil lgn\rceil$ again, Equation (14) becomes which reduces to the identical in case all the $n_i$’s and $d_i$’s are upper-bounded by some constant $\xi$, which again is on the order of $m^2$.