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:2604.23076

Rejection Sampling is Optimal for Relative Entropy Coding

Spencer Hill, Fady Alajaji, Tamás Linder, Gergely Flamich

Published Apr 25, 2026• 0 citations
arXivHTMLPDF

Abstract

In relative entropy coding, a sender aims to design a stochastic code such that, on input $X \sim P_X$, the receiver can generate a sample $Y \sim P_{Y \mid X}$. It is a standard result that (1) this requires at least $I(X; Y)$ bits, (2) the lower bound is achievable within a logarithmic gap, and (3) this gap cannot be reduced in general. The necessity of the gap suggests that the mutual information is not the correct information measure to quantify the rate of relative entropy coding. A potential alternative emerged in the work of Flamich et al. (2025), who proved a tighter lower bound of $I_F(X \to Y)$, a quantity we call the functional information. In this paper, we construct the ring toss code, an encoding method for rejection sampling which uses at most $I_F(X \to Y) + \log e$ bits, hence obtaining a tight one-shot characterization of relative entropy coding. For the trivial channel $Y = X$, our result recovers the noiseless source coding theorem within a small constant. For a general channel, it implies that the classical mutual information lower bound is achievable within $\log(I(X; Y) + 1) + 2.45$ bits in general and within $1.45$ bits for singular channels, which are both the tightest bounds of their kind to date. Moreover, our one-shot result also recovers Sriramu and Wagner's asymptotic results on the second-order redundancy of relative entropy codes.

DOI
10.48550/arxiv.2604.23076

Related papers

Information-Theoretic Bounds on Entropy Generation in Quantum Channels

Tibor Svoboda, Milos Bartos, Igor Novotny

Landauer's principle sets a fundamental lower bound on the entropy generated when information is erased, but the tightness of that bound for realistic, noisy quantum channels used in physical information-processing devices remains only partially characterized. We derive and numerically test information-theoretic lower bounds on entropy generation for three canonical quantum channel models, the amplitude-damping channel, the depolarizing channel, and the dephasing channel, expressing each bound in terms of the channel's quantum capacity and its deviation from unitarity, and compare these bounds against directly computed von Neumann entropy production across 1,200 randomly sampled input states per channel type at 22 noise-strength settings spanning damping/depolarizing/dephasing parameters from 0.02 to 0.90. Across all three channel families, measured entropy production exceeded the derived lower bound in every one of the 3,600 trials, with a median excess (bound tightness gap) of 0.087 bits and an interquartile range of 0.041 to 0.156 bits, confirming the bounds are valid but revealing systematic looseness that varies by channel type. The amplitude-damping channel showed the tightest bound performance, with a median gap of 0.052 bits at low-to-moderate damping strength (gamma < 0.4), while the depolarizing channel showed the loosest bound, with a median gap of 0.134 bits across the full noise range, a 2.6-fold difference attributable to the depolarizing channel's more uniform mixing of the Bloch sphere. Gap magnitude correlated strongly with channel noise strength (Spearman rho = 0.81, p < 0.001 pooled across channel types), growing roughly threefold from the lowest to highest noise settings tested, indicating the bound is tightest in the near-unitary, low-decoherence regime relevant to near-term quantum error correction. A correction term incorporating the channel's output purity reduced the median gap to 0.029 bits (a 67% reduction) without requiring knowledge of the specific input state, at the cost of a more complex closed-form expression requiring numerical evaluation of the channel's Choi matrix eigenvalues. These results quantify, for the first time across three major channel families on a common footing, how much headroom exists between an easily computable information-theoretic bound and actual thermodynamic entropy cost, information directly relevant to estimating the true energetic overhead of near-term noisy quantum information processing.

•Dec 13, 2022•0 citations

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

Yijun Fan, Aaron B. Wagner

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)$.

arXiv:2610.15656•Oct 11, 2026•0 citations

One-shot and asymptotic classical capacity in general physical theories

Shintaro Minagawa, Hayato Arai

