Entropy accumulation with improved second-order term

I. INTRODUCTION

• The theorem is relevant to quantum key distribution and device-independent protocols that generate randomness from repeated quantum subprotocols and sampled statistics.Such protocols estimate quantities such as error rates before processing the resulting randomness further.Source: §I · p. 1
• The entropy accumulation theorem bounds extractable randomness from an n-step quantum process conditioned on observed statistics, using a tradeoff function that captures worst-case per-step entropy.It applies the theorem by instantiating each channel with one step of a cryptographic protocol.Source: §I · p. 1
• For testing probability O(1/n), the tradeoff-function gradient can scale as n, making the second-order correction Ω(n^3/2) and overwhelming the first-order term.The problematic correction scales as √n times a constant proportional to the gradient of the tradeoff function.Source: §I · p. 1
• Conventional Chernoff-Hoeffding analyses can have better scaling in amenable cases and retain a non-trivial bound when the testing rate is O(1/n).Prior work also applies entropy accumulation to blocks rather than individual rounds to improve dependence on the testing rate [2, Appendix B].Source: §I · p. 2
• The paper improves the entropy accumulation theorem’s second-order term, building on a broader information-theoretic literature on second-order bounds –[16].The introduction notes that exact O(√n) terms obtained through Berry-Esseen techniques appear unavailable here.Source: §I · p. 2
• The paper develops notation and divergence-variance tools, proves a refined Rényi-to-von-Neumann entropy bound, applies it to entropy accumulation, and evaluates finite-block device-independent randomness expansion.The paper also discusses infrequent sampling and open problems concerning optimal second-order terms.Source: §I · p. 2

A. Notation

• Quantum systems and their associated Hilbert spaces are denoted by letters such as A, B, and C.Collections A1 through An can be abbreviated by indexed ranges or by An shorthand, depending on context.Source: A. Notation · p. 3
• L(A) denotes linear operators on A, while L(A)→L(B) denotes linear maps from operators on A to operators on B.The identity map on L(A) is also assigned dedicated notation.Source: A. Notation · p. 3
• D(A) denotes the set of normalized density operators on A.Source: A. Notation · p. 3
• The notation includes logarithms in base 2, variance and covariance, several divergence measures, and divergence-variance quantities used throughout the paper.The listed divergences are the sandwiched Rényi divergence, Petz Rényi divergence, and related variance measures.Source: A. Notation · p. 3

B. Entropic quantities

• The conditional von Neumann entropy is introduced for bipartite density operators as a central entropic quantity.Source: B. Entropic quantities · p. 3
• The paper’s proofs heavily rely on two Rényi relative entropies: the Petz version, first introduced in, and the sandwiched version, introduced in [18], [19].Source: B. Entropic quantities · p. 3
• Conditional entropies are defined from relative entropies, including sandwiched and alternative Rényi conditional entropies for bipartite quantum states.The sandwiched conditional entropy is parameterized by α ∈ [1/2,∞].Source: B. Entropic quantities · p. 4
• Smooth min- and max-entropies optimize the corresponding entropies over subnormalized states within ε purified distance of the actual state.The smooth min- and max-entropies quantify uncertainty after allowing an ε-close state in the purified-distance ball.Source: B. Entropic quantities · p. 4

C. Chain rule for Rényi entropies

• The original entropy accumulation proof relies on a Rényi-entropy chain rule, which this paper reproduces because its proof follows the same main steps [1].The required structural condition is the tripartite Markov relation A ↔ B ↔ C, defined by I(A:C|B)ρ = 0.Source: C. Chain rule for Rényi entropies · p. 4
• The chain rule applies to a trace-preserving completely positive map that produces sequential systems under the Markov condition A1 ↔ B1 ↔ B2.The statement is formulated for Rényi parameter α in the relevant interval and optimizes over density operators on the prior systems.Source: C. Chain rule for Rényi entropies · p. 4
• When the initial state is pure, the optimization in the chain-rule statement can be restricted to pure input states.Source: C. Chain rule for Rényi entropies · p. 4
• Figure 2 plots the divergence variance v(q) for a Bernoulli random variable with Pr[X = 0] = q and shows a peak near q = 0.083 with value approximately 0.9142.Source: Figure 2 · p. 5

