PaperlayerView exact revision on arXiv

Source-linked AI summary

Entropy accumulation

Frederic Dupuis, Omar Fawzi, Renato Renner

arXiv:1607.01796v2quant-phcs.IT

TL;DR

The paper studies whether total uncertainty in an n-partite system accumulates as the uncertainty of its parts beyond the IID setting. It establishes entropy accumulation for sequentially generated, potentially dependent systems using suitably conditioned von Neumann entropies, and reports essentially tight security bounds for device-independent cryptography. The framework also incorporates global statistical information and supports applications to general attacks.

  • Problem

    The paper addresses the limited tractability of smooth entropies for large systems when the IID assumption of independent, identically distributed parts does not hold.

  • Method

    The paper uses a chain rule for conditional sandwiched Rényi entropies to decompose sequence-level uncertainty into single-step terms, then bounds them with conditioned von Neumann entropies.

  • Results

    Entropy accumulation applies without independence under quantum Markov conditions, and device-independent cryptography obtains essentially tight security bounds against general attacks.

  • Takeaways & Limitations

    Large-system uncertainty can be analyzed through sequential parts while incorporating observed global statistics, enabling applications including device-independent quantum key distribution and randomness expansion.

  • Takeaways & Limitations

    The framework relies on Markov-chain conditions, and the authors identify generalizing beyond exact Markov conditions as an open direction for physically realistic thermalization arguments.

Abstract

from arXiv · show

We ask the question whether entropy accumulates, in the sense that the operationally relevant total uncertainty about an $n$-partite system $A = (A_1, \ldots A_n)$ corresponds to the sum of the entropies of its parts $A_i$. The Asymptotic Equipartition Property implies that this is indeed the case to first order in $n$, under the assumption that the parts $A_i$ are identical and independent of each other. Here we show that entropy accumulation occurs more generally, i.e., without an independence assumption, provided one quantifies the uncertainty about the individual systems $A_i$ by the von Neumann entropy of suitably chosen conditional states. The analysis of a large system can hence be reduced to the study of its parts. This is relevant for applications. In device-independent cryptography, for instance, the approach yields essentially optimal security bounds valid for general attacks, as shown by Arnon-Friedman et al.

1 Introduction

The paper asks whether operational uncertainty accumulates beyond the IID setting, and develops a framework showing that total uncertainty can be bounded using suitably conditioned entropies of sequentially generated parts.

  • Motivation: The IID assumption makes smooth-entropic uncertainty of a large system tractable, but requires mutually independent and identically distributed parts with analogous side information.Under IID structure, the Asymptotic Equipartition Property relates total uncertainty to a sum of conditional von Neumann entropies.
  • Main contribution: Entropy accumulation generalizes this relation to non-IID pairs generated sequentially by processes that may pass information through memory registers.The required condition is that, given previously generated side information, the relevant systems form a quantum Markov chain.
  • Main contribution: Each part contributes a conditional von Neumann entropy evaluated with its side information and possible information about the process memory, optimized over compatible memory states.This reduces bounds on the uncertainty of the full sequence to terms associated with individual generation steps.
  • Extensions: The more general theorem can incorporate global statistical information by restricting the optimization to states whose induced classical distributions match observed statistics.The statistical values can be determined from each generated pair without disturbing it.
  • Applications: Entropy accumulation converts security proofs restricted to collective attacks into proofs against general attacks, with essentially tight bounds demonstrated for device-independent cryptography.The cited applications include fully device-independent quantum key distribution and randomness expansion.
  • Proof strategy: The proof decomposes a conditional sandwiched Rényi entropy into single-step terms and bounds those terms using von Neumann entropies through a novel chain rule.The approach generalizes the quantum Asymptotic Equipartition Property to general non-IID states.

2 Preliminaries

The preliminaries establish notation for quantum states, conditional states, channels, Markov chains, and smooth and Rényi entropies used throughout the paper.

  • Notation: The paper works with finite-dimensional Hilbert spaces and distinguishes normalized, sub-normalized, and positive semidefinite operators.It also introduces shorthand for collections of systems and operators between Hilbert spaces.
  • Conditional states: For classical-quantum states, ρA|x denotes the conditional state obtained from the block ρA,x after normalization.Conditional states can also be restricted to events and reduced by partial trace.
  • Conditional states: The paper defines a quantum conditional-state operator for a bipartite density operator, analogous to a conditional probability distribution.The operator is well defined because the support of ρAB lies within the support of idA ⊗ρB.
  • Quantum Markov chains: Quantum Markov chains are characterized through a direct-sum decomposition of the conditioning system and the entropic equality I(A : C|B)ρ = 0.The Markov condition also permits reconstruction from ρAB by a map acting only on B.
  • Entropic quantities: Smooth min- and max-entropies quantify conditional uncertainty using nearby sub-normalized operators and density operators on the conditioning system.The preliminaries also introduce sandwiched α-Rényi conditional entropies and related variants derived from relative entropies.

