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:quant-ph/0506013 · International Journal of Theoretical Physics

Information Complexity of Quantum Gates

Subhash C. Kak

Published Mar 21, 2006• 20 citations
arXivHTMLPDF
DOI
10.1007/s10773-006-9086-3

Related papers

Computational Complexity Analysis of Quantum Algorithms using Information Theory

Jincheng Zhang

This paper explores the application of information theory to analyze the computational complexity of quantum algorithms. Traditional approaches to complexity analysis often rely on circuit models and gate complexity, which can be insufficient for fully characterizing the resource requirements of quantum computation. We propose utilizing information-theoretic concepts, specifically quantum entropy and mutual information, to provide a more nuanced understanding of how quantum circuits process information. This approach allows us to quantify the information-theoretic limits of quantum algorithms, providing insights into the number of qubits and gates necessary for efficient execution. We examine several key aspects, including the role of entanglement, the impact of measurement, and the relationship between quantum entropy and algorithmic complexity. The goal is to establish a framework for assessing quantum algorithms based on their fundamental information-processing capabilities, moving beyond purely circuit-based evaluations. This work contributes to a deeper theoretical understanding of quantum computation and its potential limitations.

•Sep 2, 2026•0 citations

Quantum Information Theory, Entropy, and Computational Complexity

Advances in computational intelligence and robotics book series•Nov 5, 2026•0 citations

Pieces of Quantum Information and Quantum Logical Gates

María Luisa Dalla Chiara, Roberto Giuntini, Roberto Leporini +1 more

Trends in logic•Jan 1, 2018•0 citations

Information in Quantum Description and Gate Implementation

Krishnan, Gayathre

This note considers Kak's observer-reference model of quantum information, where it is shown that qubits carry information that is sqrt n / ln n times classical information, where n is the number of components in the measurement system, to analyze information processing in quantum gates. The obverse side of this exponential nature of quantum information is that the computational complexity of implementing unconditionally reliable quantum gates is also exponential.

arXiv:cs/0604085•Apr 21, 2006•0 citations

Short Proofs of Linear Growth of Quantum Circuit Complexity

Zhi Li

The complexity of a quantum gate, defined as the minimal number of elementary gates to build it, is an important concept in quantum information and computation. It is shown recently that the complexity of quantum gates built from random quantum circuits almost surely grows linearly with the number of building blocks. In this article, we provide two short proofs of this fact. We also discuss a discrete version of quantum circuit complexity growth.

arXiv:2205.05668•May 11, 2022•16 citations

Quantum Computational Complexity

John Watrous

Springer eBooks•Nov 2, 2011•55 citations
This paper explores the application of information theory to analyze the computational complexity of quantum algorithms. Traditional approaches to complexity analysis often rely on circuit models and gate complexity, which can be insufficient for fully characterizing the resource requirements of quantum computation. We propose utilizing information-theoretic concepts, specifically quantum entropy and mutual information, to provide a more nuanced understanding of how quantum circuits process information. This approach allows us to quantify the information-theoretic limits of quantum algorithms, providing insights into the number of qubits and gates necessary for efficient execution. We examine several key aspects, including the role of entanglement, the impact of measurement, and the relationship between quantum entropy and algorithmic complexity. The goal is to establish a framework for assessing quantum algorithms based on their fundamental information-processing capabilities, moving beyond purely circuit-based evaluations. This work contributes to a deeper theoretical understanding of quantum computation and its potential limitations.