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

Chapman & Hall/CRC eBooks

Counting complexity and quantum computation

Stephen Fenner

Published Feb 14, 2002• 1 citation
Publisher

Abstract

Abstract We survey several applications to quantum computing of computational complexity theory, especially the complexity of problems related to counting. We show how the connection of quantum computation to counting is very close. We define counting complexity classes, relativization of both classical computation and quantum circuits, and present a number of results from disparate sources, recast into a single consistent formalism. We assume prior knowledge of the mathematical formalism of quantum mechanics, but we present the concepts of computational complexity in an introductory manner.

DOI
10.1201/9781420035377-9

Related papers

Computational Complexity Analysis of Quantum Algorithms using Category Theory

Jincheng Zhang

Traditional methods for analyzing the computational complexity of algorithms, predominantly rooted in classical computer models, struggle to accurately characterize the potential advantages offered by quantum computation. This work proposes a novel approach utilizing category theory to provide a more fundamental and abstract framework for assessing the complexity of quantum algorithms. Instead of focusing on the specifics of quantum hardware, we examine the underlying categorical structures that define the computational processes inherent in these algorithms. This allows us to identify and analyze complexity properties that are independent of the physical implementation. We define key concepts like quantum states as objects and quantum gates as morphisms, establishing a formal connection between quantum computation and category theory. This framework facilitates a more rigorous and generalized understanding of quantum complexity, potentially revealing new insights and providing a basis for comparing different quantum algorithms. The core claim is that traditional complexity analysis is inadequate, and the mechanism is the application of category theory for a more abstract and generalized framework.

•Sep 7, 2026•0 citations

Quantum Computation

Helmut Bez, Tony Croft

Quantum Computation presents the mathematics of quantum computation. The purpose is to introduce the topic of quantum computing to students in computer science, physics and mathematics who have no prior knowledge of this field. The book is written in two parts. The primary mathematical topics required for an initial understanding of quantum computation are dealt with in Part I: sets, functions, complex numbers and other relevant mathematical structures from linear and abstract algebra. Topics are illustrated with examples focussing on the quantum computational aspects which will follow in more detail in Part II. Part II discusses quantum information, quantum measurement and quantum algorithms. These topics provide foundations upon which more advanced topics may be approached with confidence. Features A more accessible approach than most competitor texts, which move into advanced, research-level topics too quickly for today's students. Part I is comprehensive in providing all necessary mathematical underpinning, particularly for those who need more opportunity to develop their mathematical competence. More confident students may move directly to Part II and dip back into Part I as a reference. Ideal for use as an introductory text for courses in quantum computing. Fully worked examples illustrate the application of mathematical techniques. Exercises throughout develop concepts and enhance understanding. End-of-chapter exercises offer more practice in developing a secure foundation.

Chapman & Hall/CRC eBooks•Jan 6, 2023•0 citations

Applying computational complexity to the emergence of classicality

Arkady Bolotin

Can the computational complexity theory of computer science and mathematics say something new about unresolved problems in quantum physics? Particularly, can the P versus NP question in the computational complexity theory be a factor in the elucidation of the emergency of classicality in quantum mechanics? The paper compares two different ways of deriving classicality from the quantum formalism resulted from two differing hypotheses regarding the P versus NP question -- the approach of the quantum decoherence theory implying that P = NP and the computational complexity approach which assumes that P is not equal to NP.

arXiv:1309.1801•Sep 7, 2013•1 citation

One Complexity Theorist's View of Quantum Computing

Lance Fortnow

The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how useful these machines will be. The tools of computational complexity theory should come to bear on these important questions. Quantum computing often scares away many potential researchers from computer science because of the apparent background need in quantum mechanics and the alien looking notation used in papers on the topic. This paper will give an overview of quantum computation from the point of view of a complexity theorist. We will see that one can think of BQP as yet another complexity class and study its power without focusing on the physical aspects behind it.

arXiv:quant-ph/0003035•Mar 9, 2000•0 citations

Revisiting a limit on efficient quantum computation

Tarsem S. Purewal