• Quantum divergence variance is the quantity governing the paper’s second-order correction term.Source: §III · p. 5
• Divergence variance does not satisfy data processing in general, even for classical states.Source: §III · p. 5
• The divergence variance has general bounds, with improved upper bounds when the first system is classical.Source: §III · pp. 5–6
• The section also establishes additivity of divergence variance and introduces quantum mutual-information variance, previously defined in [26].Source: §III · pp. 5, 7
• Conditional-entropy variance decomposes over a classical conditioning variable into averaged conditional variances plus the variance of conditional entropies.Source: §III · pp. 5, 8
• For Markov-chain states, conditional-entropy variance includes the component variances and twice their covariance; with trivial B, it reduces to V(A|CX).Source: §III · pp. 8–9

V (AB|CDX)

• For AC ↔ X ↔ BD, V(AB|CDX) equals the two conditional variances plus twice the covariance of their conditional-entropy random variables.Source: V (AB|CDX) · p. 9
• The proof combines the classical-conditioning decomposition with divergence-variance additivity and bounds the cross term using Cauchy–Schwarz.Source: V (AB|CDX) · pp. 9–10
• If the conditional states for different X values are orthogonal, X is effectively redundant for computing conditional-entropy variance.Source: V (AB|CDX) · p. 10

• An explicit remainder term is obtained for classical probability distributions and then transferred to Petz divergence through Nussbaum–Szkoła distributions.Source: §IV · pp. 11–12
• The proof uses Taylor expansion, remainder control, and concavity arguments to bound the α-dependent error.Source: §IV · pp. 11–12
• The construction preserves relative entropy and divergence variance under the Nussbaum–Szkoła representation at α = 1.Source: §IV · p. 12
• The resulting continuity estimate yields a quantitative bound for conditional Rényi entropy near α = 1.Source: §IV · p. 12

• The new theorem improves entropy-accumulation bounds under the same channel, event, tradeoff-function, and Markov conditions as the original framework.Source: §V · pp. 12–14
• The theorem is designed for direct application to protocols with infrequent sampling, with bounds tailored to the resulting second-order dependence.Source: §V · pp. 13–14
• Its finite-n correction is expressed through tradeoff-function variance, system dimension, and an α-dependent constant that can be optimized numerically.Source: §V · p. 13
• For classical A_i systems, 2 log dA can be replaced by log dA because conditional Rényi entropy is nonnegative.Source: §V · pp. 13–14
• The proof then applies the Rényi chain rule across rounds, uses the improved continuity estimate, and bounds the resulting variance terms using Section III.Source: §V · pp. 14–16
• The proof constructs entropy-price systems D_i whose entropies encode the tradeoff function while keeping their entropy variance small.Source: §V · p. 14

Definitions

• Infrequent-sampling channels model protocols that test only a few randomly sampled rounds, with testing probability γ and a special no-test output ⊥.The output alphabet is X = X′ ∪ {⊥}, and the channel never outputs ⊥ in the non-testing case.Source: A. EAT channels with infrequent sampling · p. 17

Tradeoff-function construction

• A crossover tradeoff function g based on testing statistics induces a min-tradeoff function f for the full channel.The construction restricts admissible input states using the statistics produced by the testing map and relates f(q) to g(q′) for distributions with testing mass γ.Source: A. EAT channels with infrequent sampling · p. 17
• The constructed tradeoff function is verified by characterizing feasible output distributions and comparing its value with conditional von Neumann entropy over compatible states.For distributions outside the required γ-scaled form, the compatible-state set is empty; for valid distributions, the defining entropy inequality establishes that f is a min-tradeoff function.Source: A. EAT channels with infrequent sampling · p. 17

