Quantum complexity theory


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 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 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.

BQP

≥ 2/3≤ 1/3
≤ 1/3≥ 2/3

The class of problems that can be efficiently solved by a quantum computer with bounded error is called BQP. 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, the class of problems that can be efficiently solved by probabilistic Turing machines with bounded error. It is known that BPPBQP and widely suspected, but not proven, that BQPBPP, which intuitively would mean that quantum computers are more powerful than classical computers in terms of time complexity. BQP is a subset of PP.
The exact relationship of BQP to P, NP, and PSPACE is not known. However, it is known that PBQPPSPACE; that is, the class of problems that can be efficiently solved by quantum computers includes all problems that can be efficiently solved by deterministic classical computers but does not include any problems that cannot be solved by classical computers with polynomial space resources. It is further suspected that BQP is a strict superset of P, meaning there are problems that are efficiently solvable by quantum computers that are not efficiently solvable by deterministic classical computers. For instance, integer factorization and the discrete logarithm problem are known to be in BQP and are suspected to be outside of P. On the relationship of BQP to NP, little is known beyond the fact that some NP problems are in BQP. It is suspected that NPBQP; that is, it is believed that there are efficiently checkable problems that are not efficiently solvable by a quantum computer. As a direct consequence of this belief, it is also suspected that BQP is disjoint from the class of NP-complete problems.
The relationship of BQP to the essential classical complexity classes can be summarized as:
It is also known that BQP is contained in the complexity class #P, which is a subset of PSPACE.

Quantum query complexity

In the query complexity model, the input is given as an oracle. The algorithm gets information about the input only by querying the oracle. The algorithm starts in some fixed quantum state and the state evolves as it queries the oracle.
Quantum query complexity is the smallest number of queries to the oracle that are required in order to calculate the function. This makes the quantum query complexity a lower bound on the overall time complexity of a function.
An example depicting the power of quantum computing is Grover's algorithm for searching unstructured databases. The algorithm's quantum query complexity is, a quadratic improvement over the best possible classical query complexity, which is a linear search.