Concentration of Purity (Lévy’s Lemma)

Haar Measure & Weingarten Calculus, numerical solution.

Concentration of Purity (Lévy’s Lemma)

Background

The purity \(\gamma = \mathrm{Tr}(\rho_A^2)\) is a single number that reports how mixed a subsystem is. It equals one when the subsystem is in a pure state and falls to \(1/m\) when the reduction of dimension \(m\) is maximally mixed, so it serves as a quick proxy for entanglement without requiring the full entropy. For a global pure state drawn from the Haar measure, the purity of a subsystem becomes a random variable.

Its average is known in closed form, \((m+n)/(mn+1)\) for subsystem dimension \(m\) and complement dimension \(n\), and what matters more is how little it fluctuates. As the total dimension grows the variance of the purity collapses, so nearly every random state yields almost the same subsystem purity. This shrinking spread is concentration of measure seen in a specific observable.

Lévy’s lemma turns the observation into a quantitative bound. For a function on the space of pure states that does not change too steeply, the lemma states that the probability of straying from the mean by more than a fixed amount decays exponentially in the Hilbert space dimension. Applied to the purity, whose steepness is controlled by a fixed constant, it shows that deviations are suppressed exponentially in the number of qubits.

This is the engine behind quantum typicality, the principle that one random state can represent the whole ensemble. The notebook makes the bound concrete, finding that already around twenty-two qubits a deviation of more than \(0.01\) from the mean has probability below one in a million, and it watches the purity distribution narrow as the dimension increases.

Mathematical background

The sharpness of typicality is controlled by concentration of measure on the sphere \(S^{2D-1}\) of pure states. Let \(f(\psi) = \langle\psi|\mathcal{O}_A|\psi\rangle\) for an observable \(\mathcal{O}_A\) acting on subsystem \(A\). This function is Lipschitz with constant \(2\|\mathcal{O}_A\|\), and Lévy’s lemma bounds its fluctuations around the Haar mean,

\[ \Pr\big(|f(\psi) - \mathbb{E}[f]| > \epsilon\big) \le 2\exp\!\Big(\!-\frac{C D \epsilon^2}{\|\mathcal{O}_A\|^2}\Big), \]

with \(C\) a constant of order one and the mean fixed by the maximally mixed state, \(\mathbb{E}[f] = \mathrm{Tr}(\mathcal{O}_A\,\mathbb{I}_A/m)\). The deviation probability is exponentially small in the full dimension \(D = mn\), so for almost every pure state the reduced matrix satisfies \(\rho_A \approx \mathbb{I}_A/m\) up to corrections that vanish as the environment grows. The purity is the corresponding two-copy quantity, and its Haar average \((m+n)/(mn+1)\) sits within \(\mathcal{O}(1/n)\) of the maximally mixed value \(1/m\). Typicality of this kind is kinematic, a property of Hilbert-space geometry alone, and needs no assumption about dynamics or equilibration.

Motivation

Concentration of measure is the mathematical mechanism behind quantum typicality: for Haar-random states in high-dimensional Hilbert spaces, observables such as entanglement entropy and purity are sharply concentrated around their mean values. Lévy’s lemma provides the quantitative bound, the probability of a deviation \(\epsilon\) from the mean decays exponentially in the Hilbert space dimension \(D\). This exercise applies Lévy’s lemma to the purity, showing that in multi-qubit systems, virtually every random state has nearly the same subsystem purity.

Preliminaries / Toolbox

1. Purity: The purity of a state \(\rho\) is \(\gamma = \mathrm{Tr}(\rho^2)\). For pure states \(\gamma = 1\), and for maximally mixed states \(\gamma = 1/D\).

2. Haar Measure: The uniform distribution over the unitary group \(U(D)\). Integrals over polynomials of \(U_{ij}\) and \(\bar{U}_{kl}\) can be evaluated using Weingarten calculus.

3. Lévy’s Lemma: Given a Lipschitz-continuous function \(f: \mathbb{S}^{2D-1} \to \mathbb{R}\) on the unit hypersphere, the probability that \(f(|\psi\rangle)\) deviates from its median by more than \(\epsilon\) decays exponentially with dimension \(D\): \(\Pr(|f - \bar{f}| \geq \epsilon) \leq 2 \exp\left(- \frac{C D \epsilon^2}{\eta^2}\right)\).