With the recent development of quantum information theory, some attempts have been made to construct information theory beyond quantum theory. Here, we consider hypothesis-testing relative entropy and one-shot classical capacity, that is, the optimal rate of classical information transmitted by using a single channel under the constraint of a certain error probability, in general physical theories where states and measurements are operationally defined. Then we obtain the upper bound of the one-shot classical capacity by generalizing the method given by Wang and Renner [Phys. Rev. Lett. 108, 200501 (2012)]. Also, we derive the lower bound of the capacity by showing the existence of a good code that can transmit classical information with a certain error probability. Applying the above two bounds, we prove the asymptotic equivalence between classical capacity and hypothesis-testing relative entropy in any general physical theory.

arXiv:2303.04138•Physical Review A•Jun 11, 2024•0 citations

Quantum soft covering with relative entropy criterion

Xingyi He, S. Sandeep Pradhan

In this work, we propose a soft covering problem for fully quantum channels using relative entropy as a criterion for operator closeness. We establish covering lemmas by deriving one-shot bounds on the achievable rates in terms of smooth min-entropies. In the asymptotic regime, we show that the infimum of the rate, defined as the logarithm of the minimum rank of the encoded input state, is given by the minimal coherent information between the reference and output systems that yields the target output state. Furthermore, we present a one-shot quantum decoupling theorem that also employs a relative-entropy criterion. Due to the Pinsker inequality, our one-shot results based on the relative-entropy criterion are tighter than the corresponding results based on the trace norm considered in the literature. In addition, we establish achievable error exponents and second-order rates for quantum soft covering under both trace-distance and relative-entropy criteria.

arXiv:2402.11112•International Journal of Quantum Information•Jun 16, 2026•0 citations

Bitwise Quantum Min-Entropy Sampling and New Lower Bounds for Random Access Codes

Jürg Wullschleger

Min-entropy sampling gives a bound on the min-entropy of a randomly chosen subset of a string, given a bound on the min-entropy of the whole string. König and Renner showed a min-entropy sampling theorem that holds relative to quantum knowledge. Their result achieves the optimal rate, but it can only be applied if the bits are sampled in blocks, and only gives weak bounds for the non-smooth min-entropy. We give two new quantum min-entropy sampling theorems that do not have the above weaknesses. The first theorem shows that the result by König and Renner also applies to bitwise sampling, and the second theorem gives a strong bound for the non-smooth min-entropy. Our results imply a new lower bound for k-out-of-n random access codes: while previous results by Ben-Aroya, Regev, and de Wolf showed that the decoding probability is exponentially small in k if the storage rate is smaller than 0.7, our results imply that this holds for any storage rate strictly smaller than 1, which is optimal.

arXiv:1012.2291•Dec 10, 2010•5 citations

Rethinking quantum smooth entropies: Tight one-shot analysis of quantum privacy amplification

Bartosz Regula, Marco Tomamichel

We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.

