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 (i.e., non-quantum) complexity classes.

Two important quantum complexity classes are BQP and QMA.

Background

See also: Computational complexity and Complexity class

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

Main article: BQP

BQP algorithm (1 run)

Answer produced Correct answer	Yes	No
Yes	≥ 2/3	≤ 1/3
No	≤ 1/3	≥ 2/3

The suspected relationship of BQP to other complexity classes.

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 BPP$\subseteq$BQP and widely suspected, but not proven, that 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.

The exact relationship of BQP to P, NP, and PSPACE is not known. However, it is known that P$\subseteq$BQP$\subseteq$PSPACE; 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 (integer factorization and the discrete logarithm problem are both in NP, for example). It is suspected that NP$\nsubseteq$BQP; 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 (if any NP-complete problem were in BQP, then it follows from NP-hardness that all problems in NP are in BQP).

The relationship of BQP to the essential classical complexity classes can be summarized as:

${\mathsf {P\subseteq BPP\subseteq BQP\subseteq PP\subseteq PSPACE}}$

It is also known that BQP is contained in the complexity class #P (or more precisely in the associated class of decision problems P^#P), which is a subset of PSPACE.

Quantum Query Complexity

One major advantage of using a quantum computational system instead of a classical one, is that a quantum computer may be able to give a polynomial time algorithm for some problem for which no classical polynomial time algorithm exists, but more importantly, a quantum computer may significantly decrease the calculation time for a problem that a classical computer can already solve efficiently. Essentially, a quantum computer may be able to both determine how long it will take to solve a problem, while a classical computer may be unable to do so, and can also greatly improve the computational efficiency associated with the solution to a particular problem. Quantum query complexity refers to how complex, or how many queries to the graph associated with the solution of a particular problem, are required to solve the problem. Before we delve further into query complexity, let us consider some background regarding graphing solutions to particular problems, and the queries associated with these solutions.

Query Models of Directed Graphs

One type of problem that quantum computing can make easier to solve are graph problems. If we are to consider the amount of queries to a graph that are required to solve a given problem, let us first consider the most common types of graphs, called directed graphs, that are associated with this type of computational modelling. In brief, directed graphs are graphs where all edges between vertices are unidirectional. Directed graphs are formally defined as the graph $G=(N,E)$, where N is the set of vertices, or nodes, and E is the set of edges.

Adjacency Matrix Model

When considering quantum computation of the solution to directed directed graph problems, there are two important query models to understand. First, there is the adjacency matrix model, where the graph of the solution is given by the adjacency matrix: $M\in \{0,1\}a^{n\mathrm {X} n}$, with $M_{ij}=1$, if and only if $(v_{i},v_{j})\in E$.

Adjacency Array Model

Next, there is the slightly more complicated adjacency array model built on the idea of adjacency lists, where every vertex, $u$, is associated with an array of neighboring vertices such that $f_{i}:[d_{i}^{+}]\rightarrow [n]$, for the out-degrees of vertices $d_{i}^{+},...,d_{n}^{+}$, where $n$ is the minimum value of the upper bound of this model, and $f_{i}(j)$ returns the "$j^{th}$" vertex adjacent to $i$. Additionally, the adjacency array model satisfies the simple graph condition, $\forall i\in [n],j,j^{'}\in [k],j\neq j^{'}:f_{i}(j)\neq f_{i}(j^{'})$, meaning that there is only one edge between any pair of vertices, and the number of edges is minimized throughout the entire model (see Spanning tree model for more background).

Quantum Query Complexity of Certain Types of Graph Problems

Both of the above models can be used to determine the query complexity of particular types of graphing problems, including the connectivity, strong connectivity (a directed graph version of the connectivity model), minimum spanning tree, and single source shortest path models of graphs. An important caveat to consider is that the quantum complexity of a particular type of graphing problem can change based on the query model (namely either matrix or array) used to determine the solution. The following table showing the quantum query complexities of these types of graphing problems illustrates this point well.

Quantum Query Complexity of Certain Types of Graph Problems

Problem	Matrix Model	Array Model
Minimum Spanning Tree	$\Theta (n^{3/2})$	$\Theta ({\sqrt {nm}})$
Connectivity	$\Theta (n^{3/2})$	$\Theta (n)$
Strong Connectivity	$\Theta (n^{3/2})$	$\Omega ({\sqrt {nm}})$, $O({\sqrt {nmlog(n)}})$
Single Source Shortest Path	$\Omega (n^{3/2})$, $O(n^{3/2}log^{2}n)$	$\Omega ({\sqrt {nm}})$, $O({\sqrt {nm}}log^{2}(n))$

Notice the discrepancy between the quantum query complexities associated with a particular type of problem, depending on which query model was used to determine the complexity. For example, when the matrix model is used, the quantum complexity of the connectivity model in Big O notation is $\Theta (n^{3/2})$, but when the array model is used, the complexity is $\Theta (n)$. Additionally, for brevity, we use the shorthand $m$ in certain cases, where $m=\Theta (n^{2})$. The important implication here is that the efficiency of the algorithm used to solve a graphing problem is dependent on the type of query model used to model the graph.

Other Types of Quantum Computational Queries

In the query complexity model, the input can also be given as an oracle (black box). 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.

Similar to the case of graphing problems, the quantum query complexity of a black-box problem 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.

Grover's Algorithm

An example depicting the power of quantum computing is Grover's algorithm for searching unstructured databases. The algorithm's quantum query complexity is ${\textstyle O{\left({\sqrt {N}}\right)}}$, a quadratic improvement over the best possible classical query complexity $O(N)$, which is a linear search. While Grover's algorithm is more optimized than the best possible classical algorithm, we know that Grover's algorithm is not one hundred percent optimal. Optimization of a query algorithm refers to how the algorithm compares to the most efficient theoretical algorithm that solves the same problem. An algorithm is said to be asymptotically optimized if at worst, it performs at a constant factor worse than the most efficient possible algorithm. Note that an algorithm is still considered to be optimized if it performs worse than the most efficient possible algorithm, as long as the algorithm doesn't get exponentially worse than the most efficient possible algorithm, as the number of inputs increases.

See also

• Quantum computing
• Quantum Turing machine
• Polynomial hierarchy (PH)

References

• Nielsen, Michael; Chuang, Isaac (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 978-0-521-63503-5. OCLC 174527496.
• Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. pp. 201–236. ISBN 978-0-521-42426-4.
• John Watrous (2008). "Quantum Computational Complexity". arXiv:0804.3401v1 [quant-ph].
• Watrous J. (2009) Quantum Computational Complexity. In: Meyers R. (eds) Encyclopedia of Complexity and Systems Science. Springer, New York, NY

External links

• MIT lectures by Scott Aaronson