4. Partial Trace: The reduced density matrix of subsystem \(A\) is \(\rho_A = \mathrm{Tr}_B(|\psi\rangle\langle\psi|)\), where \(|\psi\rangle\) is a bipartite state on \(\mathcal{H}_A \otimes \mathcal{H}_B\).

Exercise

The purity \(\gamma = \mathrm{Tr}(\rho_A^2)\) of a Haar-random state has mean \(\mathbb{E}[\gamma] = (m+n)/(mn+1)\). The function \(f(\psi) = \mathrm{Tr}(\rho_A^2)\) is Lipschitz with constant \(\eta_f = 4\).

(a) Using Lévy’s lemma, write the concentration bound \(\Pr(|\gamma - \mathbb{E}[\gamma]| > \epsilon)\).

(b) For an equal bipartition (\(m = n = 2^{N/2}\)), find the minimum \(N\) such that \(\Pr(\gamma > \mathbb{E}[\gamma] + 0.01) < 10^{-6}\).

Solution

Part (a): Lévy’s lemma bound

Lévy’s lemma states: if \(f: S^{2D-1} \to \mathbb{R}\) is Lipschitz with constant \(\eta_f\), then for Haar-random \(|\psi\rangle\):

\[ \Pr\!\left(|f(\psi) - \mathbb{E}[f]| > \epsilon\right) \leq 2\exp\!\left(-\frac{c\, D\, \epsilon^2}{\eta_f^2}\right), \]

where \(c > 0\) is a universal constant of order unity and \(D = mn\) is the total Hilbert space dimension.

For the purity with \(\eta_f = 4\):

\[ \boxed{\Pr\!\left(|\gamma - \mathbb{E}[\gamma]| > \epsilon\right) \leq 2\exp\!\left(-\frac{c\, D\, \epsilon^2}{16}\right).} \]

The concentration is exponentially tight in \(D\): doubling the number of qubits squares the Hilbert space dimension and drives the failure probability to zero exponentially fast.

Part (b): Critical qubit number

For the equal bipartition \(m = n = 2^{N/2}\), we have \(D = 2^N\). The condition is:

\[ 2\exp\!\left(-\frac{c \cdot 2^N \cdot 10^{-4}}{16}\right) < 10^{-6}. \]

Taking logarithms (with \(c \approx 1\)):

\[ \frac{2^N \cdot 10^{-4}}{16} > \ln(2 \times 10^6) \approx 14.5. \]

\[ 2^N > \frac{16 \times 14.5}{10^{-4}} \approx 2.3 \times 10^6. \]

Since \(2^{21} \approx 2.1 \times 10^6\) and \(2^{22} \approx 4.2 \times 10^6\):

\[ \boxed{N \geq 22 \text{ qubits}.} \]

With just 22 qubits (a 22-qubit Hilbert space of dimension \(\sim 4 \times 10^6\)), the probability that the purity deviates by more than 0.01 from its mean is less than one in a million. This extreme concentration is why typicality arguments are so powerful in quantum many-body physics.

Symbolic Verification (SymPy)

Code

import sympy as sp

d_A, d_B = sp.symbols('d_A d_B', positive=True, integer=True)
D = d_A * d_B

# Page formula for expected purity of subsystem A
# E[Tr(rho_A^2)] = (d_A + d_B) / (d_A * d_B + 1)
E_purity = (d_A + d_B) / (D + 1)
print(f'E[purity_A] = {E_purity}')

# For equal bipartition d_A = d_B = d
d = sp.Symbol('d', positive=True, integer=True)
E_equal = E_purity.subs([(d_A, d), (d_B, d)])
print(f'Equal bipartition: E[purity] = {sp.simplify(E_equal)}')

# Large d limit: E[purity] -> 2d/(d^2+1) -> 2/d
print(f'Large d limit: {sp.limit(E_equal, d, sp.oo)} (maximally mixed = 1/d)')

# Numerical values
for n in [2, 4, 8, 16]:
    val = float(2*n / (n**2 + 1))
    print(f'  d={n:3d}: E[purity] = {val:.6f}, 1/d = {1/n:.6f}')

E[purity_A] = (d_A + d_B)/(d_A*d_B + 1)
Equal bipartition: E[purity] = 2*d/(d**2 + 1)
Large d limit: 0 (maximally mixed = 1/d)
  d=  2: E[purity] = 0.800000, 1/d = 0.500000
  d=  4: E[purity] = 0.470588, 1/d = 0.250000
  d=  8: E[purity] = 0.246154, 1/d = 0.125000
  d= 16: E[purity] = 0.124514, 1/d = 0.062500

