An Introduction to Quantum Complexity Theory

2001/01/01 by Richard Cleve · 3 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Computability, Logic, AI Algorithms #Quantum Information and Cryptography

paper · doi:10.1142/9789810248185_0004

openalex publication_date 2001/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a basic overview of computational complexity, query complexity, and communication complexity, with quantum information incorporated into each of these scenarios. The aim is to provide simple but clear definitions, and to highlight the interplay between the three scenarios and currently-known quantum algorithms.

Citations

• Threshold Accuracy for Quantum Computation
• Lower Bounds for Quantum Search and Derandomization
• Strengths and Weaknesses of Quantum Computing
• Quantum Entanglement and Communication Complexity
• Elementary gates for quantum computation
• Fast quantum verification for the formulas of predicate calculus
• Quantum Algorithms Revisited
• On the Power of Quantum Computation
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Quantum computations: algorithms and error correction
• Quantum Lower Bounds by Polynomials
• Fault-tolerant quantum computation

Cited by

• Information and computation: Classical and quantum aspects
• Semantics and simulation of communication in quantum programming
• Quantum complexity theory [wikipedia]