We consider channel simulation protocols between two communicating parties, Alice and Bob. First, Alice receives a target distribution Q, unknown to Bob. Then, she employs a shared coding distribution P to send the minimum amount of information to Bob so that he can simulate a single sample X ~ Q. For discrete distributions, Harsha et al. [1] developed a well-known channel simulation protocol – greedy rejection sampling (GRS) – with a bound of ${D_{{\text{KL}}}}\left[ {Q\left\| P \right.} \right] + 2\ln \left( {{D_{{\text{KL}}}}\left[ {Q\left\| P \right.} \right] + 1} \right) + \mathcal{O}\left( 1 \right)$ on the expected code-length of the protocol. In this paper, we extend the definition of GRS to general probability spaces and allow it to adapt its proposal distribution after each step. We call this new procedure Adaptive GRS (AGRS) and prove its correctness. Furthermore, we prove the surprising result that the expected runtime of GRS is exactly exp(D∞[Q║P]), where D∞[Q║P] denotes the Rényi ∞-divergence. We then apply AGRS to Gaussian channel simulation problems. We show that the expected runtime of GRS is infinite when averaged over target distributions and propose a solution that trades off a slight increase in the coding cost for a finite runtime. Finally, we describe a specific instance of AGRS for 1D Gaussian channels inspired by hybrid coding [2]. We conjecture and demonstrate empirically that the runtime of AGRS is $\mathcal{O}\left( {{D_{KL}}\left[ {Q\left\| P \right.} \right]} \right)$ in this case.
We consider channel simulation protocols between two communicating parties, Alice and Bob. First, Alice receives a target distribution Q, unknown to Bob. Then, she employs a shared coding distribution P to send the minimum amount of information to Bob so that he can simulate a single sample X ~ Q. For discrete distributions, Harsha et al. [1] developed a well-known channel simulation protocol – greedy rejection sampling (GRS) – with a bound of DKL[Q∥P]+2ln(DKL[Q∥P]+1)+O(1) on the expected code-length of the protocol. In this paper, we extend the definition of GRS to general probability spaces and allow it to adapt its proposal distribution after each step. We call this new procedure Adaptive GRS (AGRS) and prove its correctness. Furthermore, we prove the surprising result that the expected runtime of GRS is exactly exp(D∞[Q║P]), where D∞[Q║P] denotes the Rényi ∞-divergence. We then apply AGRS to Gaussian channel simulation problems. We show that the expected runtime of GRS is infinite when averaged over target distributions and propose a solution that trades off a slight increase in the coding cost for a finite runtime. Finally, we describe a specific instance of AGRS for 1D Gaussian channels inspired by hybrid coding [2]. We conjecture and demonstrate empirically that the runtime of AGRS is O(DKL[Q∥P]) in this case.
Let H be a finite dimensional Hilbert space and ρ, σ ∈ D(H) be quantum states in H \nsuch that S(ρ||σ) is finite. In this thesis, we consider the following communication task involving two parties Alice and Bob. Suppose that Alice is given a classical description of the states ρ and σ. Given an unlimited number of copies of an entangled state whose marginal on Bob’s side is σ, Alice’s goal is to help Bob output a single copy of the state ρ by sending a single message to Bob in a one-way LOCC (short for local operation and classical communication) protocol. We propose a class of one-way LOCC protocols for this task which we refer to as quantum rejection sampling protocols. Inspired by the classical rejection sampling protocol of Harsha, Jain, McAllester, and Radhakrishnan [25] for a similar classical communication task, we introduce the Greedy Quantum Rejection Sampler. We characterize the expected communication cost of the protocol in terms of max-relative entropy of ρ with respect to σ, in the case where the state ρ is a pure state and prove that the Greedy Quantum Rejection Sampler is an optimal quantum rejection sampling protocol in this case. We describe an optimal quantum rejection sampling protocol in terms of a semidefinite program and we find general lower bounds and upper bounds on the expected communication cost of the optimal protocol. We propose an LOCC compression protocol based on the Greedy Quantum Rejection Sampler protocol, for lossless compression of an arbitrary pure state quantum source in the visible compression model and we show an upper bound on the average length of this encoding. The upper bound is always less than or equal to the Shannon entropy of the quantum source and the gap between the two quantities can be arbitrary large. Finally, we introduce a high-entanglement deterministic exact protocol for remote preparation of an arbitrary ensemble of quantum states. Our protocol is based on a quantum rejection sampling protocol which uses a prefix-free encoding for communication of the messages. We establish an upper bound on the expected communication cost of this protocol for the worst case choice of the target state in terms of the max-information in Bob’s output register at the end of the protocol about Alice’s classical input register. Furthermore, this protocol can be used as a non-oblivious universal protocol for exact remote preparation of an arbitrary d-dimensional state at an expected communication cost of at most lg(d) +O (lg(lg(d))).
We study the communication cost of exact sampling under Campbell's exponential coding criterion. Given a target distribution P and a proposal distribution Q, the sender and receiver share i.i.d. Q-distributed samples, and the sender communicates an index so that the selected sample has distribution exactly P. We introduce a new information measure Rényi channel simulation divergence Rα(P∥Q), a Rényi generalization of the channel simulation divergence. We then show that it lower bounds the Campbell cost of every exact sampler and is achievable, via a new layered sampling scheme, within an additive constant depending only on the Campbell parameter. This yields a tighter one-shot characterization than previous bounds based on Rényi divergences of different orders. For i.i.d. product distributions, under suitable non-degeneracy and moment conditions, we further show that the gap beyond the leading Rényi-divergence term is 21logn+O(1).
In this work, we generalize results in exact channel simulation to an exponential communication cost, specifically to Campbell’s average codeword length L(t) of order t [1], and to Rényi’s entropy. In exact channel simulation, given a source of shared randomness, a sender wishes to communicate a message to the receiver so they can generate a sample from the conditional distribution PY |X. We lower bound the Campbell cost of channel simulation using any sampling algorithm, showing that it grows approximately as It+1(X; Y), where Iα is an appropriately defined α-mutual information of order α. Using the Poisson functional representation of Li and El Gamal [2], we prove an upper bound on L(t) whose leading α-mutual information term has order within ϵ of the lower bound. Our results reduce to the bounds of Harsha et al. [3] as t → 0. We also provide numerical examples for the additive white Gaussian noise channel, demonstrating that the upper and lower bounds are typically within 5-10 bits of each other.
We show how to sample exactly discrete probability distributions whose defining parameters are distributed among remote parties. For this purpose, von Neumann’s rejection algorithm is turned into a distributed sampling communication protocol. We study the expected number of bits communicated among the parties and also exhibit a trade-off between the number of rounds of the rejection algorithm and the number of bits transmitted in the initial phase. Finally, we apply remote sampling to the simulation of quantum entanglement in its essentially most general form possible, when an arbitrary finite number m of parties share systems of arbitrary finite dimensions on which they apply arbitrary measurements (not restricted to being projective measurements, but restricted to finitely many possible outcomes). In case the dimension of the systems and the number of possible outcomes per party are bounded by a constant, it suffices to communicate an expected O ( m 2 ) bits in order to simulate exactly the outcomes that these measurements would have produced on those systems.
A basic problem in information theory is the following: Let P = (X, Y) be an arbitrary distribution where the marginals X and Y are (potentially) correlated. Let Alice and Bob be two players where Alice gets samples {xi}i≥1 and Bob gets samples {yi}i≥i and for all i, (xi,yi) ∼ P. What joint distributions Q can be simulated by Alice and Bob without any interaction? Classical works in information theory by Gács-Körner and Wyner answer this question when at least one of P or Q is the distribution Eq (Eq is defined as uniform over the points (0, 0) and (1, 1)). However, other than this special case, the answer to this question is understood in very few cases. Recently, Ghazi, Kamath and Sudan showed that this problem is decidable for Q supported on {0, 1} × {0, 1}. We extend their result to Q supported on any finite alphabet. Moreover, we show that If Q can be simulated, our algorithm also provides a (non-interactive) simulation protocol. We rely on recent results in Gaussian geometry (by the authors) as well as a new smoothing argument inspired by the method of boosting from learning theory and potential function arguments from complexity theory and additive combinatorics.
LetXandYbe finite nonempty sets and(X,Y) a pair of random variables taking values inX?Y. We consider communication protocols between two parties,AliceandBob, for generatingXandY.Aliceis provided anx?Xgenerated according to the distribution ofX, and is required to send a message toBobin order to enable him to generatey?Y, whose distribution is the same as that ofY|X=x. Both parties have access to a shared random string generated in advance. LetT[X:Y] be the minimum (over all protocols) of the expected number of bitsAliceneeds to transmit to achieve this. We show that I[X:Y] ? T[X:Y] ? I [X:Y] + 2 log2(I[X:Y]+ O(1). We also consider the worst case communication required for this problem, where we seek to minimize the average number of bitsAlicemust transmit for the worst casex?X. We show that the communication required in this case is related to the capacityC(E) of the channelE, derived from(X,Y) , that mapsx?Xto the distribution ofY|X=x. We also show that the required communicationT(E) satisfiesC(E) ?T(E) ?C(E) + 2 log2(C(E)+1) +O(1). Using the first result, we derive a direct-sum theorem in communication complexity that substantially improves the previous such result shown by Jain, Radhakrishnan, and Sen [In Proc. 30th International Colloquium of Automata, Languages and Programming (ICALP), ser. Lecture Notes in Computer Science, vol. 2719. 2003, pp. 300-315]. These results are obtained by employing a rejection sampling procedure that relates the relative entropy between two distributions to the communication complexity of generating one distribution from the other.