Smooth Entropies and One-Shot Information Theory

Classical and quantum Shannon theory answer almost every operational question with a single number, the von Neumann conditional entropy $H(A|B)$ : how far a source compresses, how much secret key a state yields, how much entanglement it costs to merge one system into another. Those clean answers are exact only in one idealized regime — the asymptotic, independent-and-identically-distributed limit, where you process $n\to\infty$ copies and let the error vanish. Real devices do not live there: a quantum-key-distribution session exchanges a finite, correlated block of signals once, and must certify security against an adversary entangled with it. One-shot information theory is built for exactly that world — it asks what a single use of a resource achieves at a fixed tolerated error $\varepsilon$ — and it finds the von Neumann entropy is no longer the right currency. The replacements come in a dual pair. The conditional min-entropy $H_{\min}(A|B)$ is the worst-case quantity — minus the logarithm of how well an adversary holding $B$ can guess $A$ — so it counts extractable randomness and secret-key length. The conditional max-entropy $H_{\max}(A|B)$ is the optimistic counterpart, a fidelity of decoupling that counts compression and merging. A quantum miracle links them: on any purification to a pure state on $ABC$ , they are equal and opposite, $H_{\max}(A|B) = -H_{\min}(A|C)$ . Because raw versions are brittle, one smooths over an $\varepsilon$ -ball of nearby states, baking the error budget into the entropy. The Asymptotic Equipartition Property closes the loop: over $n$ i.i.d. copies the smooth entropies collapse back onto $H(A|B)$ with a $1/\sqrt{n}$ correction, so this theory strictly contains Shannon's while additionally governing the single-shot world.

Key takeaways

