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

Elsevier eBooks

Quantum computational complexity

Daowen Qiu

Published Aug 29, 2025• 0 citations
Publisher
DOI
10.1016/b978-0-44-327704-7.00012-8

Related papers

Quantum Computational Complexity

John Watrous

Springer eBooks•Nov 2, 2011•55 citations

Counting complexity and quantum computation

Stephen Fenner

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.

Chapman & Hall/CRC eBooks•Feb 14, 2002•2 citations

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•2 citations

Computational Complexity and Quantum Computing

Marco O. Lanzagorta, Jeffrey K. Uhlmann

Synthesis lectures on quantum computing•Jan 1, 2008•0 citations

Computational Complexity

Suman Saha, Shailendra Shukla

This chapter delves into the fundamental concept of computational complexity as it relates to algorithmic performance in the Smart World. It begins by exploring the principles of computability and various computational models. A major focus is on different complexity classes, including a detailed examination of probabilistic complexity (such as the BPP class) and the emergent field of quantum complexity. The chapter specifically discusses the power and intrigue of the BQP class and its relationship with traditional complexity classes like P and NP, outlining future directions in both probabilistic and quantum computation.

Wiley eBooks•Mar 17, 2026•0 citations

Computational complexity and applications of quantum algorithm

Satoshi Iriyama, Makoto Ohya

Applied Mathematics and Computation•Jun 24, 2011•2 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.
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.
This chapter delves into the fundamental concept of computational complexity as it relates to algorithmic performance in the Smart World. It begins by exploring the principles of computability and various computational models. A major focus is on different complexity classes, including a detailed examination of probabilistic complexity (such as the BPP class) and the emergent field of quantum complexity. The chapter specifically discusses the power and intrigue of the BQP class and its relationship with traditional complexity classes like P and NP, outlining future directions in both probabilistic and quantum computation.