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

CREATORAshutosh Marwah and Frédéric Dupuis
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE174 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text