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

Open Systems & Information Dynamics

Quantum Algorithmic Complexities and Entropy

Fabio Benatti

Published Mar 1, 2009• 30 citations
Publisher

Abstract

We review the basics of classical algorithmic complexity theory and two of its quantum extensions that have been prompted by the foreseeable existence of quantum computing devices. In particular, we will examine the relations between these extensions and the von Neumann entropy rate of generic quantum information sources of ergodic type.
DOI
10.1142/s1230161209000025

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

A Brief Review of Classical and Quantum Relationships Between Entropy and Information

Donovan X Chapman

In this review paper, different definitions of classical entropies and a quantum version of entropy, the von Neumann Entropy, are introduced. Correlations between these classical and quantum models of entropy and the relevance of each in information theory are shown. Computing and quantum teleportation are discussed with the goal of providing a pedagogical introduction to some of the applications of information theory.

•Nov 10, 2026•0 citations

Quantum Chaos and Quantum Information: Interactions and Implications

Arul Lakshminarayan, Karol Życzkowski

The notion of Shannon entropy is crucial for the theory of classical information. In quantum information theory, an analogous key role is played by the von Neumann entropy: quantum information processing is closely related to entropy dynamics. This reveals a direct link with the theory of quantum chaotic systems, which can be characterized by a positive entropy production. Furthermore, noise, which inevitably affects any quantum system, can be modeled by a random quantum operation or by coupling to an environment in a generic chaotic state. In this contribution, we emphasize the universality of quantum chaotic dynamics and discuss its implications for quantum information processing.

quant-pharXiv:2604.12267•Apr 15, 2026•2 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•4 citations

Quantum Computation Complexity Theory Based on Quantum Information Entropy

Jincheng Zhang

This paper explores the application of quantum information entropy to the theory of computational complexity. We posit that quantum information entropy can serve as a novel metric for quantifying the complexity of quantum algorithms and their associated resource requirements. The core argument is that traditional measures of computational complexity, such as circuit depth or quantum gate count, often fail to fully capture the inherent challenges posed by quantum systems. By leveraging entropy, we aim to provide a more nuanced and potentially more accurate assessment of the difficulty of quantum computations. This work introduces a framework for analyzing quantum algorithms through the lens of information entropy, exploring relationships between algorithmic complexity, entropy generation, and the resources needed to execute these algorithms. Specifically, we examine how entropy can be used to characterize the 'quantumness' of an algorithm and its impact on the overall computational cost. The ultimate goal is to develop a more robust and predictive model for quantum computation, leading to improved algorithm design and resource allocation. ---

•Aug 31, 2026•0 citations

An Introduction to Quantum Complexity Theory

Richard Cleve

We give a basic overview of computational complexity, query complexity, and communication complexity, with quantum information incorporated into each of these scenarios. The aim is to provide simple but clear definitions, and to highlight the interplay between the three scenarios and currently-known quantum algorithms.

arXiv:quant-ph/9906111•WORLD SCIENTIFIC eBooks•Jan 1, 2001•94 citations
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.
The notion of Shannon entropy is crucial for the theory of classical information. In quantum information theory, an analogous key role is played by the von Neumann entropy: quantum information processing is closely related to entropy dynamics. This reveals a direct link with the theory of quantum chaotic systems, which can be characterized by a positive entropy production. Furthermore, noise, which inevitably affects any quantum system, can be modeled by a random quantum operation or by coupling to an environment in a generic chaotic state. In this contribution, we emphasize the universality of quantum chaotic dynamics and discuss its implications for quantum information processing.
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 application of quantum information entropy to the theory of computational complexity. We posit that quantum information entropy can serve as a novel metric for quantifying the complexity of quantum algorithms and their associated resource requirements. The core argument is that traditional measures of computational complexity, such as circuit depth or quantum gate count, often fail to fully capture the inherent challenges posed by quantum systems. By leveraging entropy, we aim to provide a more nuanced and potentially more accurate assessment of the difficulty of quantum computations. This work introduces a framework for analyzing quantum algorithms through the lens of information entropy, exploring relationships between algorithmic complexity, entropy generation, and the resources needed to execute these algorithms. Specifically, we examine how entropy can be used to characterize the 'quantumness' of an algorithm and its impact on the overall computational cost. The ultimate goal is to develop a more robust and predictive model for quantum computation, leading to improved algorithm design and resource allocation. ---