quant-pharXiv:2603.04493•Mar 6, 2026•0 citations
In relative entropy coding, a sender aims to design a stochastic code such that, on input X∼PXX \sim P_XX∼PX​, the receiver can generate a sample Y∼PY∣XY \sim P_{Y \mid X}Y∼PY∣X​. It is a standard result that (1) this requires at least I(X;Y)I(X; Y)I(X;Y) bits, (2) the lower bound is achievable within a logarithmic gap, and (3) this gap cannot be reduced in general. The necessity of the gap suggests that the mutual information is not the correct information measure to quantify the rate of relative entropy coding. A potential alternative emerged in the work of Flamich et al. (2025), who proved a tighter lower bound of IF(X→Y)I_F(X \to Y)IF​(X→Y), a quantity we call the functional information. In this paper, we construct the ring toss code, an encoding method for rejection sampling which uses at most IF(X→Y)+log⁡eI_F(X \to Y) + \log eIF​(X→Y)+loge bits, hence obtaining a tight one-shot characterization of relative entropy coding. For the trivial channel Y=XY = XY=X, our result recovers the noiseless source coding theorem within a small constant. For a general channel, it implies that the classical mutual information lower bound is achievable within log⁡(I(X;Y)+1)+2.45\log(I(X; Y) + 1) + 2.45log(I(X;Y)+1)+2.45 bits in general and within 1.451.451.45 bits for singular channels, which are both the tightest bounds of their kind to date. Moreover, our one-shot result also recovers Sriramu and Wagner's asymptotic results on the second-order redundancy of relative entropy codes.
Landauer's principle sets a fundamental lower bound on the entropy generated when information is erased, but the tightness of that bound for realistic, noisy quantum channels used in physical information-processing devices remains only partially characterized. We derive and numerically test information-theoretic lower bounds on entropy generation for three canonical quantum channel models, the amplitude-damping channel, the depolarizing channel, and the dephasing channel, expressing each bound in terms of the channel's quantum capacity and its deviation from unitarity, and compare these bounds against directly computed von Neumann entropy production across 1,200 randomly sampled input states per channel type at 22 noise-strength settings spanning damping/depolarizing/dephasing parameters from 0.02 to 0.90. Across all three channel families, measured entropy production exceeded the derived lower bound in every one of the 3,600 trials, with a median excess (bound tightness gap) of 0.087 bits and an interquartile range of 0.041 to 0.156 bits, confirming the bounds are valid but revealing systematic looseness that varies by channel type. The amplitude-damping channel showed the tightest bound performance, with a median gap of 0.052 bits at low-to-moderate damping strength (gamma < 0.4), while the depolarizing channel showed the loosest bound, with a median gap of 0.134 bits across the full noise range, a 2.6-fold difference attributable to the depolarizing channel's more uniform mixing of the Bloch sphere. Gap magnitude correlated strongly with channel noise strength (Spearman rho = 0.81, p < 0.001 pooled across channel types), growing roughly threefold from the lowest to highest noise settings tested, indicating the bound is tightest in the near-unitary, low-decoherence regime relevant to near-term quantum error correction. A correction term incorporating the channel's output purity reduced the median gap to 0.029 bits (a 67% reduction) without requiring knowledge of the specific input state, at the cost of a more complex closed-form expression requiring numerical evaluation of the channel's Choi matrix eigenvalues. These results quantify, for the first time across three major channel families on a common footing, how much headroom exists between an easily computable information-theoretic bound and actual thermodynamic entropy cost, information directly relevant to estimating the true energetic overhead of near-term noisy quantum information processing.
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).
With the recent development of quantum information theory, some attempts have been made to construct information theory beyond quantum theory. Here, we consider hypothesis-testing relative entropy and one-shot classical capacity, that is, the optimal rate of classical information transmitted by using a single channel under the constraint of a certain error probability, in general physical theories where states and measurements are operationally defined. Then we obtain the upper bound of the one-shot classical capacity by generalizing the method given by Wang and Renner [Phys. Rev. Lett. 108, 200501 (2012)]. Also, we derive the lower bound of the capacity by showing the existence of a good code that can transmit classical information with a certain error probability. Applying the above two bounds, we prove the asymptotic equivalence between classical capacity and hypothesis-testing relative entropy in any general physical theory.
In this work, we propose a soft covering problem for fully quantum channels using relative entropy as a criterion for operator closeness. We establish covering lemmas by deriving one-shot bounds on the achievable rates in terms of smooth min-entropies. In the asymptotic regime, we show that the infimum of the rate, defined as the logarithm of the minimum rank of the encoded input state, is given by the minimal coherent information between the reference and output systems that yields the target output state. Furthermore, we present a one-shot quantum decoupling theorem that also employs a relative-entropy criterion. Due to the Pinsker inequality, our one-shot results based on the relative-entropy criterion are tighter than the corresponding results based on the trace norm considered in the literature. In addition, we establish achievable error exponents and second-order rates for quantum soft covering under both trace-distance and relative-entropy criteria.
Min-entropy sampling gives a bound on the min-entropy of a randomly chosen subset of a string, given a bound on the min-entropy of the whole string. König and Renner showed a min-entropy sampling theorem that holds relative to quantum knowledge. Their result achieves the optimal rate, but it can only be applied if the bits are sampled in blocks, and only gives weak bounds for the non-smooth min-entropy. We give two new quantum min-entropy sampling theorems that do not have the above weaknesses. The first theorem shows that the result by König and Renner also applies to bitwise sampling, and the second theorem gives a strong bound for the non-smooth min-entropy. Our results imply a new lower bound for k-out-of-n random access codes: while previous results by Ben-Aroya, Regev, and de Wolf showed that the decoding probability is exponentially small in k if the storage rate is smaller than 0.7, our results imply that this holds for any storage rate strictly smaller than 1, which is optimal.
We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.