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:1705.09449 · Open Systems & Information Dynamics

Quantum Entropy and Complexity

Fabio Benatti, Samad Khabbazi Oskouei, A. Shafiei Deh Abad

Published Jun 1, 2017• 1 citation
arXivHTMLPDF

Abstract

We study the relations between the recently proposed machine-independent quantum complexity of P. Gacs [1] and the entropy of classical and quantum systems. On one hand, by restricting Gacs complexity to ergodic classical dynamical systems, we retrieve the equality between the Kolmogorov complexity rate and the Shannon entropy rate derived by A. A. Brudno [2]. On the other hand, using the quantum Shannon-McMillan theorem [3], we show that such an equality holds densely in the case of ergodic quantum spin chains.

DOI
10.1142/s1230161217500056

Related papers

Quantum Dynamical Entropies and Gács Algorithmic Entropy

Fabio Benatti

Several quantum dynamical entropies have been proposed that extend the classical Kolmogorov–Sinai (dynamical) entropy. The same scenario appears in relation to the extension of algorithmic complexity theory to the quantum realm. A theorem of Brudno establishes that the complexity per unit time step along typical trajectories of a classical ergodic system equals the KS-entropy. In the following, we establish a similar relation between the Connes–Narnhofer–Thirring quantum dynamical entropy for the shift on quantum spin chains and the Gács algorithmic entropy. We further provide, for the same system, a weaker linkage between the latter algorithmic complexity and a different quantum dynamical entropy proposed by Alicki and Fannes.

Entropy•Jul 12, 2012•3 citations

Gacs Algorithmic Complexity on Hilbert Spaces and Some of its Applications

Samad Khabbazi Oskouei

We extend the notion of Gacs quantum algorithmic entropy, originally formulated for finitely many qubits, to infinite dimensional quantum spin chains and investigate the relation of this extension with two quantum dynamical entropies that have been proposed in recent years. Further, we prove an extension of Brudno's theorem in quantum spin chains with shift dynamics.

arXiv:1511.00635•Oct 21, 2015•1 citation

Entropy and Algorithmic Complexity in Quantum Information Theory: a Quantum Brudno's Theorem

Fabio Benatti, Tyll Krueger, Markus P. Müller +2 more

In classical information theory, entropy rate and algorithmic complexity per symbol are related by a theorem of Brudno. In this paper, we prove a quantum version of this theorem, connecting the von Neumann entropy rate and two notions of quantum algorithmic complexity, both based on the shortest qubit descriptions of qubit strings that, run by a universal quantum Turing machine, reproduce them as outputs.

•Jun 10, 2005•1 citation

Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces

Fabio Benatti, Samad Khabbazi Oskouei, Ahmad Shafiei Deh Abad

We extend the notion of Gacs quantum algorithmic entropy, originally formulated for finitely many qubits, to infinite dimensional quantum spin chains and investigate the relation of this extension with two quantum dynamical entropies that have been proposed in recent years.

Journal of Mathematical Physics•Aug 1, 2014•5 citations

Quantum complexity and the virial theorem

Ning Bao, Junyu Liu

Abstract It is conjectured that in the geometric formulation of quantum computing, one can study quantum complexity through classical entropy of statistical ensembles established non-relativistically in the group manifold of unitary operators. The kinetic and positional decompositions of statistical entropy are conjectured to correspond to the Kolmogorov complexity and computational complexity, respectively, of corresponding quantum circuits. In this paper, we claim that by applying the virial theorem to the group manifold, one can derive a generic relation between Kolmogorov complexity and computational complexity in the thermal equilibrium.

arXiv:1804.03242•Journal of High Energy Physics•Aug 1, 2018•9 citations

Quantum Algorithmic Complexities and Entropy

Fabio Benatti

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.

Open Systems & Information Dynamics•Mar 1, 2009•30 citations
We study the relations between the recently proposed machine-independent quantum complexity of P. Gacs [1] and the entropy of classical and quantum systems. On one hand, by restricting Gacs complexity to ergodic classical dynamical systems, we retrieve the equality between the Kolmogorov complexity rate and the Shannon entropy rate derived by A. A. Brudno [2]. On the other hand, using the quantum Shannon-McMillan theorem [3], we show that such an equality holds densely in the case of ergodic quantum spin chains.
Several quantum dynamical entropies have been proposed that extend the classical Kolmogorov–Sinai (dynamical) entropy. The same scenario appears in relation to the extension of algorithmic complexity theory to the quantum realm. A theorem of Brudno establishes that the complexity per unit time step along typical trajectories of a classical ergodic system equals the KS-entropy. In the following, we establish a similar relation between the Connes–Narnhofer–Thirring quantum dynamical entropy for the shift on quantum spin chains and the Gács algorithmic entropy. We further provide, for the same system, a weaker linkage between the latter algorithmic complexity and a different quantum dynamical entropy proposed by Alicki and Fannes.
Abstract It is conjectured that in the geometric formulation of quantum computing, one can study quantum complexity through classical entropy of statistical ensembles established non-relativistically in the group manifold of unitary operators. The kinetic and positional decompositions of statistical entropy are conjectured to correspond to the Kolmogorov complexity and computational complexity, respectively, of corresponding quantum circuits. In this paper, we claim that by applying the virial theorem to the group manifold, one can derive a generic relation between Kolmogorov complexity and computational complexity in the thermal equilibrium.