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
QKC, 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.
Nies and Scholz introduced the notion of a state to describe an infinite sequence of qubits and defined quantum-Martin-Lof randomness for states, analogously to the well known concept of Martin-L\"of randomness for elements of Cantor space (the space of infinite sequences of bits). We formalize how 'measurement' of a state in a basis induces a probability measure on Cantor space. 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\"of randoms. Equivalently, a state is mR if and only if measuring it in any computable basis yields a Martin-L\"of random with probability one. While quantum-Martin-L\"of random states are mR, the converse fails: there is a mR state, x which is not quantum-Martin-L\"of random. In fact, something stronger is true. While x is computable and can be easily constructed, measuring it in any computable basis yields an arithmetically random sequence with probability one. I.e., classical arithmetic randomness can be generated from a computable, non-quantum random sequence of qubits.
Abstract Nies and Scholz formalized the notion of an infinite qubitstring and referred to it as a ‘state’. They defined ‘quantum Martin-Löf randomness’ for states. We give a notion of measurement of a state in a computable basis and introduce ‘quantum measurement randomness’, a randomness notion for states. A state is quantum measurement random if measuring it in any computable basis yields a Martin-Löf random bitstring with probability one. Our main result is that quantum Martin-Löf randomness strictly implies quantum measurement randomness. This uses the construction of a quantum measurement random state which is not quantum Martin-Löf random. We prove two general results on which this construction relies: The first concerns Martin-Löf randomness relative to computable measures and extends a result of V. Vovk. The second is a combinatorial result about Kronecker products.
Abstract Quantum mechanics (QM) predicts probabilities on the fundamental level which are, via Born probability law, connected to the formal randomness of infinite sequences of QM outcomes. Recently it has been shown that QM is algorithmic 1-random in the sense of Martin-Löf. We extend this result and demonstrate that QM is algorithmic ω-random and generic precisely as described by the ’miniaturisation’ of the Solovay forcing to arithmetic. This is extended further to the result that QM becomes Zermelo-Fraenkel Solovay random on infinite dimensional Hilbert spaces. Moreover it is more likely that there exists a standard transitive model of ZFC M where QM is expressed in reality than in the universe V of sets. Then every generic quantum measurement adds the infinite sequence, i.e. random real r ∈ 2ω , to M and the model undergoes random forcing extensions, M[r]. The entire process of forcing becomes the structural ingredient of QM and parallels similar constructions applied to spacetime in the quantum limit. This shows the structural resemblance of both in the limit. We discuss several questions regarding measurability and eventual practical applications of the extended Solovay randomness of QM. The method applied is the formalization based on models of ZFC, however, this is particularly well-suited technique to recognising randomness questions of QM. When one works in a constant model of ZFC or in axiomatic ZFC itself the issues considered here become mostly hidden.
Abstract Quantum mechanics (QM) predicts probabilities on the fundamental level which are, via Born probability law, connected to the formal randomness of infinite sequences of QM outcomes. Recently it has been shown that QM is algorithmic 1-random in the sense of Martin-Löf. We extend this result and demonstrate that QM is algorithmic ω-random and generic precisely as described by the ’miniaturisation’ of the Solovay forcing to arithmetic. This is extended further to the result that QM becomes Zermelo-Fraenkel Solovay random on infinite dimensional Hilbert spaces. Moreover it is more likely that there exists a standard transitive model of ZFC M where QM is expressed in reality than in the universe V of sets. Then every generic quantum measurement adds the infinite sequence, i.e. random real r ∈ 2ω, to M and the model undergoes random forcing extensions, M[r]. The entire process of forcing becomes the structural ingredient of QM and parallels similar constructions applied to spacetime in the quantum limit. This shows the structural resemblance of both in the limit. We discuss several questions regarding measurability and eventual practical applications of the extended Solovay randomness of QM. The method applied is the formalization based on models of ZFC, however, this is particularly well-suited technique to recognising randomness questions of QM. When one works in a constant model of ZFC or in axiomatic ZFC itself the issues considered here become mostly hidden.