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

International Journal of Quantum Information

COMPLEXITY MEASURE: A QUANTUM INFORMATION APPROACH

Yuri Campbell, José Roberto Castilho Piqueira

Published Jun 1, 2012• 7 citations
Publisher

Abstract

In the past decades, all of the efforts at quantifying systems complexity with a general tool has usually relied on using Shannon's classical information framework to address the disorder of the system through the Boltzmann–Gibbs–Shannon entropy, or one of its extensions. However, in recent years, there were some attempts to tackle the quantification of algorithmic complexities in quantum systems based on the Kolmogorov algorithmic complexity, obtaining some discrepant results against the classical approach. Therefore, an approach to the complexity measure is proposed here, using the quantum information formalism, taking advantage of the generality of the classical-based complexities, and being capable of expressing these systems' complexity on other framework than its algorithmic counterparts. To do so, the Shiner–Davison–Landsberg (SDL) complexity framework is considered jointly with linear entropy for the density operators representing the analyzed systems formalism along with the tangle for the entanglement measure. The proposed measure is then applied in a family of maximally entangled mixed state.

DOI
10.1142/s0219749912500475

Related papers

Extending SDL and LMC complexity measures to quantum states

José Roberto Castilho Piqueira, Yuri Campbell

An extension of SDL (Shiner, Davison, Landsberg) and LMC (López-Ruiz, Mancini, Calbet) complexity measures is proposed for the quantum information context, considering that Von Neumann entropy is a natural disorder quantifier for quantum states. As a first example of application, the simple qubit was studied, presenting results similar to that obtained by applying SDL and LMC measures to a classical probability distribution. Then, for the Werner state, a mixture of Bell states, SDL and LMC measures were calculated, depending on the mixing factor γ , providing some conjectures concerning quantum systems.

Physica A Statistical Mechanics and its Applications•Jun 21, 2013•3 citations

Quantum State Complexity Measure

Yuri Campbell, José Roberto Castilho Piqueira

The complexity measures role has become much clearer in recent years as they help to better understand complex systems dynamical behavior. Even though the large number of measures proposed to tackle this issue for classical systems, for quantum systems only Kolmogorov’s algorithm complexity extensions have been proposed. Hence, the present approach makes use of a new and mathematically well-established complexity measure for classical systems and extends it to assess quantum states complexity as well. Then the proposed extension is applied to a mixed state constructed with a W-state together with controlled white noise, showing a convex behavior of quantum state complexity. Thus, this reinforces the differences from previous known quantum complexities.

•Oct 27, 2011•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

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•50 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•27 citations

Quantum-Enhanced Kolmogorov Complexity Theory

Jincheng Zhang

This paper investigates the potential impact of quantum mechanics on Kolmogorov complexity, a fundamental concept in information theory. The core claim is that quantum phenomena, specifically entanglement and superposition, introduce limitations to the compression achievable through Kolmogorov complexity that are absent in the classical framework. We demonstrate through theoretical analysis that certain datasets exhibit compression ratios exceeding those attainable by classical methods, leveraging the unique properties of quantum states. This extends Kolmogorov complexity by incorporating quantum principles, offering a novel perspective on the nature of information and its quantification. The theoretical framework presented here highlights potential discrepancies between classical and quantum notions of information and sets the stage for future research exploring the implications of quantum mechanics for fundamental information theory. We present a novel approach to defining Kolmogorov complexity within a quantum context, focusing on the measurement problem and its effect on the ability to uniquely determine a string. This work doesn't present experimental results; it is a purely theoretical exploration.

•Sep 3, 2026•0 citations
In the past decades, all of the efforts at quantifying systems complexity with a general tool has usually relied on using Shannon's classical information framework to address the disorder of the system through the Boltzmann–Gibbs–Shannon entropy, or one of its extensions. However, in recent years, there were some attempts to tackle the quantification of algorithmic complexities in quantum systems based on the Kolmogorov algorithmic complexity, obtaining some discrepant results against the classical approach. Therefore, an approach to the complexity measure is proposed here, using the quantum information formalism, taking advantage of the generality of the classical-based complexities, and being capable of expressing these systems' complexity on other framework than its algorithmic counterparts. To do so, the Shiner–Davison–Landsberg (SDL) complexity framework is considered jointly with linear entropy for the density operators representing the analyzed systems formalism along with the tangle for the entanglement measure. The proposed measure is then applied in a family of maximally entangled mixed state.
An extension of SDL (Shiner, Davison, Landsberg) and LMC (López-Ruiz, Mancini, Calbet) complexity measures is proposed for the quantum information context, considering that Von Neumann entropy is a natural disorder quantifier for quantum states. As a first example of application, the simple qubit was studied, presenting results similar to that obtained by applying SDL and LMC measures to a classical probability distribution. Then, for the Werner state, a mixture of Bell states, SDL and LMC measures were calculated, depending on the mixing factor γ , providing some conjectures concerning quantum systems.
The complexity measures role has become much clearer in recent years as they help to better understand complex systems dynamical behavior. Even though the large number of measures proposed to tackle this issue for classical systems, for quantum systems only Kolmogorov’s algorithm complexity extensions have been proposed. Hence, the present approach makes use of a new and mathematically well-established complexity measure for classical systems and extends it to assess quantum states complexity as well. Then the proposed extension is applied to a mixed state constructed with a W-state together with controlled white noise, showing a convex behavior of quantum state complexity. Thus, this reinforces the differences from previous known quantum complexities.
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. ---
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 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.
This paper investigates the potential impact of quantum mechanics on Kolmogorov complexity, a fundamental concept in information theory. The core claim is that quantum phenomena, specifically entanglement and superposition, introduce limitations to the compression achievable through Kolmogorov complexity that are absent in the classical framework. We demonstrate through theoretical analysis that certain datasets exhibit compression ratios exceeding those attainable by classical methods, leveraging the unique properties of quantum states. This extends Kolmogorov complexity by incorporating quantum principles, offering a novel perspective on the nature of information and its quantification. The theoretical framework presented here highlights potential discrepancies between classical and quantum notions of information and sets the stage for future research exploring the implications of quantum mechanics for fundamental information theory. We present a novel approach to defining Kolmogorov complexity within a quantum context, focusing on the measurement problem and its effect on the ability to uniquely determine a string. This work doesn't present experimental results; it is a purely theoretical exploration.