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

arXiv:quant-ph/9907035 · IEEE Conference on Computational Complexity (CCC)

Three approaches to the quantitative definition of information in an individual pure quantum state

Paul M. B. Vitanyi

Published Nov 7, 2002• 24 citations
arXivHTMLPDF

Abstract

In analogy of classical Kolmogorov complexity we develop a theory of the algorithmic information in bits contained in any one of continuously many pure quantum states: quantum Kolmogorov complexity. Classical Kolmogorov complexity coincides with the new quantum Kolmogorov complexity restricted to the classical domain. Quantum Kolmogorov complexity is upper bounded and can be effectively approximated from above. With high probability a quantum object is incompressible. There are two alternative approaches possible: to define the complexity as the length of the shortest qubit program that effectively describes the object, and to use classical descriptions with computable real parameters.

DOI
10.1109/ccc.2000.856757

Related papers

Quantum Kolmogorov complexity based on classical descriptions

Paul M. B. Vitanyi

We develop a theory of the algorithmic information in bits contained in an individual pure quantum state. This extends classical Kolmogorov complexity to the quantum domain retaining classical descriptions. Quantum Kolmogorov complexity coincides with the classical Kolmogorov complexity on the classical domain. Quantum Kolmogorov complexity is upper-bounded and can be effectively approximated from above under certain conditions. With high probability, a quantum object is incompressible. Upper and lower bounds of the quantum complexity of multiple copies of individual pure quantum states are derived and may shed some light on the no-cloning properties of quantum states. In the quantum situation complexity is not subadditive. We discuss some relations with "no-cloning" and "approximate cloning" properties.

arXiv:quant-ph/0102108•IEEE Transactions on Information Theory•Jan 1, 2001•75 citations

Quantum Kolmogorov complexity

A. Berthiaume, Wim van Dam, Sophie Laplante

In this paper we give a definition for quantum Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a string is the length of the shortest program that can produce this string as its output. It is a measure of the amount of innate randomness (or information) contained in the string. We define the quantum Kolmogorov complexity of a qubit string as the length of the shortest quantum input to a universal quantum Turing machine that produces the initial qubit string with high fidelity. The definition of P. Vitanyi (2000) measures the amount of classical information, whereas we consider the amount of quantum information in a qubit string. We argue that our definition is natural and is an accurate representation of the amount of quantum information contained in a quantum state.

IEEE Conference on Computational Complexity (CCC)•Nov 7, 2002•17 citations

ALGORITHMIC COMPLEXITY OF QUANTUM STATES

Caterina E. Mora, Hans J. Briegel

We give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory, the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of "how difficult" it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of known states. Furthermore, we establish a connection between the entanglement of a quantum state and its algorithmic complexity.

arXiv:quant-ph/0412172•International Journal of Quantum Information•Aug 1, 2006•24 citations

QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS

Caterina E. Mora, Hans J. Briegel, Barbara Kraus

Kolmogorov complexity is a measure of the information contained in a binary string. We investigate here the notion of quantum Kolmogorov complexity, a measure of the information required to describe a quantum state. We show that for any definition of quantum Kolmogorov complexity measuring the number of classical bits required to describe a pure quantum state, there exists a pure n-qubit state which requires exponentially many bits of description. This is shown by relating the classical communication complexity to the quantum Kolmogorov complexity. Furthermore, we give some examples of how quantum Kolmogorov complexity can be applied to prove results in different fields, such as quantum computation and thermodynamics, and we generalize it to the case of mixed quantum states.

arXiv:quant-ph/0610109•International Journal of Quantum Information•Oct 1, 2007•43 citations

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•68 citations

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•5 citations
In analogy of classical Kolmogorov complexity we develop a theory of the algorithmic information in bits contained in any one of continuously many pure quantum states: quantum Kolmogorov complexity. Classical Kolmogorov complexity coincides with the new quantum Kolmogorov complexity restricted to the classical domain. Quantum Kolmogorov complexity is upper bounded and can be effectively approximated from above. With high probability a quantum object is incompressible. There are two alternative approaches possible: to define the complexity as the length of the shortest qubit program that effectively describes the object, and to use classical descriptions with computable real parameters.
We develop a theory of the algorithmic information in bits contained in an individual pure quantum state. This extends classical Kolmogorov complexity to the quantum domain retaining classical descriptions. Quantum Kolmogorov complexity coincides with the classical Kolmogorov complexity on the classical domain. Quantum Kolmogorov complexity is upper-bounded and can be effectively approximated from above under certain conditions. With high probability, a quantum object is incompressible. Upper and lower bounds of the quantum complexity of multiple copies of individual pure quantum states are derived and may shed some light on the no-cloning properties of quantum states. In the quantum situation complexity is not subadditive. We discuss some relations with "no-cloning" and "approximate cloning" properties.
In this paper we give a definition for quantum Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a string is the length of the shortest program that can produce this string as its output. It is a measure of the amount of innate randomness (or information) contained in the string. We define the quantum Kolmogorov complexity of a qubit string as the length of the shortest quantum input to a universal quantum Turing machine that produces the initial qubit string with high fidelity. The definition of P. Vitanyi (2000) measures the amount of classical information, whereas we consider the amount of quantum information in a qubit string. We argue that our definition is natural and is an accurate representation of the amount of quantum information contained in a quantum state.
We give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory, the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of "how difficult" it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of known states. Furthermore, we establish a connection between the entanglement of a quantum state and its algorithmic complexity.
Kolmogorov complexity is a measure of the information contained in a binary string. We investigate here the notion of quantum Kolmogorov complexity, a measure of the information required to describe a quantum state. We show that for any definition of quantum Kolmogorov complexity measuring the number of classical bits required to describe a pure quantum state, there exists a pure n-qubit state which requires exponentially many bits of description. This is shown by relating the classical communication complexity to the quantum Kolmogorov complexity. Furthermore, we give some examples of how quantum Kolmogorov complexity can be applied to prove results in different fields, such as quantum computation and thermodynamics, and we generalize it to the case of mixed quantum states.
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.
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.