Von Neumann Entropy and Quantum Algorithmic Randomness

Abstract

A state $\rho =({\rho }_n{)}_{n=1}^{\infty }$ is a sequence such that ${\rho }_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 $\rho$ is a computable quantum Schnorr random state then ${\lim }_n[H({\rho }_n)/n]=1$. (2) We define quantum s-tests for $s\in [0,1]$, show that $\liminf_n [H(\rho_n)/n]\geq \{ s: \rho$iscoveredbyaquantums-test$\}$ for computable $\rho$ and construct states where this inequality is an equality. (3) If $\exists c{\exists }^{\infty }nH({\rho }_n)>n-c$ then $\rho$ is strong quantum random. Strong quantum randomness is a randomness notion which implies quantum Schnorr randomness relativized to any oracle. (4) A computable state $({\rho }_n{)}_{n=1}^{\infty }$ is quantum Schnorr random iff the family of distributions of the ${\rho }_n$'s is uniformly integrable. We show that the implications in (1) and (3) are strict.