Smooth entropies — $H_{\min}^{\varepsilon}$ and $H_{\max}^{\varepsilon}$ — replace the von Neumann entropy as the operational quantities for one-shot, finite-resource processing, where the i.i.d. asymptotic limit does not apply.
The conditional min-entropy is an operator inequality, $H_{\min}(A|B)_\rho=\max\{\lambda:\rho_{AB}\le 2^{-\lambda}\,\mathbb{1}_A\otimes\sigma_B\}$ ; for classical $A$ it equals $-\log_2 p_{\mathrm{guess}}(A|B)$ .
The max-entropy is its purification dual, $H_{\max}(A|B)_\rho=-H_{\min}(A|C)_{\psi}$ — a structural identity with no classical analogue, since only quantum states have canonical purifications.
Smoothing optimizes over an $\varepsilon$ -ball in purified distance, discarding pathological tails so negligible events cannot distort the answer; $\varepsilon$ is the tolerated error.
$H_{\min}^{\varepsilon}$ counts extractable secret bits (leftover hashing) and $H_{\max}^{\varepsilon}$ counts compression and merging cost, and the two sandwich $H(A|B)$ : $H_{\min}\le H\le H_{\max}$ .
The AEP recovers ordinary theory: $\tfrac1n H_{\min/\max}^{\varepsilon}(A^n|B^n)_{\rho^{\otimes n}}\to H(A|B)_\rho$ with a $1/\sqrt n$ correction, making smooth entropy the language of finite block lengths.
Key idea: replace the von Neumann entropy with a worst-case entropy (the min-entropy, an adversary's smallest surprise) and its optimistic dual (the max-entropy), smooth each over an $\varepsilon$ -ball so negligible events cannot distort the answer, and recover $H(A|B)$ only asymptotically through the AEP.

The core insight

Replace the von Neumann entropy by a worst-case min-entropy (the smallest surprise an adversary faces) and its optimistic purification dual, the max-entropy, smoothed over an $\varepsilon$ -ball so negligible events cannot distort the answer. Min governs security and extraction, max governs compression and merging, and the AEP recovers $H(A|B)$ only asymptotically.

Where this lives today

Smooth entropy is the arithmetic inside deployed and standardized quantum cryptography. Every modern finite-key QKD security proof — the kind demanded by ETSI and the emerging ISO/IEC standards — computes a secret-key length $\ell\approx H_{\min}^{\varepsilon}(X|E)-\mathrm{leak}_{\mathrm{EC}}$ , the smooth min-entropy estimated from the observed error rate and block size. A real session sends $10^{6}$ to $10^{9}$ signals, and the $1/\sqrt n$ AEP correction is exactly what separates an honest finite-key rate from the over-optimistic asymptotic one. The same machinery, through entropy accumulation (Dupuis, Fawzi and Renner), certifies device-independent randomness expansion and the public beacons behind the loophole-free experiments. Beyond cryptography, the AEP drives second-order coding ( $\ell\approx nC-\sqrt{nV}\,\Phi^{-1}(\varepsilon)$ ), and one-shot decoupling — the max-entropy dual of leftover hashing — underlies one-shot state merging and the Hayden–Preskill argument in black-hole information.

The physical picture

Picture an adversary, Eve, holding a system $B$ correlated — perhaps entangled — with your system $A$ , and trying to guess $A$ . The conditional min-entropy is, up to a logarithm, the reciprocal of how often she succeeds: $H_{\min}(A|B)=-\log_2 p_{\mathrm{guess}}(A|B)$ . If she guesses almost surely, $H_{\min}\approx 0$ ; if $A$ is uniform and decoupled from $B$ , $H_{\min}=\log_2|A|$ , the maximum. This is why a secret-key length is set by the smooth min-entropy and never by the average-case von Neumann entropy — security is a worst-case promise, and averages hide the tail an adversary exploits. The max-entropy is the mirror image: the fidelity with which $A$ can be decoupled from or merged into $B$ , setting the qubits to compress a single instance. The von Neumann entropy sits between them, $H_{\min}\le H\le H_{\max}$ — the gap being the room between the pessimist's security estimate and the optimist's compression bound. The first figure makes that sandwich concrete for a qubit. The second shows the deepest structural fact: the two entropies are not merely ordered but dual. Purify any $\rho_{AB}$ to a pure $|\rho\rangle_{ABC}$ by adjoining a complement $C$ (the environment, or Eve herself); then the optimist's max-entropy of $A$ given the friendly $B$ equals minus the pessimist's min-entropy of $A$ given the hostile $C$ : $H_{\max}(A|B)=-H_{\min}(A|C)$ . Compression on one side and guessing security on the other are the same number read backwards. Classically this is impossible — a distribution has no canonical purification — so the identity is a gift of quantum mechanics, the lever that converts every compression theorem into a security theorem and back.

Figure

The entropy sandwich for a qubit with eigenvalues 0.9 and 0.1: the min-entropy H_min = 0.152 bits, the von Neumann entropy H = 0.469 bits and the max-entropy H_max = 0.678 bits obey H_min ≤ H ≤ H_max, and on n i.i.d. copies smoothing squeezes both ends onto H at the rate 1 over √n

Figure

Min–max duality on a purification: for any pure state ρ on the three systems A, B, C the max-entropy of A given the friendly reference B equals minus the min-entropy of A given the complement C, so H_max(A given B) = −H_min(A given C) — compression cost on one side is guessing security on the other

The core equations

Everything begins with the operator-inequality definition of the min-entropy: the largest exponent $\lambda$ such that a decoupled $2^{-\lambda}\,\mathbb{1}_A\otimes\sigma_B$ still dominates $\rho_{AB}$ in the Löwner ordering, optimized over $\sigma_B$ . That optimal $\lambda$ in bits is $H_{\min}(A|B)$ .

H_{\min}(A|B)_\rho \;=\; \max_{\sigma_B\ge 0,\;\mathrm{Tr}\,\sigma_B\le 1}\;\sup\{\lambda\in\mathbb{R}\,:\,\rho_{AB}\le 2^{-\lambda}\,\mathbb{1}_A\otimes\sigma_B\} \qquad (1)

where: $\rho_{AB}$ — bipartite density operator on $A,B$ ; $\sigma_B$ — auxiliary subnormalized state on $B$ , optimized; $\mathbb{1}_A$ — identity on $A$ ; $\le$ — operator (Löwner) ordering, $X\le Y$ meaning $Y-X\ge 0$ ; $\lambda$ — the exponent, optimal value $H_{\min}(A|B)$ in bits. Reading it: the closer $\rho_{AB}$ is to a decoupled $\mathbb{1}_A\otimes\sigma_B$ , the larger $\lambda$ and the min-entropy. The max-entropy is defined not by domination but by fidelity — how close, in Uhlmann fidelity, the state comes to the decoupled form. A large fidelity means $A$ resists merging into $B$ and is expensive to compress.

H_{\max}(A|B)_\rho \;=\; \max_{\sigma_B}\; 2\,\log_2 F\!\big(\rho_{AB},\,\mathbb{1}_A\otimes\sigma_B\big),\qquad F(\rho,\tau)=\big\|\sqrt{\rho}\sqrt{\tau}\big\|_1 \qquad (2)

where: $F(\rho,\tau)$ — Uhlmann fidelity; $\|\cdot\|_1$ — trace norm; $\sigma_B$ — normalized state on $B$ , optimized. Reading it: min uses an operator inequality (worst case), max a fidelity (average case) — the seed of pessimist versus optimist. The load-bearing identity ties the two together through purification: adjoin a complement $C$ so $\rho_{AB}$ becomes pure on $ABC$ , and the max-entropy of $A$ given $B$ is minus the min-entropy of $A$ given $C$ .

H_{\max}(A|B)_\rho = -\,H_{\min}(A|C)_\rho \qquad\text{for any purification } |\rho\rangle_{ABC} \qquad (3)

where: $|\rho\rangle_{ABC}$ — any pure state with $\mathrm{Tr}_C|\rho\rangle\langle\rho|=\rho_{AB}$ ; $C$ — the purifying (complementary) system. Reading it: one pure state carries a compression quantity and a security quantity at once — turning any statement about $B$ into one about the environment $C$ . Raw min- and max-entropies are fragile: a lone eigenvalue of weight $2^{-100}$ can collapse $H_{\min}$ or inflate $H_{\max}$ . Smoothing repairs both by optimizing over a ball of nearby states, reflecting only what happens up to the tolerated error.

H_{\min}^{\varepsilon}(A|B)_\rho = \max_{\tilde\rho\in\mathcal{B}^{\varepsilon}(\rho_{AB})} H_{\min}(A|B)_{\tilde\rho},\qquad H_{\max}^{\varepsilon}(A|B)_\rho = \min_{\tilde\rho\in\mathcal{B}^{\varepsilon}(\rho_{AB})} H_{\max}(A|B)_{\tilde\rho} \qquad (4)

where: $\mathcal{B}^{\varepsilon}(\rho)$ — the ball of subnormalized states within purified distance $\varepsilon$ ; $\varepsilon$ — the smoothing parameter, equal to the tolerated error. Reading it: maximize for the min-entropy (most favourable nearby state, most randomness) and minimize for the max-entropy (cheapest state, least compression cost) — both directions improve the bound. The ball is measured in the purified distance $P(\rho,\sigma)=\sqrt{1-F^2(\rho,\sigma)}$ , a genuine metric compatible with purification — the reason duality survives smoothing. It sandwiches, but does not equal, the trace distance ( $\tfrac12\|\rho-\sigma\|_1\le P\le\sqrt{\|\rho-\sigma\|_1}$ ), so proofs stated in either metric convert cleanly. The bridge back to ordinary theory is the fully quantum AEP: on $n$ i.i.d. copies the smooth min-entropy per copy rises to $H(A|B)$ from below, with a controlled finite- $n$ correction.

\frac1n\,H_{\min}^{\varepsilon}(A^n|B^n)_{\rho^{\otimes n}} \;\ge\; H(A|B)_\rho \;-\; \frac{c}{\sqrt n}\,\sqrt{\log_2\!\frac{2}{\varepsilon^2}}\;\xrightarrow[n\to\infty]{}\;H(A|B)_\rho \qquad (5)

where: $\rho^{\otimes n}$ — $n$ i.i.d. copies; $H(A|B)_\rho=H(AB)_\rho-H(B)_\rho$ — von Neumann conditional entropy; $c$ — a dimension-dependent constant. Reading it: the leading term is $H(A|B)$ and the correction dies as $1/\sqrt n$ — the Gaussian scaling that drives second-order coding. Finally, the operational payoff: the quantum leftover hash lemma converts smooth min-entropy into extractable near-uniform secret bits.

\ell \;=\; H_{\min}^{\varepsilon}(A|E)_\rho - 2\log_2\frac{1}{\delta_{\mathrm{PA}}}\quad\Longrightarrow\quad d\big(\text{output}\big)\;\le\;2\varepsilon+\delta_{\mathrm{PA}} \qquad (6)

where: $\ell$ — extracted key length in bits; $E$ — the adversary's quantum side information; $\delta_{\mathrm{PA}}$ — privacy-amplification error; $d(\cdot)$ — trace distance of the output from an ideal uniform-and-decoupled key. Reading it: one secret bit per bit of smooth min-entropy, minus a fixed toll of $2\log_2(1/\delta_{\mathrm{PA}})$ for security — the min-entropy is the currency of key.

Derivation AMin-entropy equals minus the log of the guessing probability

The goal is to give the min-entropy its operational meaning: for a classical–quantum state in which register $A$ is correlated with an adversary's quantum system $B$ , the conditional min-entropy is exactly minus the logarithm of the optimal guessing probability, $H_{\min}(A|B)=-\log_2 p_{\mathrm{guess}}(A|B)$ . Both quantities are semidefinite programs; the proof exhibits them as a primal–dual pair whose optima coincide, turning an abstract operator inequality into a statement about how often an eavesdropper wins.

Step 1. Write the state as classical–quantum, $\rho_{AB}=\sum_x p_x\,|x\rangle\langle x|_A\otimes\rho_B^x$ . Why: this is exactly a raw key $A$ against an eavesdropper $B$ .

Step 2. Specialize Eq. (1). Because $A$ is classical, $\rho_{AB}\le 2^{-\lambda}\mathbb{1}_A\otimes\sigma_B$ decouples block by block into $p_x\rho_B^x\le 2^{-\lambda}\sigma_B$ ; writing $\sigma_B'=2^{-\lambda}\sigma_B$ gives $2^{-H_{\min}(A|B)}=\min_{\sigma_B'}\{\mathrm{Tr}\,\sigma_B':\,p_x\rho_B^x\le\sigma_B'\ \forall x\}$ . Why: minimizing the trace of the dominating operator maximizes $\lambda$ — Eq. (1) as a clean SDP.

