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

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•0 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

Quantum Information Entropy: A Generalized Definition

Jincheng Zhang

This paper introduces a generalized definition of quantum information entropy, aiming to provide a more comprehensive framework for quantifying information in complex quantum systems. The core of this work lies in extending the conventional concept of entropy, traditionally applied to classical information, to the realm of quantum mechanics. We explore various types of quantum entropy, including von Neumann entropy, relative entropy, and a newly proposed generalized entropy, denoted as *Eg*. The definition of *Eg* is based on a novel approach that considers the entanglement structure and correlations within quantum states. We establish relationships between these different entropy measures, demonstrating their interconnectedness within the broader context of quantum information theory. The paper further outlines a mathematical formalism for calculating *Eg*, providing a tool for analyzing and characterizing quantum information. Our generalized entropy provides a more flexible and potentially more accurate measure of quantum information, particularly in scenarios involving complex quantum correlations and multi-partite quantum systems. ---

•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•76 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.
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.
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.
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. ---
This paper introduces a generalized definition of quantum information entropy, aiming to provide a more comprehensive framework for quantifying information in complex quantum systems. The core of this work lies in extending the conventional concept of entropy, traditionally applied to classical information, to the realm of quantum mechanics. We explore various types of quantum entropy, including von Neumann entropy, relative entropy, and a newly proposed generalized entropy, denoted as *Eg*. The definition of *Eg* is based on a novel approach that considers the entanglement structure and correlations within quantum states. We establish relationships between these different entropy measures, demonstrating their interconnectedness within the broader context of quantum information theory. The paper further outlines a mathematical formalism for calculating *Eg*, providing a tool for analyzing and characterizing quantum information. Our generalized entropy provides a more flexible and potentially more accurate measure of quantum information, particularly in scenarios involving complex quantum correlations and multi-partite quantum systems. ---