An Introduction to Quantum Complexity Theory

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.

28 pages, LaTeX, 11 figures within the text, to appear in "Collected Papers on Quantum Computation and Quantum Information Theory", edited by C. Macchiavello, G.M. Palma, and A. Zeilinger (World Scientific)

References in corpus (2)

• On Universal and Fault-Tolerant Quantum Computing
• Computational Complexity of Uniform Quantum Circuit Families and Quantum Turing Machines

Cited by in corpus (29)

• The Physical Implementation of Quantum Computation
• Information and Computation: Classical and Quantum Aspects
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Quantum Computational Complexity -- From Quantum Information to Black Holes and Back
• Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines
• Decoherence-Free Subspaces for Multiple-Qubit Errors: (II) Universal, Fault-Tolerant Quantum Computation
• The Hidden Subgroup Problem - Review and Open Problems
• Circuit Complexity and 2D Bosonisation
• Succinct quantum proofs for properties of finite groups
• Semantics and simulation of communication in quantum programming
• Quantum Computing, NP-complete Problems and Chaotic Dynamics
• Communication Complexity Lower Bounds by Polynomials
• Classical programmability is enough for quantum circuits universality in approximate sense
• Characterization of quantum computable decision problems by state discrimination
• A Note on Oracle Separations for BQP
• Quantum Algorithm for SAT Problem and Quantum Mutual Entropy
• Programmable Quantum Networks with Pure States
• Taming Quantum Time Complexity
• On the solution of trivalent decision problems by quantum state identification
• Contextual Observables and Quantum Information
• Quantum Processors and Controllers
• ALEPH-QP: Universal hybrid quantum processors
• Comparative Computational Strength of Quantum Oracles
• A stochastic limit approach to the SAT problem
• Von Neumann Quantum Processors
• Universal quantum processors with arbitrary radix n
• NMR Quantum Information Processing and Entanglement
• Physics and metaphysics looks at computation
• The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems