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.
Background
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 (deterministic) 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. Asymptotic computational complexities of both quantum algorithms and classical algorithms are often expressed with asymptotic notation. Some common forms of asymptotic notation of functions are O ( T ( n ) ) {\displaystyle O(T(n))} , Ω ( T ( n ) ) {\displaystyle \Omega (T(n))} , and Θ ( T ( n ) ) {\displaystyle \Theta (T(n))} . O ( T ( n ) ) {\displaystyle O(T(n))} expresses that something is bounded above by c T ( n ) {\displaystyle cT(n)} where c {\displaystyle c} is a constant such that c > 0 {\displaystyle c>0} and T ( n ) {\displaystyle T(n)} is a function of n {\displaystyle n} , Ω ( T ( n ) ) {\displaystyle \Omega (T(n))} expresses that something is bounded below by c T ( n ) {\displaystyle cT(n)} where c {\displaystyle c} is a constant such that c > 0 {\displaystyle c>0} and T ( n ) {\displaystyle T(n)} is a function of n {\displaystyle n} , and Θ ( T ( n ) ) {\displaystyle \Theta (T(n))} expresses both O ( T ( n ) ) {\displaystyle O(T(n))} and Ω ( T ( n ) ) {\displaystyle \Omega (T(n))} . These notations also have their own names. O ( T ( n ) ) {\displaystyle O(T(n))} is called big O notation, Ω ( T ( n ) ) {\displaystyle \Omega (T(n))} is called big Omega notation, and Θ ( T ( n ) ) {\displaystyle \Theta (T(n))} is called big Theta notation.
Overview of complexity classes The important complexity classes P, BPP, BQP, PP, and PSPACE can be compared based on promise problems. A promise problem is a decision problem that has an input assumed to be selected from the set of all possible input strings. A promise problem is a pair A = ( A yes , A no ) {\displaystyle A=(A_{\text{yes}},A_{\text{no}})} , where A yes {\displaystyle A_{\text{yes}}} is the set of yes instances and A no {\displaystyle A_{\text{no}}} is the set of no instances, and the intersection of these sets is empty: A yes ∩ A no = ∅ {\displaystyle A_{\text{yes}}\cap A_{\text{no}}=\varnothing } . All of the previous complexity classes contain promise problems.
BQP
… excerpt ends here. Continue reading the full article.