Numerical Verification

We verify concentration at small \(N\) by sampling Haar-random states and checking the purity distribution.

Code

import numpy as np
from scipy.stats import unitary_group

np.random.seed(42)

print(f"{'N':>3s}  {'m':>4s}  {'D':>6s}  {'E[γ] (MC)':>10s}  {'(m+n)/(mn+1)':>14s}  {'std(γ)':>8s}")
print(f"{'─'*3:>3s}  {'─'*4:>4s}  {'─'*6:>6s}  {'─'*10:>10s}  {'─'*14:>14s}  {'─'*8:>8s}")

for N in [4, 6, 8]:
    m = 2**(N//2)
    n = m
    D = m * n
    E_gamma_pred = (m + n) / (m*n + 1)

    n_samples = min(5000, max(500, 100000//D))
    purities = []
    for _ in range(n_samples):
        psi = unitary_group.rvs(D)[:, 0]
        rho = np.outer(psi, psi.conj()).reshape(m, n, m, n)
        rho_A = np.trace(rho, axis1=1, axis2=3)
        purities.append(np.trace(rho_A @ rho_A).real)

    purities = np.array(purities)
    E_gamma = np.mean(purities)
    std_gamma = np.std(purities)

    print(f"{N:3d}  {m:4d}  {D:6d}  {E_gamma:10.4f}  {E_gamma_pred:14.4f}  {std_gamma:8.4f}")
    assert abs(E_gamma - E_gamma_pred) < 0.02

print("\nConcentration sharpens with D: std(γ) → 0.")

  N     m       D   E[γ] (MC)    (m+n)/(mn+1)    std(γ)
───  ────  ──────  ──────────  ──────────────  ────────

  4     4      16      0.4696          0.4706    0.0670

  6     8      64      0.2456          0.2462    0.0209

  8    16     256      0.1244          0.1245    0.0053

Concentration sharpens with D: std(γ) → 0.

Visual Pedagogical Proof

Code

import matplotlib.pyplot as plt
from scipy.stats import unitary_group

np.random.seed(42)
purities_8 = []
purities_16 = []

for _ in range(500):
    psi8 = unitary_group.rvs(8)[:, 0]
    rho8 = psi8.reshape(2, 4) @ psi8.reshape(2, 4).conj().T
    purities_8.append(np.trace(rho8 @ rho8).real)

    psi16 = unitary_group.rvs(16)[:, 0]
    rho16 = psi16.reshape(4, 4) @ psi16.reshape(4, 4).conj().T
    purities_16.append(np.trace(rho16 @ rho16).real)

plt.rcParams['figure.dpi'] = 150
plt.figure(figsize=(7, 4.5))
plt.hist(purities_8, bins=30, alpha=0.6, color='crimson', label='D=8 (Subsystem d=2)')
plt.hist(purities_16, bins=30, alpha=0.6, color='royalblue', label='D=16 (Subsystem d=4)')

plt.xlabel(r"Subsystem Purity $\gamma$")
plt.ylabel("Frequency")
plt.title("Concentration of Measure: Subsystem Purity")
plt.axvline(1/2, color='crimson', linestyle='dashed', label='Max Mixed d=2')
plt.axvline(1/4, color='royalblue', linestyle='dashed', label='Max Mixed d=4')
plt.legend()
plt.grid(True, ls="--", alpha=0.5)
plt.tight_layout()
plt.show()

Takeaway

The subsystem purity concentrates on its mean \((m+n)/(mn+1)\) with a spread that shrinks exponentially in the qubit number, so by around 22 qubits a deviation past \(0.01\) has probability below one in a million. A single random state then reproduces the ensemble-averaged purity.

Connections

The collapse of purity fluctuations as the dimension grows is concentration of measure, the same effect behind the Page formula and the overlap distribution. In quantum machine learning it reappears with the opposite sign of usefulness, where the kernel and feature values concentrate so tightly that the data they encode becomes invisible.

References

Ledoux, The concentration of measure phenomenon, American Mathematical Society (2001).
Popescu et al., Entanglement and the foundations of statistical mechanics, Nature Physics (2006).
Goldstein et al., Canonical typicality, Physical Review Letters (2006).
Hayden et al., Randomizing Quantum States: Constructions and Applications, Communications in Mathematical Physics (2004). doi
Płodzień, Information Scrambling, Quantum Chaos, and Haar-Random States, lecture notes (2025). arXiv:2511.14397