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:1511.00635

Gacs Algorithmic Complexity on Hilbert Spaces and Some of its Applications

Samad Khabbazi Oskouei

Published Oct 21, 2015• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1511.00635

Related papers

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

Quantum Entropy and Complexity

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

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.

arXiv:1705.09449•Open Systems & Information Dynamics•Jun 1, 2017•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

Infinite-Dimensional Quantum Entropy: The Unified Entropy Case

Roman Gielerak, Joanna Wiśniewska, Marek Sawerwain

Infinite-dimensional systems play an important role in the continuous-variable quantum computation model, which can compete with a more standard approach based on qubit and quantum circuit computation models. But, in many cases, the value of entropy unfortunately cannot be easily computed for states originating from an infinite-dimensional Hilbert space. Therefore, in this article, the unified quantum entropy (which extends the standard von Neumann entropy) notion is extended to the case of infinite-dimensional systems by using the Fredholm determinant theory. Some of the known (in the finite-dimensional case) basic properties of the introduced unified entropies were extended to this case study. Certain numerical examples for computing the proposed finite- and infinite-dimensional entropies are outlined as well, which allowed us to calculate the entropy values for infinite Hilbert spaces.

Entropy•Dec 9, 2024•2 citations

Computational Notions of Quantum Min-Entropy

Yi-Hsiu Chen, Kai-Min Chung, Ching–Yi Lai +2 more

We initiate the study of computational entropy in the quantum setting. We investigate to what extent the classical notions of computational entropy generalize to the quantum setting, and whether quantum analogues of classical theorems hold. Our main results are as follows. (1) The classical Leakage Chain Rule for pseudoentropy can be extended to the case that the leakage information is quantum (while the source remains classical). Specifically, if the source has pseudoentropy at least $k$, then it has pseudoentropy at least $k-\ell$ conditioned on an $\ell$-qubit leakage. (2) As an application of the Leakage Chain Rule, we construct the first quantum leakage-resilient stream-cipher in the bounded-quantum-storage model, assuming the existence of a quantum-secure pseudorandom generator. (3) We show that the general form of the classical Dense Model Theorem (interpreted as the equivalence between two definitions of pseudo-relative-min-entropy) does not extend to quantum states. Along the way, we develop quantum analogues of some classical techniques (e.g. the Leakage Simulation Lemma, which is proven by a Non-uniform Min-Max Theorem or Boosting). On the other hand, we also identify some classical techniques (e.g. Gap Amplification) that do not work in the quantum setting. Moreover, we introduce a variety of notions that combine quantum information and quantum complexity, and this raises several directions for future work.

arXiv:1704.07309•Apr 24, 2017•4 citations
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.
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.
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.
Infinite-dimensional systems play an important role in the continuous-variable quantum computation model, which can compete with a more standard approach based on qubit and quantum circuit computation models. But, in many cases, the value of entropy unfortunately cannot be easily computed for states originating from an infinite-dimensional Hilbert space. Therefore, in this article, the unified quantum entropy (which extends the standard von Neumann entropy) notion is extended to the case of infinite-dimensional systems by using the Fredholm determinant theory. Some of the known (in the finite-dimensional case) basic properties of the introduced unified entropies were extended to this case study. Certain numerical examples for computing the proposed finite- and infinite-dimensional entropies are outlined as well, which allowed us to calculate the entropy values for infinite Hilbert spaces.
We initiate the study of computational entropy in the quantum setting. We investigate to what extent the classical notions of computational entropy generalize to the quantum setting, and whether quantum analogues of classical theorems hold. Our main results are as follows. (1) The classical Leakage Chain Rule for pseudoentropy can be extended to the case that the leakage information is quantum (while the source remains classical). Specifically, if the source has pseudoentropy at least kkk, then it has pseudoentropy at least k−ℓk-\ellk−ℓ conditioned on an ℓ\ellℓ-qubit leakage. (2) As an application of the Leakage Chain Rule, we construct the first quantum leakage-resilient stream-cipher in the bounded-quantum-storage model, assuming the existence of a quantum-secure pseudorandom generator. (3) We show that the general form of the classical Dense Model Theorem (interpreted as the equivalence between two definitions of pseudo-relative-min-entropy) does not extend to quantum states. Along the way, we develop quantum analogues of some classical techniques (e.g. the Leakage Simulation Lemma, which is proven by a Non-uniform Min-Max Theorem or Boosting). On the other hand, we also identify some classical techniques (e.g. Gap Amplification) that do not work in the quantum setting. Moreover, we introduce a variety of notions that combine quantum information and quantum complexity, and this raises several directions for future work.