Step 3. The guessing SDP: an eavesdropper measures a POVM $\{E_x\}$ on $B$ , succeeding with $p_{\mathrm{guess}}=\max_{\{E_x\ge0,\,\sum_x E_x=\mathbb{1}\}}\sum_x p_x\,\mathrm{Tr}(E_x\rho_B^x)$ . Why: the best any adversary holding $B$ can do.

Step 4. Weak duality: for any feasible $\sigma_B'$ and POVM, $\sum_x p_x\,\mathrm{Tr}(E_x\rho_B^x)\le\sum_x\mathrm{Tr}(E_x\sigma_B')=\mathrm{Tr}\,\sigma_B'$ , using $p_x\rho_B^x\le\sigma_B'$ and $\sum_x E_x=\mathbb{1}$ . Why: every guessing value is bounded by every feasible trace.

Step 5. Close the gap. Slater's condition holds, so strong duality gives $p_{\mathrm{guess}}=\min_{\sigma_B'}\mathrm{Tr}\,\sigma_B'=2^{-H_{\min}(A|B)}$ ; taking $-\log_2$ yields the identity. Why: zero duality gap makes the worst-case bound and the best guessing measurement one number. *Verified: if $A$ is uniform on $|A|$ values and independent of $B$ (so $\rho_B^x=\rho_B$ ), a random guess gives $p_{\mathrm{guess}}=1/|A|$ and hence $H_{\min}=\log_2|A|$ — the maximal, side-information-proof randomness, as it must be.*

