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

Proceedings of symposia in applied mathematics

A survey of quantum complexity theory

Umesh V. Vazirani

Published Jan 1, 2002• 44 citations
Publisher
DOI
10.1090/psapm/058/1922899

Related papers

A survey on the complexity of learning quantum states

Anurag Anshu, Srinivasan Arunachalam

arXiv:2305.20069•Nature Reviews Physics•Dec 11, 2023•134 citations

Current Trends in Quantum Complexity Theory

Tetsuro Nihino

•Jan 20, 2006•0 citations

A Survey: SWAP Test and Its Applications to Quantum Complexity Theory

Harumichi Nishimura

Abstract The SWAP test is a fundamental tool commonly used in the theory of quantum information and computation while its understanding and applications have been investigated in the literature. This survey focuses on the SWAP test in the studies of quantum complexity theory. We review the basics of the SWAP test, some tests related to it, and their properties, and report their applications in quantum complexity theory.

Springer eBooks•Jan 1, 2025•8 citations

Quantum Complexity Theory and Quantum Algorithm

R. Hayakawa, Tomoyuki Morimae

電子情報通信学会誌•Nov 1, 2021•0 citations

Quantum Proofs for Classical Theorems

Andrew Drucker, Ronald de Wolf

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in diverse classical (non-quantum) areas, such as coding theory, communication complexity, and polynomial approximations. In this paper we survey these results and the quantum toolbox they use.

arXiv:0910.3376•Theory of Computing•Jan 1, 2011•49 citations

The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)

Sagnik Chatterjee

This paper surveys various results in the field of Quantum Learning theory, specifically focusing on learning quantum-encoded classical concepts in the Probably Approximately Correct (PAC) framework. The cornerstone of this work is the emphasis on query, sample, and time complexity separations between classical and quantum learning that emerge under learning with query access to different labeling oracles. This paper aims to consolidate all known results in the area under the above umbrella and underscore the limits of our understanding by leaving the reader with 23 open problems.

quant-pharXiv:2602.01054•Feb 3, 2026•1 citation
This paper surveys various results in the field of Quantum Learning theory, specifically focusing on learning quantum-encoded classical concepts in the Probably Approximately Correct (PAC) framework. The cornerstone of this work is the emphasis on query, sample, and time complexity separations between classical and quantum learning that emerge under learning with query access to different labeling oracles. This paper aims to consolidate all known results in the area under the above umbrella and underscore the limits of our understanding by leaving the reader with 23 open problems.