Universal chain rules from entropic triangle inequalities
Ashutosh Marwah and Frédéric Dupuis · 2024
Read Universal chain rules from entropic triangle inequalities by Ashutosh Marwah and Frédéric Dupuis (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-06723.txt.
Introduction
Ashutosh Marwah and Frédéric Dupuis prove a universal chain rule for a smoothed measure of entropy used in quantum information, in a 2024 paper. A chain rule splits the uncertainty of a whole system into the uncertainties of its parts, added step by step. The standard rule fails for the smooth min-entropy, a quantity central to quantum cryptography.
The authors prove the rule for a close variant of that entropy, equal to the usual one up to a constant, for any number of parts. A dual result follows for the matching max-entropy. Their proof leans on entropy triangle inequalities. As a bonus, they prove a relaxed entropy accumulation theorem that drops the usual demand that the state be built step by step.
Catalog record
| CREATOR | Ashutosh Marwah and Frédéric Dupuis |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 174 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-06723
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Universal chain rules from entropic triangle inequalities Ashutosh Marwah and Frédéric Dupuis Abstract The von Neumann entropy of an n n -partite system A 1 n A_{1}^{n} given a system B B can be written as the sum of the von Neumann entropies of the individual subsystems A k A_{k} given A 1 k − 1 A_{1}^{k-1} and B B . While it is known that such a chain rule does not hold for the smooth min-entropy, we prove a counterpart of this for a variant of the smooth min-entropy, which is equal to the conventional smooth min-entropy up to a constant. This enables us to lower bound the smooth min-entropy of an n n -partite system in terms of, roughly speaking, equally strong entropies of the individual subsystems. We call this a universal chain rule for the smooth min-entropy, since it is applicable for all values of n n . Using duality, we also derive a similar relation for the smooth max-entropy. Our proof utilises the entropic triangle inequality based technique developed in [ MD23 ] for analysing approximation chains. Additionally, we also prove an approximate version of the entropy accumulation theorem, which significantly relaxes the conditions required on the state to bound its smooth min-entropy. In particular, it does not require the state to be produced through a sequential process like previous entropy accumulation type bounds. In our upcoming companion paper [ MD24a ] , we use it to prove the security of parallel device independent quantum key distribution. \DeclareCaptionType Protocol 1 Introduction The rates of several interesting tasks with i.i.d (independent and identically distributed) structure, like coding and randomness extraction, are characterised by the von Neumann entropy [ Sch95 , Wil13 ] in the asymptotic regime. The von Neumann entropy is the most commonly used and understood measure of uncertainty. It generally follows the behaviour one intuitively expects from a measure of uncertainty. Central to this paper is the intuitive expectation that the total uncertainty of two registers A_{1} and A_{2} given a register B should be the sum of the uncertainty of register A_{1} given B and the uncertainty of register A_{2} , conditioned on both A_{1} and B . The von Neumann entropy, respects this intuition nicely and satisfies the following chain rule: \displaystyle H(A_{1}A_{2}|B)_{\rho}=H(A_{1}|B)_{\rho}+H(A_{2}|A_{1}B)_{\rho}. (1) More generally, we can decompose the von Neumann entropy of a large system A_{1}^{n} (1) (1) (1) The notation A_{1}^{n} denotes the set of registers A_{1},A_{2},\cdots,A_{n} . given B into a sum of the entropies of its parts as: \displaystyle H(A_{1}^{n}|B)_{\rho}=\sum_{k=1}^{n}H(A_{k}|A_{1}^{k-1}B)_{\rho}. (2) As we move beyond the asymptotic and i.i.d regime and consider general processes, we move into the territory of one-shot information theory, where we need a multitude of different entropic measures to characterise and analyse various tasks. The smooth min-entropy [ Ren06 , RK05 ] is one of the most important information measures among these. It determines the amount of randomness that can be securely extracted from a (classical) register, when part of it is correlated with the adversary’s state [ TRSS10 ] . This is particularly useful in cryptography, where no assumptions (specifically i.i.d assumptions) can be placed on the adversary’s actions. For a state \rho_{AB} , the min-entropy of system A conditioned on system B is defined as (2) (2) (2) We use base e for \exp and \log , and nat units for entropies throughout this paper. \displaystyle H_{\min}(A|B)_{\rho}:=\max\left\{\lambda\in\mathbb{R}:\text{there exists a state }{\sigma}_{B}\text{ such that }{\rho}_{AB}\leq e^{-\lambda}\Id_{A}\otimes\sigma_{B}\right\} (3) and the smooth min-entropy is defined as \displaystyle H_{\min}^{\epsilon}(A|B)_{\rho}:=\max_{\tilde{\rho}}H_{\min}(A|B)_{\tilde{\rho}} (4) where the maximum is over all subnormalised states \tilde{\rho}_{AB} which are \epsilon -close to the state \rho in the purified distance. The smooth min-entropy behaves very differently from the von Neumann entropy. Informally speaking, it places a much larger weight on the worst case value of the conditioning register as compared to the von Neumann entropy, which places equal weight on all conditioning values. As a consequence, the smooth min-entropy exhibits behaviour that deviates from the intuitive expectations set by the von Neumann entropy. This is evident in the chain rule for smooth min-entropy [ DBWR14 , VDTR13 ] , which is notably more complex than Eq. 1 : \displaystyle H_{\min}^{\epsilon_{1}+2\epsilon_{2}+\delta}(A_{1}A_{2}|B)_{\rho}\geq H_{\min}^{\epsilon_{1}}(A_{1}|B)_{\rho}+H_{\min}^{\epsilon_{2}}(A_{2}|A_{1}B)_{\rho}-k(\delta) (5) where k(\delta)=O\left(\log\frac{1}{\delta}\right) . Moreover, it is easy to demonstrate that a smooth min-entropy counterpart for the relation in Eq. 2 cannot hold true. Mathematically, a relation of the following form cannot be valid for \epsilon in a neighborhood of 0 (3) (3) (3) Simply consider the classical distribution p_{A_{1}^{n}B} where B is chosen uniformly at random from \{0,1\} and if B=0 then A_{1}^{n} is set to the constant all zero string, otherwise each A_{i} is independently and randomly chosen bit. In this case, H_{\min}^{g_{1}(\epsilon)}(A_{1}^{n}|B)_{p}=O(1) and for each k , H_{\min}(A_{k}|A_{1}^{k-1}B)_{p}\geq\log 4/3 . For small \epsilon , Eq. 6 would have a constant left-hand side and a linearly growing right-hand side. : \displaystyle H_{\min}^{g_{1}(\epsilon)}(A_{1}^{n}|B)_{\rho} \displaystyle\geq\sum_{k=1}^{n}H_{\min}^{\epsilon}(A_{k}|A_{1}^{k-1}B)_{\rho}-ng_{2}(\epsilon)-k(\epsilon), (6) where the functions g_{1} , g_{2} , and k are dependent solely on \epsilon and |A| (the dimension of the A_{k} registers, assumed to be constant in n ) and are independent of n . Furthermore, g_{1}(\epsilon) and g_{2}(\epsilon) are required to be small functions of \epsilon , meaning they are continuous and approach 0 as \epsilon tends to 0 . Eq. 6 is intimately related to the concept of approximation chains introduced in [ MD23 ] . For a state \rho_{A_{1}^{n}B} , a sequence of states (\sigma_{A_{1}^{k}B}^{(k)})_{k=1}^{n} is called an \epsilon -approximation chain of \rho if for every 1\leq k\leq n , we have \rho_{A_{1}^{k}B}\approx_{\epsilon}\sigma_{A_{1}^{k}B}^{(k)} . Often, direct bounds on the conditional entropies of the state \rho are unavailable; however, they can be obtained for the entropies of its approximation chain states. For instance, consider a state \rho_{A_{1}^{n}B} where the A_{k} registers are produced sequentially. Ideally, each register A_{k} should be sampled independently from the rest. However, say imperfections introduce minor correlations between A_{k} and the earlier registers. In such a case, we might only be able to confirm that \rho_{A_{1}^{k}B}\approx_{\epsilon}\rho_{A_{k}}\otimes\rho_{A_{1}^{k-1}B}=:\sigma_{A_{1}^{k}B}^{(k)} . Despite these correlations, we expect the entropy of A_{1}^{n} given B to be large, as the A_{k} registers are almost independent of B . In such cases, a chain rule-like tool relating the entropy of \rho to the entropies of its approximation chain states would be helpful. The impossibility of a bound of the form in Eq. 6 implies that H_{\min}^{\epsilon}(A_{1}^{n}|B)_{\rho} cannot be lower bounded meaningfully in terms of the min-entropies of the approximation chain states of \rho , since these approximation chain states can simply be states satisfying H_{\min}(A_{k}|A_{1}^{k-1}B)_{\sigma^{(k)}}=H_{\min}^{\epsilon}(A_{k}|A_{1}^{k-1}B)_{\rho} for every k . On the other hand, the von Neumann entropy of a state can easily be bounded in terms of its approximation chain by using the continuity of the conditional von Neumann entropy [ AF04 , Win16 ] to modify Eq. 2 and derive: \displaystyle H(A_{1}^{n}|B)_{\rho} \displaystyle\geq\sum_{k=1}^{n}H(A_{k}|A_{1}^{k-1}B)_{\sigma^{(k)}}-nf(\epsilon) (7) where f(\epsilon)=O\left(\epsilon\log\frac{|A|}{\epsilon}\right) . The absence of a comparable bound for the smooth min-entropy severely limits us (4) (4) (4) It is often useful to initially prove novel results using von Neumann entropies before translating them into the corresponding one-shot entropies. This approach separates the complexity of the problem into two distinct phases. The impossibility of Eq. 6 , in particular, prevents us from porting arguments