Go deeper · Derivation B · 1 minMin-max duality from purification and Uhlmann's theorem

Derivation BMin-max duality from purification and Uhlmann's theorem

The goal is to prove the central structural identity $H_{\max}(A|B)_\rho=-H_{\min}(A|C)_\rho$ for any purification $|\rho\rangle_{ABC}$ of $\rho_{AB}$ — the fact that trades a compression statement about the reference $B$ for a security statement about the complement $C$ . The engine is Uhlmann's theorem: the fidelity of two mixed states equals the maximal overlap of their purifications, which converts the $\sigma_B$ -optimization into the operator inequality defining the min-entropy on $C$ .

Step 1. Start from $H_{\max}(A|B)=\max_{\sigma_B}2\log_2 F(\rho_{AB},\mathbb{1}_A\otimes\sigma_B)$ , where $\rho_{AB}$ is the reduction of the pure $|\rho\rangle_{ABC}$ . Why: to bring $C$ in, lift the fidelity from $AB$ to purifications on $ABC$ .

Step 2. Apply Uhlmann's theorem: $F(\rho_{AB},\mathbb{1}_A\otimes\sigma_B)=\max_{|\phi\rangle}F(|\rho\rangle_{ABC},|\phi\rangle_{ABC})$ , over purifications $|\phi\rangle$ of $\mathbb{1}_A\otimes\sigma_B$ . Why: a mixed-state fidelity becomes a pure-state overlap $|\langle\rho|\phi\rangle|$ .

