This exercise bridges the abstract formalism of σ-algebras and measurable functions to the concrete quantum information quantities that we integrate against the Haar measure throughout the book. We verify that familiar functions, the survival probability \(|\langle 0|U|0\rangle|^2\) and the entanglement entropy \(S(\mathrm{Tr}_B[U|00\rangle\!\langle 00|U^\dagger])\), are Borel-measurable on the unitary group, and hence legitimate integrands for Haar averaging. The exercise also constructs the σ-algebra of the finite Pauli group to ground the abstract axioms in a hands-on computation.
Background
Writing down an average of a function over the unitary group quietly assumes that the function can be integrated, and integration in turn requires the function to be measurable. Measurable means that the set of inputs landing in any chosen interval is one the measure knows how to weigh, that is, a Borel set. Without this property the integral that defines a Haar average would have no meaning, so measurability is the entry ticket for any quantity we want to average.
Continuous functions pass this test for free. A continuous function pulls every open set back to an open set, and the open sets are exactly what generate the Borel \(\sigma\)-algebra, so the preimage of any Borel set is again Borel. Since the quantities averaged over \(U(D)\) throughout the book depend continuously on the matrix entries of \(U\), each one is automatically a legitimate integrand and the averages are well posed.
In practice one checks measurability by breaking a function into continuous building blocks and using the fact that composing continuous maps stays continuous. The survival probability \(|\langle 0|U|0\rangle|^2\) is a polynomial in the entries of \(U\) and so is continuous outright. The entanglement entropy takes more steps, passing through a partial trace and then the continuous map \(-x\log x\) applied to the eigenvalues of the reduced state, yet each step preserves continuity. On a finite group like the Pauli group the question evaporates, because every subset belongs to the \(\sigma\)-algebra and so every function is measurable.
The notebook follows both functions through their continuous steps and contrasts them with the finite-group case.
1. Physical Motivation
Every time we write an expression like \[
\mathbb{E}_U\bigl[f(U)\bigr] = \int_{U(D)} f(U)\, d\mu_{\mathrm{Haar}}(U),
\] we are implicitly assuming that \(f\) is a measurable function on \(U(D)\), that is, a function whose domain and range are compatible with the σ-algebras in play. Without this property, the integral is undefined.
But what does ‘measurable function’ actually mean? And for the functions we care about, fidelities, entropies, OTOCs, cost function gradients, why are they measurable?
The short answer is: continuous functions are automatically measurable. For the functions in this book, measurability follows because they can be decomposed into a chain of continuous operations (matrix entry extraction → polynomial combination → eigenvalue computation → entropy evaluation). This exercise makes each step explicit.
The final part constructs the power-set σ-algebra of the finite Pauli group, showing that for finite groups the measurability question is trivial, every function is measurable, and only becomes nontrivial for continuous groups like \(U(D)\).
2. Mathematical Toolbox
We first recall the key definitions (introduced in Section 1.13 and the companion exercise on Lebesgue/counting measures) and then add the tools specific to measurable functions.
Recall: \(\Omega\), \(\mathcal{F}\), \(\mu\), and what ‘measurable’ means.
\(\Omega\) is the sample space (e.g., \(U(D)\), \(\mathbb{R}\), or a finite group).
\(\mathcal{F}\) is a σ-algebra on \(\Omega\): a collection of subsets of \(\Omega\) closed under complements and countable unions. A subset \(A \subseteq \Omega\) is called measurable if \(A \in \mathcal{F}\), meaning we can assign it a well-defined size \(\mu(A)\). A non-measurable subset (\(A \notin \mathcal{F}\)) cannot be assigned any consistent size at all.
\(\mu: \mathcal{F} \to [0,\infty]\) is a measure, the size assignment. The triple \((\Omega, \mathcal{F}, \mu)\) is a measure space.
Tool 1, Borel σ-algebra. When \(\Omega\) is a topological space (i.e., it has a notion of ‘open sets’, for example, \(U(D)\) with the matrix-entry topology), the Borel σ-algebra\(\mathcal{B}(\Omega)\) is the smallest σ-algebra containing all open sets. It contains all open sets, all closed sets, all countable intersections of open sets, and so on. For the unitary group: \(\mathcal{F} = \mathcal{B}(U(D))\). This is the σ-algebra on which the Haar measure lives.
Tool 2, Measurable functions. A function \(f: \Omega \to \mathbb{R}\) is called Borel-measurable (or simply ‘measurable’) if it is compatible with the σ-algebras: for every Borel set \(B \subseteq \mathbb{R}\), the preimage \(f^{-1}(B) = \{\omega \in \Omega : f(\omega) \in B\}\) belongs to \(\mathcal{F}\). Equivalently, for every \(a \in \mathbb{R}\), the set \(\{\omega : f(\omega) \leq a\}\) is in \(\mathcal{F}\). This ensures that questions like ‘what is the probability that \(f(U)\) lies in \([0.3, 0.7]\)?’ have well-defined answers.
Tool 3, Continuous ⟹ measurable. If \(f: \Omega \to \mathbb{R}\) is continuous, then \(f\) is automatically Borel-measurable. The reason: continuous functions pull open sets back to open sets, and open sets are in \(\mathcal{B}(\Omega)\) by definition. This is the key fact that makes almost every function in quantum information measurable.
Tool 4, Composition rule. If \(f\) and \(g\) are both continuous (or both measurable), then the composition \(g \circ f\) is also continuous (or measurable). This lets us build complex measurable functions from simple ones by chaining operations.
Tool 5, Eigenvalue continuity. For an \(n \times n\) Hermitian matrix \(H\) with eigenvalues \(\lambda_1 \leq \cdots \leq \lambda_n\), each \(\lambda_k(H)\) is a continuous function of the matrix entries. This follows from the Weyl perturbation inequality: \(|\lambda_k(H) - \lambda_k(H')| \leq \|H - H'\|_{\mathrm{op}}\).
Tool 6, Partial trace. For a bipartite Hilbert space \(\mathcal{H}_A \otimes \mathcal{H}_B\), the partial trace \(\mathrm{Tr}_B[\hat{\rho}]\) has matrix entries that are sums of products of entries of \(\hat{\rho}\), i.e., the partial trace is a linear (hence continuous) map. Therefore \(U \mapsto \mathrm{Tr}_B[U|00\rangle\!\langle 00|U^\dagger]\) is continuous.
Tool 7, Power-set σ-algebra. For a finite set \(\Omega\) with \(|\Omega| = n\), the power set \(2^\Omega\) (the collection of all subsets) is trivially a σ-algebra with \(|2^\Omega| = 2^n\) elements. Every subset is measurable, every function is measurable. The nontrivial σ-algebra structure arises only for infinite/continuous spaces.
3. Exercise
(a) Survival probability is Borel-measurable. For \(\Omega = U(2)\) and \(f(U) = |\langle 0|U|0\rangle|^2\), prove that \(f\) is Borel-measurable by showing it is a composition of continuous functions.
(b) Entanglement entropy is Borel-measurable. For \(U \in U(4)\), the entanglement entropy \(S(U) = -\mathrm{Tr}[\hat{\rho}_A \log \hat{\rho}_A]\) with \(\hat{\rho}_A = \mathrm{Tr}_B[U|00\rangle\!\langle 00|U^\dagger]\) is measurable. Trace through the chain: matrix entries → partial trace → eigenvalues → entropy.
(c) Power-set σ-algebra of \(\mathcal{P}_N\). On the Pauli group \(\mathcal{P}_N = \{I, X, Y, Z\}^{\otimes N}\) (ignoring phases), verify axioms (S1)-(S3) for \(2^{\mathcal{P}_N}\), and compute \(|2^{\mathcal{P}_N}|\) for \(N = 1, 2\).
4. Analytical Derivation
Part (a): \(f(U) = |U_{00}|^2\) is continuous
We decompose \(f\) into a chain of two continuous maps: \[
U \xrightarrow{\text{step 1: extract entry}} U_{00} \xrightarrow{\text{step 2: squared modulus}} |U_{00}|^2
\]
Step 1: The map \(U \mapsto U_{00}\) extracts the \((0,0)\) entry of the matrix. This is a coordinate projection from \(\mathbb{C}^{D \times D}\) to \(\mathbb{C}\), a linear map, hence continuous.
Step 2: The map \(z \mapsto |z|^2 = z\bar{z}\) is a polynomial in \(\mathrm{Re}(z)\) and \(\mathrm{Im}(z)\): \(|z|^2 = (\mathrm{Re}\,z)^2 + (\mathrm{Im}\,z)^2\). Polynomials are continuous.
By the composition rule (Tool 4), \(f = |\cdot|^2 \circ \pi_{00}\) is continuous, hence Borel-measurable by Tool 3. \(\square\)
Part (b): \(S(U)\) is continuous
We decompose the entropy into a chain of four continuous operations: \[
U \xrightarrow{\text{(i)}} \hat{\rho} = U|00\rangle\!\langle 00|U^\dagger \xrightarrow{\text{(ii)}} \hat{\rho}_A = \mathrm{Tr}_B[\hat{\rho}] \xrightarrow{\text{(iii)}} (\lambda_1, \lambda_2) \xrightarrow{\text{(iv)}} S = -\sum_i \lambda_i \log \lambda_i
\]
Each step is continuous:
(i)\(U \mapsto U|00\rangle\!\langle 00|U^\dagger\): the entries of \(\hat{\rho}\) are \(\hat{\rho}_{ij} = U_{i0}\overline{U_{j0}}\), products of matrix entries, hence continuous (polynomials).
(ii)\(\hat{\rho} \mapsto \mathrm{Tr}_B[\hat{\rho}]\): partial trace is a linear map, each entry of \(\hat{\rho}_A\) is a sum of entries of \(\hat{\rho}\), hence continuous (Tool 6).
(iii)\(\hat{\rho}_A \mapsto (\lambda_1, \lambda_2)\): eigenvalues of a Hermitian matrix depend continuously on the matrix entries (Tool 5, Weyl inequality).
(iv)\((\lambda_1, \lambda_2) \mapsto -\sum_i \lambda_i \log \lambda_i\): the function \(h(x) = -x \log x\) is continuous on \([0,1]\) (with \(h(0) = 0\) by convention), so \(S = h(\lambda_1) + h(\lambda_2)\) is continuous.
By repeated application of the composition rule, \(S(U)\) is a continuous function of the matrix entries of \(U\), hence Borel-measurable. \(\square\)
Part (c): Power-set σ-algebra
For a finite set \(\Omega = \mathcal{P}_N\) with \(|\Omega| = 4^N\) elements, \(\mathcal{F} = 2^\Omega\) satisfies the three σ-algebra axioms:
(S1)\(\Omega \in 2^\Omega\): trivially, \(\Omega\) is a subset of itself.
(S2) If \(A \in 2^\Omega\), then \(\Omega \setminus A \in 2^\Omega\): every subset of a finite set is in its power set.
(S3) If \(A_1, A_2, \ldots \in 2^\Omega\), then \(\bigcup_k A_k \subseteq \Omega\), hence \(\bigcup_k A_k \in 2^\Omega\).
The number of elements: \(|2^{\mathcal{P}_N}| = 2^{4^N}\). - \(N = 1\): \(|2^{\mathcal{P}_1}| = 2^4 = 16\). - \(N = 2\): \(|2^{\mathcal{P}_2}| = 2^{16} = 65{,}536\).
Physical insight: For finite groups, every subset is measurable (it belongs to the σ-algebra), and every function is measurable. This is why the ‘average over Paulis’ \(\frac{1}{4^N}\sum_P f(P)\) never requires σ-algebra considerations. The nontrivial structure, which subsets are measurable and which are not, only appears for continuous groups like \(U(D)\).
5. Symbolic Verification (SymPy)
Code
import sympy as sp# ── Part (a): f(U) = |U₀₀|² is a polynomial ─────────────────────# Show that f is a polynomial in Re(U₀₀) and Im(U₀₀),# hence continuous → Borel-measurable.x, y = sp.symbols('x y', real=True) # x = Re(U₀₀), y = Im(U₀₀)z = x + sp.I * y # U₀₀ = x + iyf_symbolic = sp.Abs(z)**2f_expanded = sp.expand(sp.re(z * sp.conjugate(z)))print(f'f(U) = |U₀₀|² = |x + iy|² = {f_expanded}')print(f'This is the polynomial x² + y² → continuous → measurable ')assert f_expanded == x**2+ y**2
f(U) = |U₀₀|² = |x + iy|² = x**2 + y**2
This is the polynomial x² + y² → continuous → measurable
Code
# ── Part (b): Symbolic chain for entanglement entropy ─────────────# For a 2-qubit state |ψ⟩ = U|00⟩, compute ρ_A symbolically.a, b, c, d = sp.symbols('a b c d')# |ψ⟩ = a|00⟩ + b|01⟩ + c|10⟩ + d|11⟩psi = sp.Matrix([a, b, c, d])rho = psi * psi.adjoint()# Step (ii): Partial trace over qubit B# ρ_A[i,j] = Σ_k ρ[2i+k, 2j+k] for i,j ∈ {0,1}rho_A = sp.zeros(2, 2)for i inrange(2):for j inrange(2):for k inrange(2): rho_A[i, j] += rho[2*i + k, 2*j + k]print('ρ_A = Tr_B[|ψ⟩⟨ψ|] =')sp.pprint(sp.simplify(rho_A))# Bell state: a=1/√2, b=0, c=0, d=1/√2subs_bell = {a: 1/sp.sqrt(2), b: 0, c: 0, d: 1/sp.sqrt(2)}rho_A_bell = rho_A.subs(subs_bell)print('\nBell state ρ_A =')sp.pprint(sp.simplify(rho_A_bell))# Step (iii): Eigenvalues (as {eigenvalue: multiplicity})eigs_bell = rho_A_bell.eigenvals()print(f'\nEigenvalues: {eigs_bell}')# Step (iv): Entropy S = -Σ λ log λ, weighting each eigenvalue by its multiplicityS_bell =sum(-lam * sp.log(lam) * mult for lam, mult in eigs_bell.items() if lam >0)S_bell_simplified = sp.simplify(S_bell)print(f'S(Bell) = {S_bell_simplified} = {float(S_bell_simplified):.6f}')assertabs(float(S_bell_simplified) -float(sp.log(2))) <1e-10print(f'Expected: log(2) = {float(sp.log(2)):.6f} ')
import numpy as npfrom scipy.stats import unitary_groupfrom scipy.linalg import expm# ── Part (a): Numerical continuity of f(U) = |⟨0|U|0⟩|² ────────# We demonstrate that small changes in U produce small changes in f.# This is continuity - and continuous → Borel-measurable.D =2np.random.seed(42)U0 = unitary_group.rvs(D)def f_survival(U):"""Survival probability |⟨0|U|0⟩|² - a measurable function on U(2)."""returnfloat(np.abs(U[0, 0])**2)f0 = f_survival(U0)print(f'Reference: f(U₀) = |⟨0|U₀|0⟩|² = {f0:.10f}')print()# Perturb U₀ in a fixed direction in the Lie algebra u(2)A_base = np.random.randn(D, D) +1j* np.random.randn(D, D)A_base = (A_base - A_base.conj().T) /2# anti-HermitianA_base /= np.linalg.norm(A_base)print('Continuity: perturbation size vs function change')print('='*55)print(f'{"||δU||":>12s}{"δf = |f(U₀+δU) - f(U₀)|":>25s}{"ratio δf/||δU||":>16s}')print('-'*55)for eps in [1e-1, 1e-2, 1e-3, 1e-4, 1e-6, 1e-8, 1e-10]: U_pert = expm(eps * A_base) @ U0 delta_U = np.linalg.norm(U_pert - U0, 'fro') delta_f =abs(f_survival(U_pert) - f0) ratio = delta_f / delta_U if delta_U >0else0print(f'{delta_U:12.2e}{delta_f:25.2e}{ratio:16.4f}')U_tiny = expm(1e-12* A_base) @ U0assertabs(f_survival(U_tiny) - f0) <1e-10print()print('δf → 0 as δU → 0: f(U) is continuous → Borel-measurable ')
# ── Bonus: Verify S has the correct range ────────────────────────# For 2 qubits: S ∈ [0, log 2].# Product state: U = I → |ψ⟩ = |00⟩ → S = 0S_product = entanglement_entropy(np.eye(D, dtype=complex))print(f'Product state (U = I): S = {S_product:.10f} (expected 0)')assertabs(S_product) <1e-12# Bell state: CNOT · (H ⊗ I) → |ψ⟩ = (|00⟩+|11⟩)/√2 → S = log 2H_gate = np.array([[1, 1], [1, -1]], dtype=complex) / np.sqrt(2)CNOT = np.array([[1,0,0,0],[0,1,0,0],[0,0,0,1],[0,0,1,0]], dtype=complex)U_bell = CNOT @ np.kron(H_gate, np.eye(2))S_bell = entanglement_entropy(U_bell)print(f'Bell state: S = {S_bell:.10f} (expected log2 = {np.log(2):.10f})')assertabs(S_bell - np.log(2)) <1e-10# Random Haar: S concentrates near the Page value.# Exact Page formula for d_A = d_B = 2:# <S> = H(d_A·d_B) - H(d_B) - (d_A-1)/(2 d_B)# = H(4) - H(2) - 1/4 = 7/12 - 1/4 = 1/3.S_random = [entanglement_entropy(unitary_group.rvs(D)) for _ inrange(500)]S_page =1/3# Exact Page average for d_A = d_B = 2print(f'\nRandom Haar (500 samples):')print(f' Mean S = {np.mean(S_random):.6f} (Page prediction: {S_page:.6f})')print(f' Std S = {np.std(S_random):.6f}')assertabs(np.mean(S_random) - S_page) <0.05print(' Consistent with Page formula ')
Product state (U = I): S = -0.0000000000 (expected 0)
Bell state: S = 0.6931471806 (expected log2 = 0.6931471806)
Random Haar (500 samples):
Mean S = 0.335192 (Page prediction: 0.333333)
Std S = 0.175040
Consistent with Page formula
Code
# ── Part (c): Power-set σ-algebra of the Pauli group ─────────────from itertools import product as iterproductprint('Verifying σ-algebra axioms (S1)-(S3) for F = 2^{P_N}')print('='*55)for N_val in [1, 2]: pauli_labels = ['I', 'X', 'Y', 'Z'] P_N =list(iterproduct(pauli_labels, repeat=N_val)) P_N_str = [''.join(p) for p in P_N] omega =frozenset(P_N_str) size_P =len(P_N_str) size_powerset =2**size_Pprint(f'\nN = {N_val}:')print(f' Ω = P_N with |Ω| = 4^{N_val} = {size_P}')print(f' F = 2^Ω (power set) with |F| = 2^{size_P} = {size_powerset:,}')print(f' Every subset of Ω is measurable (belongs to F).')# (S1): Ω ∈ Fassert omega ==frozenset(P_N_str)print(f' (S1) Ω ∈ F: True ')# (S2): Complement closure A =frozenset(P_N_str[:3]) A_comp = omega - Aassert A_comp.issubset(omega) andlen(A) +len(A_comp) == size_Pprint(f' (S2) A^c ∈ F (|A|={len(A)}, |A^c|={len(A_comp)}): True ')# (S3): Union closure A1 =frozenset(P_N_str[:2]) A2 =frozenset(P_N_str[2:5]) A3 =frozenset(P_N_str[1:4]) union = A1 | A2 | A3assert union.issubset(omega)print(f' (S3) A₁ ∪ A₂ ∪ A₃ ∈ F (|∪| = {len(union)}): True ')print()print('Summary:')print(' N=1: |2^{P_1}| = 2^4 = 16 ')print(' N=2: |2^{P_2}| = 2^16 = 65,536 ')print(' For finite groups, every subset is measurable ∈ F.')print(' σ-algebra structure becomes nontrivial only for U(D). ')
Verifying σ-algebra axioms (S1)-(S3) for F = 2^{P_N}
=======================================================
N = 1:
Ω = P_N with |Ω| = 4^1 = 4
F = 2^Ω (power set) with |F| = 2^4 = 16
Every subset of Ω is measurable (belongs to F).
(S1) Ω ∈ F: True
(S2) A^c ∈ F (|A|=3, |A^c|=1): True
(S3) A₁ ∪ A₂ ∪ A₃ ∈ F (|∪| = 4): True
N = 2:
Ω = P_N with |Ω| = 4^2 = 16
F = 2^Ω (power set) with |F| = 2^16 = 65,536
Every subset of Ω is measurable (belongs to F).
(S1) Ω ∈ F: True
(S2) A^c ∈ F (|A|=3, |A^c|=13): True
(S3) A₁ ∪ A₂ ∪ A₃ ∈ F (|∪| = 5): True
Summary:
N=1: |2^{P_1}| = 2^4 = 16
N=2: |2^{P_2}| = 2^16 = 65,536
For finite groups, every subset is measurable ∈ F.
σ-algebra structure becomes nontrivial only for U(D).
Takeaway
Survival probability and entanglement entropy are compositions of continuous maps on \(U(D)\), so both are Borel-measurable and their Haar averages are well-defined. Measurability only constrains integrands on a continuous group; on a finite group it holds for every function by construction.
7. Summary
This exercise established the measurability of the most common functions integrated against the Haar measure in this tutorial:
Bilinear in \(U\) entries → polynomial → continuous
\(\mathrm{OTOC}(U)\)
Part 4: scrambling dynamics
Polynomial in \(U\) entries → continuous
Every function we integrate against \(\mu_{\mathrm{Haar}}\) is a continuous function of the matrix entries of \(U\), and is therefore Borel-measurable: the preimage of any Borel set in \(\mathbb{R}\) belongs to \(\mathcal{B}(U(D))\). The Haar integral \(\int_{U(D)} f(U)\, d\mu\) is therefore well-defined for all such \(f\).
References
Mele, Introduction to Haar Measure Tools in Quantum Information: A Beginner’s Tutorial, Quantum (2024). doi
Collins and Śniady, Integration with respect to the Haar measure on unitary, orthogonal and symplectic group, Communications in Mathematical Physics (2006).
Płodzień, Information Scrambling, Quantum Chaos, and Haar-Random States, lecture notes (2025). arXiv:2511.14397
