Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.15656

Exact Sampling Under Campbell Cost via Rényi Channel Simulation Divergence

Yijun Fan, Aaron B. Wagner

Published Oct 11, 2026• 0 citations
arXivHTMLPDF

Abstract

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\Vert 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 $\frac{1}{2}\log n+O(1)$.

DOI
10.48550/arxiv.2610.15656

Related papers

Exact Channel Simulation under Exponential Cost

Spencer Hill, Fady Alajaji, Tamás Linder

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.

•Sep 17, 2025•0 citations

Adaptive Greedy Rejection Sampling

Gergely Flamich, Lucas Theis

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.

arXiv:2304.10407•IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•14 citations

Rényi Resolvability and Its Applications to the Wiretap Channel

Lei Yu, Vincent Y. F. Tan

The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in[0, 2] U {∞}) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to 1 as well as (lower and upper) bounds for the case when the same parameter is smaller than 1. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than 1, consistent with the traditional case where the Rényi parameter is equal to 1, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 1 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d. random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence. This tradeoff differs from the conventional setting when the leakage is measured by the traditional mutual information.

arXiv:1707.00810•IEEE Transactions on Information Theory•Dec 7, 2018•45 citations

Large Deviation Analysis for the Reverse Shannon Theorem

Shi-Bing Li, Ke Li, Lei Yu

We consider the problem of simulating a noisy channel using noiseless channels with unlimited shared randomness. This can be interpreted as the reverse problem of Shannon’s noisy channel coding theorem. In contrast to previous works, we employ Rényi divergence (with the parameter α ∈ [0,∞]) to measure the level of approximation, and we obtain the reverse Shannon theorem under this measure, which characterizes the Rényi simulation rate, the minimum communication rate required for the Rényi divergence vanishing asymptotically. Our derivation is done by a precise large-deviation analysis. When the communication rate is above the Rényi simulation rate, we provide a complete characterization of the convergence exponent for the Rényi divergence, called the reliability function. When the communication rate is below the Rényi simulation rate, we determine the linear increasing rate for the Rényi divergence, which implies the strong converse exponent for the order-α fidelity.

arXiv:2410.07984•IEEE Transactions on Information Theory•May 25, 2026•4 citations

Exact Channel Synthesis

Lei Yu, Vincent Y. F. Tan

We consider the exact channel synthesis problem. This problem concerns the determination of the minimum amount of information required to create exact correlation remotely when there is a certain rate of randomness shared by two terminals. This problem generalizes an existing approximate version, in which the generated joint distribution is required to be close to a target distribution under the total variation (TV) distance measure (instead being exactly equal to the target distribution). We provide single-letter inner and outer bounds on the admissible region of the shared randomness rate and the communication rate for the exact channel synthesis problem. These two bounds coincide for doubly symmetric binary sources. We observe that for such sources, the admissible rate region for exact channel synthesis is strictly included in that for the TV-approximate version. We also extend the exact and TV-approximate channel synthesis problems to sources with countably infinite alphabets and continuous sources; the latter includes Gaussian sources. As by-products, lemmas concerning soft-covering under Rényi divergence measures are derived.

arXiv:1810.13246•IEEE Transactions on Information Theory•Oct 1, 2019•20 citations

Strong Converse Exponent of Channel Interconversion

Aadil Oufkir, Yongsheng Yao, Mario Berta

Abstract In their seminal work, Bennett et al. [1] showed that, with sufficient shared randomness, one noisy channel can simulate another at a rate equal to the ratio of their capacities. We establish that when coding above this channel interconversion capacity, the exact strong converse exponent is characterized by a simple optimization involving the difference of the corresponding Rényi channel capacities with Hölder dual parameters. We further extend this result to the entanglement-assisted interconversion of classical–quantum channels, showing that the strong converse exponent is likewise determined by differences of sandwiched Rényi channel capacities. The converse bound is obtained by relaxing to non-signaling assisted codes and applying Hölder duality together with the data processing inequality for Rényi divergences. Achievability is proven by concatenating refined channel coding and simulation protocols that go beyond first-order capacities, attaining an exponentially small conversion error, remaining robust under small variations in the input distribution, and tolerating a sublinear gap between the conversion rates.

arXiv:2509.15200•Annales Henri Poincaré•Sep 17, 2026•2 citations
We study the communication cost of exact sampling under Campbell's exponential coding criterion. Given a target distribution PPP and a proposal distribution QQQ, the sender and receiver share i.i.d. QQQ-distributed samples, and the sender communicates an index so that the selected sample has distribution exactly PPP. We introduce a new information measure Rényi channel simulation divergence Rα(P∥Q)R_α(P\Vert Q)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 12log⁡n+O(1)\frac{1}{2}\log n+O(1)21​logn+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 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){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)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])\mathcal{O}\left( {{D_{KL}}\left[ {Q\left\| P \right.} \right]} \right)O(DKL​[Q∥P]) in this case.
The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in[0, 2] U {∞}) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to 1 as well as (lower and upper) bounds for the case when the same parameter is smaller than 1. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than 1, consistent with the traditional case where the Rényi parameter is equal to 1, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 1 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d. random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence. This tradeoff differs from the conventional setting when the leakage is measured by the traditional mutual information.
We consider the problem of simulating a noisy channel using noiseless channels with unlimited shared randomness. This can be interpreted as the reverse problem of Shannon’s noisy channel coding theorem. In contrast to previous works, we employ Rényi divergence (with the parameter α ∈ [0,∞]) to measure the level of approximation, and we obtain the reverse Shannon theorem under this measure, which characterizes the Rényi simulation rate, the minimum communication rate required for the Rényi divergence vanishing asymptotically. Our derivation is done by a precise large-deviation analysis. When the communication rate is above the Rényi simulation rate, we provide a complete characterization of the convergence exponent for the Rényi divergence, called the reliability function. When the communication rate is below the Rényi simulation rate, we determine the linear increasing rate for the Rényi divergence, which implies the strong converse exponent for the order-α fidelity.
We consider the exact channel synthesis problem. This problem concerns the determination of the minimum amount of information required to create exact correlation remotely when there is a certain rate of randomness shared by two terminals. This problem generalizes an existing approximate version, in which the generated joint distribution is required to be close to a target distribution under the total variation (TV) distance measure (instead being exactly equal to the target distribution). We provide single-letter inner and outer bounds on the admissible region of the shared randomness rate and the communication rate for the exact channel synthesis problem. These two bounds coincide for doubly symmetric binary sources. We observe that for such sources, the admissible rate region for exact channel synthesis is strictly included in that for the TV-approximate version. We also extend the exact and TV-approximate channel synthesis problems to sources with countably infinite alphabets and continuous sources; the latter includes Gaussian sources. As by-products, lemmas concerning soft-covering under Rényi divergence measures are derived.
Abstract In their seminal work, Bennett et al. [1] showed that, with sufficient shared randomness, one noisy channel can simulate another at a rate equal to the ratio of their capacities. We establish that when coding above this channel interconversion capacity, the exact strong converse exponent is characterized by a simple optimization involving the difference of the corresponding Rényi channel capacities with Hölder dual parameters. We further extend this result to the entanglement-assisted interconversion of classical–quantum channels, showing that the strong converse exponent is likewise determined by differences of sandwiched Rényi channel capacities. The converse bound is obtained by relaxing to non-signaling assisted codes and applying Hölder duality together with the data processing inequality for Rényi divergences. Achievability is proven by concatenating refined channel coding and simulation protocols that go beyond first-order capacities, attaining an exponentially small conversion error, remaining robust under small variations in the input distribution, and tolerating a sublinear gap between the conversion rates.