Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes.

Two important quantum complexity classes are BQP and QMA.

A complexity class is a collection of computational problems that can be solved by a computational model under certain resource constraints. For instance, the complexity class P is defined as the set of problems solvable by a Turing machine in polynomial time. Similarly, quantum complexity classes may be defined using quantum models of computation, such as the quantum circuit model or the equivalent quantum Turing machine. One of the main aims of quantum complexity theory is to find out how these classes relate to classical complexity classes such as P, NP, BPP, and PSPACE.

One of the reasons quantum complexity theory is studied are the implications of quantum computing for the modern Church-Turing thesis. In short the modern Church-Turing thesis states that any computational model can be simulated in polynomial time with a probabilistic Turing machine. However, questions around the Church-Turing thesis arise in the context of quantum computing. It is unclear whether the Church-Turing thesis holds for the quantum computation model. There is much evidence that the thesis does not hold. It may not be possible for a probabilistic Turing machine to simulate quantum computation models in polynomial time.

Both quantum computational complexity of functions and classical computational complexity of functions are often expressed with asymptotic notation. Some common forms of asymptotic notion of functions are ${\displaystyle O(T(n))}$, ${\displaystyle \Omega (T(n))}$, and ${\displaystyle \Theta (T(n))}$. ${\displaystyle O(T(n))}$ expresses that something is bounded above by ${\displaystyle cT(n)}$ where ${\displaystyle c}$ is a constant such that ${\displaystyle c>0}$ and ${\displaystyle T(n)}$ is a function of ${\displaystyle n}$, ${\displaystyle \Omega (T(n))}$ expresses that something is bounded below by ${\displaystyle cT(n)}$ where ${\displaystyle c}$ is a constant such that ${\displaystyle c>0}$ and ${\displaystyle T(n)}$ is a function of ${\displaystyle n}$, and ${\displaystyle \Theta (T(n))}$ expresses both ${\displaystyle O(T(n))}$ and ${\displaystyle \Omega (T(n))}$. These notations also have their own names. ${\displaystyle O(T(n))}$ is called Big O notation, ${\displaystyle \Omega (T(n))}$ is called Big Omega notation, and ${\displaystyle \Theta (T(n))}$ is called Big Theta notation.

The important complexity classes P, BPP, BQP, PP, and PSPACE can be compared based on promise problems. A promise problem is a decision problem which has an input assumed to be selected from the set of all possible input strings. A promise problem is a pair ${\displaystyle A=(A_{\text{yes}},A_{\text{no}})}$, where ${\displaystyle A_{\text{yes}}}$ is the set of yes instances and ${\displaystyle A_{\text{no}}}$ is the set of no instances, and the intersection of these sets is empty: ${\displaystyle A_{\text{yes}}\cap A_{\text{no}}=\varnothing }$. All of the previous complexity classes contain promise problems.

The class of problems that can be efficiently solved by a quantum computer with bounded error is called BQP ("bounded error, quantum, polynomial time"). More formally, BQP is the class of problems that can be solved by a polynomial-time quantum Turing machine with error probability of at most 1/3.

As a class of probabilistic problems, BQP is the quantum counterpart to BPP ("bounded error, probabilistic, polynomial time"), the class of problems that can be efficiently solved by probabilistic Turing machines with bounded error. It is known that ${\displaystyle {\mathsf {BPP\subseteq BQP}}}$ and widely suspected, but not proven, that ${\displaystyle {\mathsf {BQP\nsubseteq BPP}}}$, which intuitively would mean that quantum computers are more powerful than classical computers in terms of time complexity. BQP is a subset of PP.