Step 3. Trace out $B$ . The freedom in $|\phi\rangle$ pushes the $\sigma_B$ -optimization onto the marginal $\rho_{AC}$ : the optimal fidelity becomes a bound $\rho_{AC}\le 2^{\mu}\,\mathbb{1}_A\otimes\sigma_C$ . Why: purifying the decoupled state and reducing onto $AC$ swaps $B$ for $C$ .

Step 4. Recognize the min-entropy SDP: $\rho_{AC}\le 2^{\mu}\,\mathbb{1}_A\otimes\sigma_C$ is Eq. (1) for $A|C$ with $\lambda=-\mu$ , so $H_{\min}(A|C)=-\mu$ . Why: the fidelity-saturating condition is exactly the inequality defining $H_{\min}(A|C)$ , sign flipped.

Step 5. Combine: $H_{\max}(A|B)=2\log_2 F=\mu=-H_{\min}(A|C)$ ; the smooth versions follow because purified-distance balls on $AB$ and $AC$ correspond under purification. Why: the construction is metric-preserving, so the identity lifts to the smoothed entropies. *Verified: for a pure $|\psi\rangle_{AB}$ the complement $C$ is trivial, so $H_{\max}(A|B)=-H_{\min}(A|C)=-H_{\min}(A)=\log_2\lambda_{\max}(\rho_A)$ and, by the dual reading, $H_{\min}(A|B)=-H_{\max}(A)=-2\log_2\mathrm{Tr}\sqrt{\rho_A}$ — both negative for an entangled state, the signature of quantum conditioning.*

Limiting cases

The smooth entropies interpolate a hierarchy of regimes; the corners are sanity checks.

Case	Result	Meaning
Product (independent) state	$\rho_{AB}=\rho_A\otimes\rho_B\;\Rightarrow\;H_{\min}(A\vert B)=H_{\min}(A),\ H_{\max}(A\vert B)=H_{\max}(A)$	Conditioning does nothing; the quantities reduce to the unconditional entropies of $\rho_A$ .
Pure entangled state	$\rho_{AB}=\vert\psi\rangle\langle\psi\vert\;\Rightarrow\;H_{\min}(A\vert B)=-H_{\max}(A)\le 0,\ H_{\max}(A\vert B)=-H_{\min}(A)\le 0$	Both go negative — the hallmark of entanglement, where an adversary out-guesses any classical correlation.
Classical uniform register	$\rho_{AB}=\tfrac{\mathbb{1}_A}{\vert A\vert}\otimes\rho_B\;\Rightarrow\;H_{\min}(A\vert B)=\log_2\vert A\vert$	Maximal min-entropy: $\log_2\vert A\vert$ bits of perfect, side-information-proof randomness.
Asymptotic i.i.d. limit (AEP)	$\lim_{n\to\infty}\tfrac1n H_{\min}^{\varepsilon}(A^n\vert B^n)=H(A\vert B)=\lim_{n\to\infty}\tfrac1n H_{\max}^{\varepsilon}(A^n\vert B^n)$	For fixed $\varepsilon\in(0,1)$ both converge to the von Neumann entropy — Shannon theory is the asymptotic shadow.
No error budget	$\varepsilon\to 0$	Smoothing off; the raw entropies return and turn brittle, often giving vacuous one-shot bounds — why $\varepsilon>0$ is mandatory.

Common trapMin- and max-entropy are just the log replaced by a min or max over eigenvalues

