Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Foundations of Physics

Random quantum states

William K. Wootters

Published Nov 1, 1990• 106 citations
Publisher
DOI
10.1007/bf01883491

Related papers

Random quantum states

Guillaume Aubrun, Stanisław Szarek

Mathematical surveys and monographs•Aug 30, 2017•0 citations

Algorithmic Randomness and Kolmogorov Complexity for Qubits

Tejas Bhojraj

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.

arXiv:2106.14280•Jun 27, 2021•2 citations

Quantum Random Systems

Josef Honerkamp

Graduate texts in physics•Jan 1, 2012•0 citations

Cutoff phenomenon and entropic uncertainty for random quantum circuits

Sangchul Oh, Sabre Kais

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.

arXiv:2305.12078•Electronic Structure•Aug 22, 2023•3 citations

QUANTUM MEASUREMENTS AND ALGORITHMIC RANDOMNESS

Tejas Bhojraj

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.

Journal of Symbolic Logic•Feb 23, 2026•0 citations

Pseudorandom Quantum States

Zhengfeng Ji, Yi-Kai Liu, Fang Song

Lecture notes in computer science•Jan 1, 2018•182 citations
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, (QKQKQK) 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 QKQKQK. Several connections between Solovay randomness and KKK carry over to those between weak Solovay randomness and QKQKQK. We then define QKCQK_CQKC​, 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' (mRmRmR) 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 mRmRmR state produces a Martin-Löf random bitstring almost surely. While quantum-Martin-Löf random states are mRmRmR, the converse fails: there is a mRmRmR 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.