Entropy bound

• The infrequent-sampling EAT bound has constants independent of n and γ, and becomes non-trivial when γ is at least c/n for a constant c.This corresponds to testing a constant number of rounds and improves on the original EAT scaling in the small-testing regime.Source: A. EAT channels with infrequent sampling · p. 18

Protocol

• The devices are modeled as arbitrary TPCP maps with internal memory and an adversarial reference system, allowing preprogrammed devices that cannot communicate with their manufacturer.The round maps generate test flags, inputs, outputs, and memory updates while preserving the device-independent setting.Source: §VI · pp. 18–19, Figure 4 · p. 20
• A CHSH-based protocol tests randomly sampled rounds, fixes data-round inputs to X = 0 and Y = 0, estimates losses, and extracts randomness from the device outputs.Each round is a test with probability γ; the protocol aborts when the number of test-round losses exceeds (1 − e)γn.Source: §VI · p. 19

Entropy-accumulation analysis

• The analysis constructs an affine min-tradeoff function by taking a tangent to the convex single-round entropy bound g* and applies the improved entropy-accumulation theorem.The tangent point can be chosen as e for the stated theorem, although smaller choices may improve bounds for particular γ and n.Source: §VI · pp. 19–21
• Theorem VI.1 gives either a lower bound on conditional min-entropy after non-abort or an abort probability of at least 1 − ε.The entropy lower bound has leading term ng*(e), a second-order correction involving r, and a constant c′ depending on ε and dg*.Source: §VI · p. 20

Security and expansion

• For e < cos2(π/8), suitable devices abort with probability 2^-Ω(γn), while successful executions yield roughly ng*(e) secure random bits after extraction.The protocol consumes approximately (h(γ) + 2γ)n input bits plus O(log^3 n) extractor-seed bits.Source: §VI · p. 20

Numerical comparison

• At fixed e = 0.8, the new bounds outperform the blocking technique of [2] across the plotted sampling regimes, for which blocking gives positive rates only at γ = 1 and γ = 0.1.The comparison fixes ε = 10^-5 and assumes ρ[Ω] ≥ 10^-5; the first-order asymptotic rate is roughly 0.3461.Source: §VI · p. 19, Figure 5 · p. 21

VII. CONCLUSION AND OPEN PROBLEMS

• The new theorem’s infrequent-sampling scaling roughly matches classical Chernoff-type bounds, avoiding the severe penalty of applying the original theorem directly.It can be applied directly when testing occurs in only a few rounds.Source: §VII · p. 21
• Compared with blocking into O(1/γ)-sized blocks, the method handles broader cases where Var(f) differs substantially from the local dimension.It also avoids additional blocking parameters and is described as more natural and simpler to use.Source: §VII · pp. 21–22
• The new method produces substantially better numerical bounds than the blocking method for the protocol studied in Section VI.The comparison is shown by the dashed blocking bounds in Figure 5.Source: §VII · p. 22
• An open problem is obtaining an optimal second-order term matching the i.i.d. form nV Φ^-1(ε^2).The paper’s variance quantity may be loosened by proof inequalities, and the ε-dependence does not match standard second-order expansions.Source: §VII · p. 22
• The final constant c′ in Equation (28) may also admit improvement because it arises from ad-hoc inequalities and may depend on parameters only as a proof artifact.The authors leave its correct parameter dependence as an open question.Source: §VII · p. 22

APPENDIX

• For a quantum state decomposed over a classical variable, the appendix states inequalities applying to each classical value and to Rényi parameters in specified ranges.The displayed lemmas concern states of the form ρ = Σ_x p_x ρ_AB|x and related classical-register constructions.Source: APPENDIX · p. 22
• A data-processing step is used after adjoining a duplicated classical register to the state.This construction supports the appendix’s entropy inequalities for classical-quantum states.Source: APPENDIX · p. 22