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

Advances in computational intelligence and robotics book series

Quantum Information Theory, Entropy, and Computational Complexity

Published Nov 5, 2026• 0 citations
Publisher
DOI
10.4018/979-8-2600-0482-1

Related papers

Entropy and algorithmic complexity in quantum information theory

Fabio Benatti

Natural Computing•Dec 7, 2006•8 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

Fully Quantum Computational Entropies

Avidan, Noam, Thomas A. Hahn, Joseph M. Renes +1 more

Quantum information theory has provided the formal framework for describing how information is stored, transmitted, and transformed in physical quantum systems [6, 7, 9]. Its entropic formulations underpin our understanding of quantum computation, communication, and cryptography. Yet this theory traditionally treats all quantum operations as freely available, ignoring computational restrictions. In practice, however, any manipulation of quantum information must be performed by devices of bounded complexity and runtime. Capturing such realistic constraints requires extending quantum information theory to include computational efficiency as a fundamental component.This work takes a first step toward building a computational version of quantum information theory, one that treats efficiency as part of the theory itself. The goal is to understand how the behavior of quantum information changes when the parties involved can only perform computationally efficient operations. This approach bridges the abstract, ideal setting of quantum information theory with the practical limitations of real quantum devices, offering a means to study information processing under realistic resource constraints.At the center of this work are two new quantities: the quantum computational min-entropy and the quantum computational max-entropy. These entropies extend standard quantum entropies by explicitly limiting the computational power of the observer or adversary. The quantum computational min-entropy captures how unpredictable a quantum system A remains to an observer holding system B, when that observer is restricted to quantum circuits of bounded size. Formally, for a bipartite state rho AB, we define(c) H-s (min)(A|B)rho := - log d(A) max (epsilon s) B > A' F ((parallel to(A)circle times epsilon(s))(rho(AB)),|Phi (AA')> Quantum information theory; Theory of computation -> Quantum complexity theory

arXiv:2506.14068•Leibniz international proceedings in informatics•Jun 16, 2025•5 citations

Quantum Algorithms and Complexity: An Information Theory Perspective

Umesh V. Vazirani

•Oct 2, 2002•0 citations

Entropic Entrainment: A Speculative Framework for Entropy, Quantum Computation, and Complexity

Victoria Mellor, Mo Adda

I propose a speculative but mathematically grounded framework called entropic entrainment, which reconceptualizes entropy not as a passive scalar measure of disorder, but as an active constraint shaping quantum and classical computation. Building on tools from quantum information geometry and open quantum systems theory, I model entropy flow through computational trajectories and suggest that complexity may emerge from a form of "entropic inertia." I define an entropic action principle and introduce a computable proxy for entropic complexity. While this theory is exploratory, it opens novel questions about decoherence, the structure of computational hardness, and entropy's role in the emergence of time in computation.

•Jul 31, 2025•0 citations

Quantum Entropy and Information

Nilanjana Datta

Lecture notes in physics•Jan 1, 2010•3 citations
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. ---
Quantum information theory has provided the formal framework for describing how information is stored, transmitted, and transformed in physical quantum systems [6, 7, 9]. Its entropic formulations underpin our understanding of quantum computation, communication, and cryptography. Yet this theory traditionally treats all quantum operations as freely available, ignoring computational restrictions. In practice, however, any manipulation of quantum information must be performed by devices of bounded complexity and runtime. Capturing such realistic constraints requires extending quantum information theory to include computational efficiency as a fundamental component.This work takes a first step toward building a computational version of quantum information theory, one that treats efficiency as part of the theory itself. The goal is to understand how the behavior of quantum information changes when the parties involved can only perform computationally efficient operations. This approach bridges the abstract, ideal setting of quantum information theory with the practical limitations of real quantum devices, offering a means to study information processing under realistic resource constraints.At the center of this work are two new quantities: the quantum computational min-entropy and the quantum computational max-entropy. These entropies extend standard quantum entropies by explicitly limiting the computational power of the observer or adversary. The quantum computational min-entropy captures how unpredictable a quantum system A remains to an observer holding system B, when that observer is restricted to quantum circuits of bounded size. Formally, for a bipartite state rho AB, we define(c) H-s (min)(A|B)rho := - log d(A) max (epsilon s) B > A' F ((parallel to(A)circle times epsilon(s))(rho(AB)),|Phi (AA')> Quantum information theory; Theory of computation -> Quantum complexity theory
I propose a speculative but mathematically grounded framework called entropic entrainment, which reconceptualizes entropy not as a passive scalar measure of disorder, but as an active constraint shaping quantum and classical computation. Building on tools from quantum information geometry and open quantum systems theory, I model entropy flow through computational trajectories and suggest that complexity may emerge from a form of "entropic inertia." I define an entropic action principle and introduce a computable proxy for entropic complexity. While this theory is exploratory, it opens novel questions about decoherence, the structure of computational hardness, and entropy's role in the emergence of time in computation.