von Neumann entropy and quantum algorithmic randomness
Tejas Bhojraj · Theoretical Computer Science · 2025
A state ρ = ( ρ n ) n = 1 ∞ is a sequence such that ρ n is a density matrix on n qubits . It formalizes the notion of an infinite sequence of qubits. The von Neumann entropy H ( d ) of a density matrix d is the Shannon entropy of its eigenvalue distribution. We show: (1) If ρ is a computable quantum Schnorr random state then lim n [ H ( ρ n ) / n ] = 1 . (2) We define quantum s-tests for s ∈ [ 0 , 1 ] , show that lim inf n [ H ( ρ n ) / n ] ≥ { s : ρ is covered by a quantum s-test } for computable ρ and construct states where this inequality is an equality. (3) If ∃ c ∃ ∞ n H ( ρ n ) > n − c then ρ is strong quantum random. Strong quantum randomness is a randomness notion which implies quantum Schnorr randomness relativized to any oracle. (4) A computable state ( ρ n ) n = 1 ∞ is quantum Schnorr random iff the family of distributions of the ρ n 's is uniformly integrable. We show that the implications in (1) and (3) are strict.