3 Chain rule for R´enyi entropies

This section develops a Rényi-entropy chain rule to decompose entropy without IID factorization, including a Markov-chain formulation based on suitably matched conditional states.

  • Motivation: The chain rule for Rényi entropies replaces IID decomposition when the target state is general and non-IID.The paper presents this chain rule as the technical tool for decomposing Rényi entropy into n terms.
  • General chain rule: Theorem 3.2 gives a chain rule for a density operator ρA1A2B and Rényi parameter α ∈(0, ∞).It is obtained by choosing σB = ρB in Lemma 3.1.
  • Markov-chain specialization: The Markov-chain theorem optimizes over states ν whose conditional state νA2B2|A1B1 matches ρA2B2|A1B1.This produces a weaker but more useful formulation than focusing on the particular state ν from the general chain rule.
  • Markov-chain specialization: For Markov states satisfying A1 ↔B1 ↔B2, the relevant conditional Rényi entropy of A1 is unchanged when conditioning on B1B2 instead of B1.The proof uses the Markov-chain structure and, for part of the parameter range, recoverability and monotonicity under quantum channels.
  • Channel formulation: The chain rules can also be formulated using trace-preserving completely positive maps rather than conditional states.The channel formulation allows optimization over input states, including pure states when the initial state is pure.

4 Entropy accumulation

The section states entropy accumulation in a general sequential model, formalizes the required maps and Markov conditions, and derives min- and max-entropy bounds with statistical tests and finite-size corrections.

  • Main result: The main result formulates entropy accumulation generally and derives a simplified corollary alongside the quantum Asymptotic Equipartition Property as a special case.The section presents the fully general theorem, simplified and introductory formulations, and the IID quantum special case.
  • Sequential model: Each process M_i maps the previous memory register to X_iA_iB_iR_i, with X_i a classical value determined jointly by A_i and B_i.The maps may include a test register X_i and are composed sequentially from an initial state on R_0E.
  • Sequential model: The construction assumes Markov conditions for every step and evaluates conditional entropies using states generated from the process M_i and a reference system isomorphic to the previous memory.The optimization ranges over states of the memory and reference system, with the conditional von Neumann entropy evaluated on M_i(ω).
  • Tradeoff functions: Affine min-tradeoff functions convert observed frequencies of X_i into lower entropy bounds for events satisfying the corresponding frequency constraint.The theorem applies when an event Ω implies f(freq(X_1^n)) ≥ h, and provides an analogous max-entropy statement for max-tradeoff functions.
  • Bounds and limitations: The resulting bounds include a second-order correction depending on the maximum dimension d_A and the gradient norm of the tradeoff function.The correction contains terms involving log(1 + 2d_A) and ||∇f||∞, while later remarks discuss replacing d_A with entropic quantities.
  • Proof strategy: The proof constructs auxiliary D_i systems encoding an entropy price for the tradeoff function, then applies a Rényi entropy chain rule repeatedly.The auxiliary systems add an entropy term that allows the tradeoff function to enter the optimization.

5 Applications

The applications section uses entropy accumulation for thermalisation, quantum-key-distribution security, and fully quantum random access codes. It derives security results for general attacks and a fidelity bound for FQRACs.

  • Applications: Entropy accumulation bounds total entropy transferred to an environment by the von Neumann entropy produced at each time step.For unitary joint evolution, this flow can also be expressed through the system’s entropy change.
  • Applications: In quantum cryptography, entropy accumulation addresses adversarial uncertainty when protocol tests provide global statistical information.The section presents a security proof for a variant of E91 quantum key distribution.
  • 5.1 Security of quantum key distribution: The E91 protocol samples basis choices, sifts matching indices, performs error correction, estimates phase errors, and applies two-universal hashing for privacy amplification.The protocol aborts when error correction fails or the estimated error count exceeds its threshold.
  • 5.1 Security of quantum key distribution: The E91 protocol is secure for admissible parameters when n is sufficiently large and can achieve asymptotic key rate 1 − HSh(e) − ϑEC.The key rate is the number of final key bits divided by n, while ϑEC denotes error-correction communication cost.
  • 5.2 Fully quantum random access codes: For fully quantum random access codes, entropy accumulation yields exponential fidelity bounds, tighter than the earlier bound for small k but weaker for large k.The construction encodes m message qubits into n < m code qubits while allowing retrieval of any subset of k message qubits.

