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.
Abstract How fast a state of a system converges to a stationary state is one of the fundamental questions in science. Some Markov chains and random walks on finite groups are known to exhibit the non-asymptotic convergence to a stationary distribution, called the cutoff phenomenon. Here, we examine how quickly a random quantum circuit could transform a quantum state to a Haar-measure random quantum state. We find that random quantum states, as stationary states of random walks on a unitary group, are invariant under the quantum Fourier transform (QFT). Thus the entropic uncertainty of random quantum states has balanced Shannon entropies for the computational basis and the QFT basis. By calculating the Shannon entropy for random quantum states and the Wasserstein distances for the eigenvalues of random quantum circuits, we show that the cutoff phenomenon occurs for the random quantum circuit. It is also demonstrated that the Dyson-Brownian motion for the eigenvalues of a random unitary matrix as a continuous random walk exhibits the cutoff phenomenon. The results here imply that random quantum states could be generated with shallow random circuits.
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.