Quantum algorithmic randomness

Abstract

Quantum Martin-Lof randomness (q-MLR) for infinite qubit sequences was introduced by Nies and Scholz. We define a notion of quantum Solovay randomness which is equivalent to q-MLR. The proof of this goes through a purely linear algebraic result about approximating density matrices by subspaces. We then show that random states form a convex set. Martin-Lof absolute continuity is shown to be a special case of q-MLR. Quantum Schnorr randomness is introduced. Quantum analogues of the law of large numbers and the Shannon-McMillan-Breiman theorem are shown to hold for quantum Schnorr random states.