They are not. Min- and max-entropy are defined by semidefinite optimizations — an operator inequality for $H_{\min}$ , a fidelity for $H_{\max}$ — over an auxiliary state $\sigma_B$ , and the conditioning is genuinely quantum: $H_{\min}(A|B)$ can be negative, which no "smallest term of a Shannon sum" ever is. Three further traps. First, smoothing is not optional — without it the one-shot quantities are typically vacuous, driven to $\pm\infty$ by one negligible eigenvalue. Second, the $\varepsilon$ -ball must use the purified distance $P=\sqrt{1-F^2}$ , not the trace distance; only $P$ preserves duality under smoothing. Third, the AEP does not equate the smooth entropy with $H(A|B)$ at finite $n$ — only in the limit, with an $\mathcal{O}(1/\sqrt n)$ correction that is the whole point of finite-block analysis.

Worked examples

1 · The min–max sandwich of a single qubit (confidence builder)

A qubit $A$ is in the state $\rho_A=\mathrm{diag}(0.9,\,0.1)$ . Compute its unconditional min-entropy, von Neumann entropy, and max-entropy, and confirm their ordering.

Step 1. Min-entropy is minus the log of the largest eigenvalue: $H_{\min}(A)=-\log_2 0.9=\mathbf{0.152\ \text{bits}}$ . A near-certain outcome leaves little surprise.

Step 2. Von Neumann entropy is the Shannon entropy of the eigenvalues: $H(A)=-0.9\log_2 0.9-0.1\log_2 0.1=\mathbf{0.469}$ bits.

Step 3. Max-entropy is $2\log_2\mathrm{Tr}\sqrt{\rho_A}=2\log_2(\sqrt{0.9}+\sqrt{0.1})=\mathbf{0.678\ \text{bits}}$ .

Step 4. The sandwich holds: $0.152\le 0.469\le 0.678$ , and the gap $0.526$ bits is the room between a security estimate and a compression estimate for this qubit. H_min = 0.152, H = 0.469, H_max = 0.678 bits, correctly ordered.

2 · A pure entangled pair, where conditioning goes negative

Two qubits are in the pure Schmidt state $|\psi\rangle_{AB}=\sqrt{0.9}\,|00\rangle+\sqrt{0.1}\,|11\rangle$ , so $\rho_A=\mathrm{diag}(0.9,0.1)$ as above. Compute the three conditional entropies $H_{\min}(A|B)$ , $H(A|B)$ , $H_{\max}(A|B)$ .

Step 1. Use duality with the complement $C$ trivial (the state is already pure on $AB$ ): $H_{\min}(A|B)=-H_{\max}(A)=-0.678$ and $H_{\max}(A|B)=-H_{\min}(A)=-0.152$ , reusing Example 1. Both negative — the entanglement signature.

Step 2. For a pure bipartite state $H(A|B)=H(AB)-H(B)=0-H(B)$ . Since $\rho_B$ shares the spectrum $(0.9,0.1)$ , $H(B)=0.469$ , so $H(A|B)=\mathbf{-0.469}$ bits.

Step 3. The ordering holds among negatives: $-0.678\le-0.469\le-0.152$ . Negativity says an adversary holding $B$ guesses $A$ better than any classical side information allows, and quantifies distillable entanglement — the resource state merging gives back. H_min = −0.678, H = −0.469, H_max = −0.152 bits: all negative, still ordered.

3 · How much secret key survives privacy amplification

A finite QKD run leaves a raw string $A$ with smooth min-entropy $H_{\min}^{\varepsilon}(A|E)=1000$ bits against Eve's $E$ , at $\varepsilon=10^{-10}$ . How many bits of secure key can be extracted, and at what total security error?

Step 1. Fix the privacy-amplification error $\delta_{\mathrm{PA}}=2^{-30}\approx9.3\times10^{-10}$ . The leftover-hash toll is $2\log_2(1/\delta_{\mathrm{PA}})=2\times30=\mathbf{60\ \text{bits}}$ .

Step 2. Apply Eq. (6): $\ell=1000-60=\mathbf{940\ \text{bits}}$ of near-uniform, decoupled key.

Step 3. Add the error budget: the output is within trace distance $d\le 2\varepsilon+\delta_{\mathrm{PA}}=2\times10^{-10}+9.3\times10^{-10}=\mathbf{1.1\times10^{-9}}$ of an ideal key.

Step 4. The tradeoff: loosening $\varepsilon$ raises $H_{\min}^{\varepsilon}$ (more key) but degrades $d$ ; the 60-bit toll is fixed by the security level alone — halving the source to 500 bits still costs 60 bits, leaving 440. 940 secret bits at security 1.1×10⁻⁹, with a fixed 60-bit toll.

