Algorithmic Randomness and Kolmogorov Complexity for Qubits
share
Nies and Scholz defined quantum Martin-Löf randomness (q-MLR) for states (infinite qubitstrings). We define a notion of quantum Solovay randomness and show it to be equivalent to q-MLR using purely linear algebraic methods. Quantum Schnorr randomness is then introduced. A quantum analogue of the law of large numbers is shown to hold for quantum Schnorr random states. We introduce quantum-K, (QK) a measure of the descriptive complexity of density matrices using classical prefix-free Turing machines and show that the initial segments of weak Solovay random and quantum Schnorr random states are incompressible in the sense of QK. Several connections between Solovay randomness and K carry over to those between weak Solovay randomness and QK. We then define QK_C, using computable measure machines and connect it to quantum Schnorr randomness. We then explore a notion of `measuring' a state. We formalize how `measurement' of a state induces a probability measure on the space of infinite bitstrings. A state is `measurement random' (mR) if the measure induced by it, under any computable basis, assigns probability one to the set of Martin-Löf randoms. I.e., measuring a mR state produces a Martin-Löf random bitstring almost surely. While quantum-Martin-Löf random states are mR, the converse fails: there is a mR state, ρ which is not quantum-Martin-Löf random. In fact, something stronger is true. While ρ is computable and can be easily constructed, measuring it in any computable basis yields an arithmetically random sequence with probability one. So, classical randomness can be generated from a computable state which is not quantum random. We conclude by studying the asymptotic von Neumann entropy of computable states.
READ FULL TEXT