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

Quantum Algorithmic Information Theory.

Samuel Epstein

Published Feb 7, 2021• 0 citations
OpenAlex

Abstract

This paper extends quantum information theory into the algorithmic sphere, using randomness and information conservation inequalities. We show for an overwhelming majority of pure states, the self classical algorithmic information induced by a measurement will be negligible. Purification of two states increases information. Decoherence causes quantum states to lose information with all other quantum states.

Related papers

On the Algorithmic Information Between Probabilities

Epstein, Samuel

We extend algorithmic conservation inequalities to probability measures. The amount of self information of a probability measure cannot increase when submitted to randomized processing. This includes (potentially non-computable) measures over finite sequences, infinite sequences, and $T_0$, second countable topologies. One example is the convolution of signals over real numbers with probability kernels. Thus the smoothing of any signal due We show that given a quantum measurement, for an overwhelming majority of pure states, no meaningful information is produced.

arXiv:2303.07296•Mar 13, 2023•0 citations

An Introduction to Algorithmic Information Theory and Quantum Mechanics

Samuel Epstein

This article presents a survey of published and unpublished material of the intersection of Algorithmic Information Theory and Quantum Mechanics. It is, to the author's knowledge, the first of its type. Three different notions of the algorithmic content of quantum states are reviewed. Notions of algorithmic quantum typicality and mutual information are introduced. The relationship between algorithmic information and quantum measurements is explored. One of the surprising results is that an overwhelming majority of quantum (pure and mixed) states, when undertaking decoherence, will result in a classical probability with no algorithmic information. Thus most quantum states decohere into white noise. A quantum analouge of Martin Löf random sequence is reviewed. Algorithmic Information Theory presents new complications for the Many Worlds Theory, as it conflicts with the Independence Postulate. When algorithmically complicated processes are ruled out, measurements are required to produce distributions over quantum states that have cloneable information.

•May 11, 2023•0 citations

Algorithmic No-Cloning Theorem

Samuel Epstein

We introduce notions of algorithmic mutual information and deficiency of randomness of quantum states. These definitions enjoy conservation inequalities over unitary transformations and partial traces. We show that a large majority of pure states have minute self-algorithmic information. We provide an algorithmic variant to the no-cloning theorem, by showing that only a small minority of quantum pure states can clone a nonnegligible amount of algorithmic information. We also provide a chain rule inequality for quantum algorithmic entropy. We show that deficiency of randomness does not increase under POVM measurements.

arXiv:1808.04213•IEEE Transactions on Information Theory•Aug 16, 2019•7 citations

On the Algorithmic Content of Quantum Measurements

Samuel Epstein

We show that given a quantum measurement, for an overwhelming majority of pure states, no meaningful information is produced. This is independent of the number of outcomes of the quantum measurement. Due to conservation inequalities, such random noise cannot be processed into coherent data.

arXiv:2102.03905•Electronic colloquium on computational complexity•Feb 7, 2021•1 citation

Conservation of information and the foundations of quantum mechanics

Giulio Chiribella, Carlo Maria Scandolo

We review a recent approach to the foundations of quantum mechanics inspired by quantum information theory [1, 2]. The approach is based on a general framework, which allows one to address a large class of physical theories which share basic information-theoretic features. We first illustrate two very primitive features, expressed by the axioms of causality and purity-preservation, which are satisfied by both classical and quantum theory. We then discuss the axiom of purification, which expresses a strong version of the Conservation of Information and captures the core of a vast number of protocols in quantum information. Purification is a highly non-classical feature and leads directly to the emergence of entanglement at the purely conceptual level, without any reference to the superposition principle. Supplemented by a few additional requirements, satisfied by classical and quantum theory, it provides a complete axiomatic characterization of quantum theory for finite dimensional systems.

arXiv:1411.2723•EPJ Web of Conferences•Jan 1, 2015•5 citations

Conservation of information and the foundations of quantum mechanics

Giulio Chiribella, Carlo Maria Scandolo