Physics of the portrait

Smooth entropies emerged not from coding theorems but from the practical demand of proving a real protocol secure against a finite, quantum adversary — and one thesis, more than any paper, created the framework.

Origins · 1 minRenato Renner and how this was discovered

Renato Renner

b. 1974 · founder of smooth-entropy / one-shot quantum information theory

Renato Renner is a Swiss physicist whose 2005 ETH Zurich doctoral thesis, Security of Quantum Key Distribution, written under Ueli Maurer, introduced the smooth min- and max-entropies and the modern one-shot framework. His problem was stubborn: existing QKD proofs handled only the asymptotic i.i.d. idealization, whereas any real device runs a finite session against an adversary who may hold a quantum system entangled with the raw key — and the von Neumann entropy could not certify such a run. Renner's move was to promote the min- and max-entropies — worst-case and best-case cousins of the Rényi entropies, whose classical smooth versions he and Stefan Wolf had introduced at ISIT in 2004 — to genuine quantum, conditional, smoothed quantities obeying a full calculus: duality under purification, data processing, chain rules, and a leftover hash lemma with explicit error. That calculus turned the abstract composable-security definition into a computable key-rate formula, and is now the backbone of every finite-key proof. With collaborators he established the operational meanings of the entropies (König, Schaffner, 2009), the fully quantum AEP that reconnects one-shot theory to Shannon's (Tomamichel, Colbeck, 2009), and the uncertainty relation with quantum memory (2010). A professor at ETH Zurich, his lasting stamp is that finite resources — the only kind that exist — finally acquired a rigorous entropy of their own.

History

1961

— Rényi defines his family of generalized entropies, the classical ancestors of the min- and max-entropy

2004

— Renner and Wolf introduce smooth Rényi entropies for classical one-shot coding

2005

— Renner's ETH thesis defines the quantum smooth min- and max-entropies and proves composable QKD security

2009

— König, Renner and Schaffner establish the operational meaning: guessing probability and decoupling fidelity

2009

— Tomamichel, Colbeck and Renner prove the fully quantum Asymptotic Equipartition Property

Going further

Texts and papers. Tomamichel, Quantum Information Processing with Finite Resources, Springer (2016), arXiv:1504.00233 — the standard monograph · Renner, Security of Quantum Key Distribution, PhD thesis, ETH Zurich (2005), arXiv:quant-ph/0512258 — the founding document · Wilde, Quantum Information Theory, 2nd ed., Cambridge (2017) · König, Renner and Schaffner, "The operational meaning of min- and max-entropy", IEEE Trans. Inf. Theory 55, 4337 (2009) · Tomamichel, Colbeck and Renner, "A fully quantum asymptotic equipartition property", IEEE Trans. Inf. Theory 55, 5840 (2009) · Datta, "Min- and max-relative entropies", IEEE Trans. Inf. Theory 55, 2816 (2009). For backdrop see Nielsen and Chuang, Watrous, and Preskill's lecture notes.

Provenance. The operator-inequality $H_{\min}$ and its guessing meaning are König–Renner–Schaffner (2009); min–max duality and purified-distance smoothing are in Tomamichel's monograph (2016) and Renner's thesis (2005); the fully quantum AEP is Tomamichel–Colbeck–Renner (2009); the leftover hash lemma against quantum side information is Renner (2005) and Tomamichel–Schaffner–Smith–Renner (2011). A verifier should confirm: (i) the SDP pair for $H_{\min}$ versus $p_{\mathrm{guess}}$ and $H_{\min}(A)=-\log_2\lambda_{\max}(\rho_A)$ , $H_{\max}(A)=2\log_2\mathrm{Tr}\sqrt{\rho_A}$ ; (ii) the qubit numbers $H_{\min}=0.152$ , $H=0.469$ , $H_{\max}=0.678$ bits for spectrum $(0.9,0.1)$ and their negatives in the pure conditional case; (iii) the leftover-hash arithmetic $\ell=1000-60=940$ with $d\le2\varepsilon+2^{-30}\approx1.1\times10^{-9}$ . Constants ( $c$ in the AEP, the variance $V$ ) are left symbolic to avoid fabrication.