6 Conclusions

The conclusion identifies cryptography and statistical mechanics as important application areas for entropy accumulation. It also highlights open scope boundaries involving protocol symmetry, finite-size scaling, and exact Markov assumptions.

  • Conclusions: Entropy accumulation gives operational meaning to multipartite entropy by approximating smooth min- or max-entropy with sums of individual von Neumann entropies.The framework has ramifications in quantum cryptography and thermodynamics.
  • Conclusions: The approach can circumvent limitations of current cryptographic security proofs and may extend to protocols such as DPS and COW.Those protocols lack the symmetries required by standard de Finetti-type techniques.
  • Conclusions: In statistical mechanics, entropy accumulation can characterize thermalisation, but physically realistic applications may require relaxing the theorem’s exact Markov conditions.The text suggests less stringent conditions as a possible generalization.
  • Conclusions: Continuous-variable protocols have security proofs against general attacks, but their bounds scale unfavourably in the finite-size regime.This is identified as a separate limitation of existing results.
  • Conclusions: Low-energy many-body states are proposed as another application area when physical assumptions support the required decomposition and Markov conditions or relaxations.The discussion mentions states approximated by matrix-product structures.

Appendix A The function ∥· ∥α

Appendix A defines an extension of the Schatten α-norm for positive α and records standard invariance properties used in later arguments.

  • The function ∥·∥α: The appendix extends the Schatten α-norm to α > 0 for operators mapping a space A to a space B.The operator is denoted X = X_B←A.
  • The function ∥·∥α: The extended norm is invariant under adjoint and transpose operations in the stated operator setting.These equalities follow from the Singular Value Theorem.
  • The function ∥·∥α: The appendix also invokes a lemma whose optimization ranges over density operators Z.This supports the operator inequalities used in the surrounding development.

Appendix B Properties of the sandwiched R´enyi entropies

Appendix B develops properties of sandwiched Rényi entropies, including definitions, conditioning identities, bounds, duality, and data-processing arguments.

  • Definitions and relations: Sandwiched Rényi entropy is presented as a special case of sandwiched Rényi relative entropy, with alternative conditional-entropy constructions also discussed.The appendix refers to comparisons between these notions and notes a duality relation.
  • Operator representation: A basis-dependent linear operator is introduced with transpose operations understood in the same basis.The appendix states properties for operators acting between product-system spaces.
  • Technical lemmas: The appendix proves inequalities for sandwiched Rényi relative entropy using purifications, operator decompositions, completely positive maps, and the data-processing inequality.The arguments include a positive-part construction and conclude one lemma through data processing.
  • Conditioning on classical information: Several lemmas relate entropies conditioned on classical information to unconditioned entropies and to classical-register extensions.These results apply to states classical on X and to conditioning induced by projective measurements.
  • Technical lemmas: Projective measurements and deterministic classical functions can be represented by a TPCP map while preserving the relevant Rényi-relative-entropy relation.The proof uses orthogonality of the projectors and data processing.
  • Bounds and comparisons: The appendix develops bounds connecting different Rényi-entropy quantities, including dimension-dependent restrictions and parameter-dependent error terms.It also records monotonicity in α and references improved but non-explicit alternatives.

Appendix C Necessity of the Markov chain conditions

The Markov chain conditions are necessary for entropy accumulation: removing them allows a classical construction where summed per-bit uncertainty grows linearly while joint uncertainty remains roughly constant.

  • Necessity of the Markov chain conditions: The appendix shows that dropping the Markov chain conditions makes the entropy-accumulation inequality invalid.It first notes that the statement is not generally valid without these conditions, then gives a specific classical counterexample.
  • Markov chain characterization: A tripartite state satisfies A ↔ B ↔ C exactly when I(A : C|B)ρ = 0.The appendix uses conditional mutual information to characterize the Markov state property and derives standard composition consequences.
  • Counterexample analysis: The joint entropy on the left-hand side is roughly 1, contradicting the proposed inequality for large n.Thus even a weaker version of the inequality fails, and the corresponding quantum statement cannot hold without Markov conditions.
  • Counterexample construction: The counterexample uses independent uniform n-bit strings B1, …, Bn and a uniform bit C to define A by conditional bitwise addition.When C = 0, A is determined by the B_i; when C = 1, A is completely random.
  • Counterexample analysis: Each individual bit Ai is random with probability 1/2, so the summed conditional entropies scale linearly with n.The construction makes every term on the right-hand side contribute uncertainty with probability 1/2.
Loading 1607.01796v2…