We review a recent approach to the foundations of quantum mechanics inspired by quantum information theory [1, 2]. The approach is based on a general framework, which allows one to address a large class of physical theories which share basic information-theoretic features. We first illustrate two very primitive features, expressed by the axioms of causality and purity-preservation, which are satisfied by both classical and quantum theory. We then discuss the axiom of purification, which expresses a strong version of the Conservation of Information and captures the core of a vast number of protocols in quantum information. Purification is a highly non-classical feature and leads directly to the emergence of entanglement at the purely conceptual level, without any reference to the superposition principle. Supplemented by a few additional requirements, satisfied by classical and quantum theory, it provides a complete axiomatic characterization of quantum theory for finite dimensional systems.

EPJ Web of Conferences•Jan 1, 2015•18 citations
This paper extends quantum information theory into the algorithmic sphere, using randomness and information conservation inequalities. We show for an overwhelming majority of pure states, the self classical algorithmic information induced by a measurement will be negligible. Purification of two states increases information. Decoherence causes quantum states to lose information with all other quantum states.
We extend algorithmic conservation inequalities to probability measures. The amount of self information of a probability measure cannot increase when submitted to randomized processing. This includes (potentially non-computable) measures over finite sequences, infinite sequences, and T0T_0T0​, second countable topologies. One example is the convolution of signals over real numbers with probability kernels. Thus the smoothing of any signal due We show that given a quantum measurement, for an overwhelming majority of pure states, no meaningful information is produced.
This article presents a survey of published and unpublished material of the intersection of Algorithmic Information Theory and Quantum Mechanics. It is, to the author's knowledge, the first of its type. Three different notions of the algorithmic content of quantum states are reviewed. Notions of algorithmic quantum typicality and mutual information are introduced. The relationship between algorithmic information and quantum measurements is explored. One of the surprising results is that an overwhelming majority of quantum (pure and mixed) states, when undertaking decoherence, will result in a classical probability with no algorithmic information. Thus most quantum states decohere into white noise. A quantum analouge of Martin Löf random sequence is reviewed. Algorithmic Information Theory presents new complications for the Many Worlds Theory, as it conflicts with the Independence Postulate. When algorithmically complicated processes are ruled out, measurements are required to produce distributions over quantum states that have cloneable information.
We introduce notions of algorithmic mutual information and deficiency of randomness of quantum states. These definitions enjoy conservation inequalities over unitary transformations and partial traces. We show that a large majority of pure states have minute self-algorithmic information. We provide an algorithmic variant to the no-cloning theorem, by showing that only a small minority of quantum pure states can clone a nonnegligible amount of algorithmic information. We also provide a chain rule inequality for quantum algorithmic entropy. We show that deficiency of randomness does not increase under POVM measurements.
We review a recent approach to the foundations of quantum mechanics inspired by quantum information theory [1, 2]. The approach is based on a general framework, which allows one to address a large class of physical theories which share basic information-theoretic features. We first illustrate two very primitive features, expressed by the axioms of causality and purity-preservation, which are satisfied by both classical and quantum theory. We then discuss the axiom of purification, which expresses a strong version of the Conservation of Information and captures the core of a vast number of protocols in quantum information. Purification is a highly non-classical feature and leads directly to the emergence of entanglement at the purely conceptual level, without any reference to the superposition principle. Supplemented by a few additional requirements, satisfied by classical and quantum theory, it provides a complete axiomatic characterization of quantum theory for finite dimensional systems.
We review a recent approach to the foundations of quantum mechanics inspired by quantum information theory [1, 2]. The approach is based on a general framework, which allows one to address a large class of physical theories which share basic information-theoretic features. We first illustrate two very primitive features, expressed by the axioms of causality and purity-preservation, which are satisfied by both classical and quantum theory. We then discuss the axiom of purification, which expresses a strong version of the Conservation of Information and captures the core of a vast number of protocols in quantum information. Purification is a highly non-classical feature and leads directly to the emergence of entanglement at the purely conceptual level, without any reference to the superposition principle. Supplemented by a few additional requirements, satisfied by classical and quantum theory, it provides a complete axiomatic characterization of quantum theory for finite dimensional systems.