Prerequisites. Von Neumann Entropy · Quantum Conditional Entropy and Mutual Information · Quantum Relative Entropy · Data-Processing Inequality · Stinespring Dilation Theorem. Leads to. Holevo Bound · Strong Subadditivity of Quantum Entropy · Complementary Channels and Degradability.

Ask the tutor: Ask me to run the min-entropy SDP on a state of your choosing, or to walk a full finite-key QKD rate from raw error rate to extracted secret bits.

Why can the conditional min-entropy be negative when Shannon entropies never are?

Because quantum conditioning is not classical averaging. Operationally $H_{\min}(A|B)=-\log_2 p_{\mathrm{guess}}(A|B)$ , and when $A$ and $B$ are entangled an adversary holding $B$ guesses $A$ with probability exceeding $1/|A|$ — better than any classical correlation permits — so $H_{\min}$ can fall below zero. For a maximally entangled pair the adversary guesses perfectly, giving $H_{\min}(A|B)=0$ . Negativity is a genuine physical signal: it certifies entanglement and a distillable resource, which is why state merging can return entanglement rather than consume it.

What exactly does smoothing do, and why the purified distance?

Smoothing optimizes the entropy over a ball of states within purified distance $\varepsilon$ of the true state, so the answer reflects only what matters up to the tolerated error. A single eigenvalue of weight $2^{-100}$ would crush the raw min-entropy, but an event that rare is irrelevant if you accept $\varepsilon=10^{-9}$ — smoothing discards such tails, returning the largest min-entropy compatible with the budget. The metric must be the purified distance $P=\sqrt{1-F^2}$ , not the trace distance, because only $P$ is compatible with purification, making min–max duality survive smoothing.

How is the min-entropy actually computed for a given state?

As a semidefinite program. After $\sigma_B'=2^{-\lambda}\sigma_B$ , Eq. (1) becomes $2^{-H_{\min}}=\min\{\mathrm{Tr}\,\sigma_B':\ \sigma_B'\ge0,\ \rho_{AB}\le\mathbb{1}_A\otimes\sigma_B'\}$ — a standard SDP any convex solver handles in time polynomial in the dimension, and its dual is the guessing SDP, so one solve gives both. Special cases are closed-form, e.g. $H_{\min}(A)=-\log_2\lambda_{\max}(\rho_A)$ . Smoothing adds an outer convex optimization over the $\varepsilon$ -ball, so $H_{\min}^{\varepsilon}$ stays efficiently computable, though the problem size grows with the joint dimension of $A$ and $B$ .

Does the AEP make smooth entropy just a fancy von Neumann entropy?

No — it makes von Neumann entropy the large- $n$ shadow of smooth entropy, not the reverse. The AEP says $\tfrac1n H_{\min/\max}^{\varepsilon}(A^n|B^n)\to H(A|B)$ for i.i.d. copies, so in that limit the family collapses to one number. But real resources are finite and often not i.i.d., and there the smooth entropies differ from $H(A|B)$ by an $\mathcal{O}(1/\sqrt n)$ correction that is the whole content of finite-block coding. The smooth theory strictly contains the asymptotic one, additionally certifying single-shot tasks von Neumann entropy cannot touch.

Why are there two entropies rather than one, and which do I use?

Because a one-shot task is either pessimistic or optimistic. Anything about security or extraction — secret key, extractable randomness, an adversary's smallest surprise — is worst-case and uses the smooth min-entropy. Anything about cost or size — qubits to compress, entanglement to merge, how well a state decouples — is best-case and uses the smooth max-entropy. Rule of thumb: if a bigger number helps you (more key) it is a min-entropy; if a smaller number helps (cheaper compression) it is a max-entropy. Duality makes them two readings of one pure state.

Where does the "minus 2 log(1 over δ)" toll in privacy amplification come from?

It is the universal price of turning an entropy lower bound into a near-uniformity guarantee. The leftover hash lemma bounds the output's distance from ideal by $\tfrac12\,2^{-\frac12(H_{\min}^{\varepsilon}-\ell)}$ , so forcing that below $\delta_{\mathrm{PA}}$ needs a gap $H_{\min}^{\varepsilon}-\ell\ge 2\log_2(1/\delta_{\mathrm{PA}})$ ; solving gives $\ell=H_{\min}^{\varepsilon}-2\log_2(1/\delta_{\mathrm{PA}})$ . The factor of two is the square-root in the fidelity bound, and the toll depends only on the security level, not the source.