In this paper, we offer an exposition of a theorem originally due to Adleman, Demarrais and Huang that shows that the quantum complexity class BQP (Bounded-error Quantum Polynomial time) is contained in the classical counting class PP (Probabilistic Polynomial time). Our proof follows the one given by Fortnow and Rogers that relates quantum computing to counting complexity classes by way of GapP functions. The contribution of this paper is an exposition of an important result that assumes a minimal background in computational complexity theory and no knowledge of quantum mechanics.

ACM Southeast Regional Conference (ACMSE)•Mar 10, 2006•1 citation

QUANTUM COMPUTATION

Dorit Aharonov

In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.

arXiv:quant-ph/9812037•WORLD SCIENTIFIC eBooks•Mar 1, 1999•103 citations
Abstract We survey several applications to quantum computing of computational complexity theory, especially the complexity of problems related to counting. We show how the connection of quantum computation to counting is very close. We define counting complexity classes, relativization of both classical computation and quantum circuits, and present a number of results from disparate sources, recast into a single consistent formalism. We assume prior knowledge of the mathematical formalism of quantum mechanics, but we present the concepts of computational complexity in an introductory manner.
Traditional methods for analyzing the computational complexity of algorithms, predominantly rooted in classical computer models, struggle to accurately characterize the potential advantages offered by quantum computation. This work proposes a novel approach utilizing category theory to provide a more fundamental and abstract framework for assessing the complexity of quantum algorithms. Instead of focusing on the specifics of quantum hardware, we examine the underlying categorical structures that define the computational processes inherent in these algorithms. This allows us to identify and analyze complexity properties that are independent of the physical implementation. We define key concepts like quantum states as objects and quantum gates as morphisms, establishing a formal connection between quantum computation and category theory. This framework facilitates a more rigorous and generalized understanding of quantum complexity, potentially revealing new insights and providing a basis for comparing different quantum algorithms. The core claim is that traditional complexity analysis is inadequate, and the mechanism is the application of category theory for a more abstract and generalized framework.
Quantum Computation presents the mathematics of quantum computation. The purpose is to introduce the topic of quantum computing to students in computer science, physics and mathematics who have no prior knowledge of this field. The book is written in two parts. The primary mathematical topics required for an initial understanding of quantum computation are dealt with in Part I: sets, functions, complex numbers and other relevant mathematical structures from linear and abstract algebra. Topics are illustrated with examples focussing on the quantum computational aspects which will follow in more detail in Part II. Part II discusses quantum information, quantum measurement and quantum algorithms. These topics provide foundations upon which more advanced topics may be approached with confidence. Features A more accessible approach than most competitor texts, which move into advanced, research-level topics too quickly for today's students. Part I is comprehensive in providing all necessary mathematical underpinning, particularly for those who need more opportunity to develop their mathematical competence. More confident students may move directly to Part II and dip back into Part I as a reference. Ideal for use as an introductory text for courses in quantum computing. Fully worked examples illustrate the application of mathematical techniques. Exercises throughout develop concepts and enhance understanding. End-of-chapter exercises offer more practice in developing a secure foundation.
Can the computational complexity theory of computer science and mathematics say something new about unresolved problems in quantum physics? Particularly, can the P versus NP question in the computational complexity theory be a factor in the elucidation of the emergency of classicality in quantum mechanics? The paper compares two different ways of deriving classicality from the quantum formalism resulted from two differing hypotheses regarding the P versus NP question -- the approach of the quantum decoherence theory implying that P = NP and the computational complexity approach which assumes that P is not equal to NP.
The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how useful these machines will be. The tools of computational complexity theory should come to bear on these important questions. Quantum computing often scares away many potential researchers from computer science because of the apparent background need in quantum mechanics and the alien looking notation used in papers on the topic. This paper will give an overview of quantum computation from the point of view of a complexity theorist. We will see that one can think of BQP as yet another complexity class and study its power without focusing on the physical aspects behind it.
In this paper, we offer an exposition of a theorem originally due to Adleman, Demarrais and Huang that shows that the quantum complexity class BQP (Bounded-error Quantum Polynomial time) is contained in the classical counting class PP (Probabilistic Polynomial time). Our proof follows the one given by Fortnow and Rogers that relates quantum computing to counting complexity classes by way of GapP functions. The contribution of this paper is an exposition of an important result that assumes a minimal background in computational complexity theory and no knowledge of quantum mechanics.
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.