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

Journal of Uncertain Systems

Expanding Algorithmic Randomness to the Algebraic Approach to Quantum Physics: Kolmogorov Complexity and Quantum Logics

Владик Крейнович

Published Jan 1, 2010• 0 citations
OpenAlex

Abstract

Physicists usually assume that events with a very small probability cannot occur. Kolmogorov complexity formalizes this idea for non-quantum events. We show how this formalization can be extended to quantum events as well.

Related papers

Quantum algorithmic entropy

Péter Gács

We extend algorithmic information theory to quantum mechanics, taking a universal semicomputable density matrix (`universal probability') as a starting point, and define complexity (an operator) as its negative logarithm. A number of properties of Kolmogorov complexity extend naturally to the new domain. Approximately, a quantum state is simple if it is within a small distance from a low-dimensional subspace of low Kolmogorov complexity. The von Neumann entropy of a computable density matrix is within an additive constant from the average complexity. Some of the theory of randomness translates to the new domain. We explore the relations of the new quantity to the quantum Kolmogorov complexity defined by Vitányi (we show that the latter is sometimes as large as 2 n − 2 log n ) and the qubit complexity defined by Berthiaume, Dam and Laplante. The `cloning' properties of our complexity measure are similar to those of qubit complexity.

arXiv:quant-ph/0011046•Journal of Physics A Mathematical and General•Aug 24, 2001•71 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

Vistas of Algebraic Probability: Quantum Computation and Information

Antonio Falcó, Hermann G. Matthies

Kolmogorov's foundation of probability takes measure spaces, $σ$-algebras, and probability measures as basic objects. It is, however, widely recognized that this classical framework is inadequate for random phenomena involving quantum effects, and more generally for \emph{quantum-like} situations. A broader formulation is provided by an algebraic viewpoint: one starts from an algebra of random variables equipped with a distinguished linear functional -- the \emph{state} -- interpreted as expectation. In this sense, the approach can also be viewed as a modern reading of ideas already implicit in early probability (e.g., the Bernoullis), while its contemporary form has been developed and used extensively in quantum physics. The algebraic framework accommodates both classical and quantum-like behaviours, yet it remains underused in classical probability and uncertainty quantification, where it can nevertheless open new perspectives and clarify structural features. Although the language carries a physics flavor, the subject is purely probabilistic. The key distinction between classical and quantum-like behaviour is \emph{commutativity}: its failure produces the characteristic effects of quantum-like situations. The rise of quantum computing is a prominent setting in which such behaviour may become relevant even for practitioners in computational science. Here we focus on the purely algebraic core of the approach. By restricting attention to finite-dimensional algebras, we avoid many analytical subtleties while retaining the main ideas, their classical limit, and their applicability to quantum-like models and quantum computation.

quant-pharXiv:2602.04351•Feb 5, 2026•1 citation

Quantum algorithmic entropy

Péter Gács

Extends algorithmic information theory to quantum mechanics, taking a universal semi-computable density matrix ("universal probability") as a starting point, and defines complexity (an operator) as its negative logarithm. A number of properties of Kolmogorov complexity extend naturally to the new domain. Approximately, a quantum state is simple if it is within a small distance from a low-dimensional subspace of low Kolmogorov complexity. The von-Neumann entropy of a computable density matrix is within an additive constant from the average complexity. Some of the theory of randomness translates to the new domain. We explore the relations of the new quantity to the quantum Kolmogorov complexity defined by P.M.B. Vita/spl acute/nyi (1999) (we show that the latter is sometimes as large as 2n-2 log n) and the qubit complexity defined by A. Berthiaume et al. (2000). The "cloning" properties of our complexity measure are similar to those of qubit complexity.

IEEE Conference on Computational Complexity (CCC)•Nov 13, 2002•4 citations

Beyond Kolmogorov: Towards a Non-Commutative Measure Theory of Quantum Probability Spaces

Revista, Zen, MATH, 10

This paper explores the limitations of Kolmogorov's measure-theoretic foundation of probability in the context of quantum mechanics and proposes an extension towards a non-commutative framework. We delve into the mathematical structures underlying quantum probability spaces, focusing on operator algebras and their associated states. We analyze the challenges in defining joint probabilities for non-commuting observables and present an overview of alternative approaches based on operator algebras, quantum logic, and non-commutative integration. Furthermore, we investigate the applications of non-commutative measure theory in quantum information theory, quantum field theory, and the foundations of quantum mechanics, highlighting the potential for a more comprehensive understanding of probabilistic phenomena in quantum systems.

•Dec 5, 2025•0 citations

Unification of classical and quantum probabilistic formalisms

Andrei Yu. Khrennikov

We demonstrate that the contextual approach to Kolmogorov probability model gives the possibility to unify this conventional model of probability with the quantum (Hilbert space) probability model. In fact, the Kolmogorov model can exhibit all distinguishing features of the quantum probability model. In particular, by using the contextual (interference) formula of total probability one can construct complex amplitudes of Kolmogorov probabilities. There exists a natural Hilbert space structure on the space of those complex amplitudes. Classical (Kolmogorovian) random variables are represented by in general noncommutative operators in the Hilbert space of complex amplitudes. The existence of such a contextual representation of the Kolmogorovian model looks very surprising in the view of the orthodox quantum tradition. Supported by EU-network “Quantum Probability and Applications”.

•Feb 27, 2003•1 citation
We extend algorithmic information theory to quantum mechanics, taking a universal semicomputable density matrix (`universal probability') as a starting point, and define complexity (an operator) as its negative logarithm. A number of properties of Kolmogorov complexity extend naturally to the new domain. Approximately, a quantum state is simple if it is within a small distance from a low-dimensional subspace of low Kolmogorov complexity. The von Neumann entropy of a computable density matrix is within an additive constant from the average complexity. Some of the theory of randomness translates to the new domain. We explore the relations of the new quantity to the quantum Kolmogorov complexity defined by Vitányi (we show that the latter is sometimes as large as 2 n − 2 log n ) and the qubit complexity defined by Berthiaume, Dam and Laplante. The `cloning' properties of our complexity measure are similar to those of qubit complexity.
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.
Kolmogorov's foundation of probability takes measure spaces, σσσ-algebras, and probability measures as basic objects. It is, however, widely recognized that this classical framework is inadequate for random phenomena involving quantum effects, and more generally for \emph{quantum-like} situations. A broader formulation is provided by an algebraic viewpoint: one starts from an algebra of random variables equipped with a distinguished linear functional -- the \emph{state} -- interpreted as expectation. In this sense, the approach can also be viewed as a modern reading of ideas already implicit in early probability (e.g., the Bernoullis), while its contemporary form has been developed and used extensively in quantum physics. The algebraic framework accommodates both classical and quantum-like behaviours, yet it remains underused in classical probability and uncertainty quantification, where it can nevertheless open new perspectives and clarify structural features. Although the language carries a physics flavor, the subject is purely probabilistic. The key distinction between classical and quantum-like behaviour is \emph{commutativity}: its failure produces the characteristic effects of quantum-like situations. The rise of quantum computing is a prominent setting in which such behaviour may become relevant even for practitioners in computational science. Here we focus on the purely algebraic core of the approach. By restricting attention to finite-dimensional algebras, we avoid many analytical subtleties while retaining the main ideas, their classical limit, and their applicability to quantum-like models and quantum computation.
Extends algorithmic information theory to quantum mechanics, taking a universal semi-computable density matrix ("universal probability") as a starting point, and defines complexity (an operator) as its negative logarithm. A number of properties of Kolmogorov complexity extend naturally to the new domain. Approximately, a quantum state is simple if it is within a small distance from a low-dimensional subspace of low Kolmogorov complexity. The von-Neumann entropy of a computable density matrix is within an additive constant from the average complexity. Some of the theory of randomness translates to the new domain. We explore the relations of the new quantity to the quantum Kolmogorov complexity defined by P.M.B. Vita/spl acute/nyi (1999) (we show that the latter is sometimes as large as 2n-2 log n) and the qubit complexity defined by A. Berthiaume et al. (2000). The "cloning" properties of our complexity measure are similar to those of qubit complexity.
This paper explores the limitations of Kolmogorov's measure-theoretic foundation of probability in the context of quantum mechanics and proposes an extension towards a non-commutative framework. We delve into the mathematical structures underlying quantum probability spaces, focusing on operator algebras and their associated states. We analyze the challenges in defining joint probabilities for non-commuting observables and present an overview of alternative approaches based on operator algebras, quantum logic, and non-commutative integration. Furthermore, we investigate the applications of non-commutative measure theory in quantum information theory, quantum field theory, and the foundations of quantum mechanics, highlighting the potential for a more comprehensive understanding of probabilistic phenomena in quantum systems.
We demonstrate that the contextual approach to Kolmogorov probability model gives the possibility to unify this conventional model of probability with the quantum (Hilbert space) probability model. In fact, the Kolmogorov model can exhibit all distinguishing features of the quantum probability model. In particular, by using the contextual (interference) formula of total probability one can construct complex amplitudes of Kolmogorov probabilities. There exists a natural Hilbert space structure on the space of those complex amplitudes. Classical (Kolmogorovian) random variables are represented by in general noncommutative operators in the Hilbert space of complex amplitudes. The existence of such a contextual representation of the Kolmogorovian model looks very surprising in the view of the orthodox quantum tradition. Supported by EU-network “Quantum Probability and Applications”.