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. 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 formula_1, formula_2, and formula_3. formula_1 expresses that something is bounded above  by formula_5 where formula_6 is a constant such that formula_7 and formula_8 is a function of formula_9, formula_2 expresses that something is bounded below by formula_5 where formula_6 is a constant such that formula_7 and formula_8 is a function of formula_9, and formula_3 expresses both formula_1 and formula_2. These notations also their own names. formula_1 is called Big O notation, formula_2 is called Big Omega notation, and formula_3 is called Big Theta notation. Overview of complexity classes. Some important complexity classes are P, BPP, BQP, PP, and P-Space. To define these we first define a promise problem. 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 formula_22. formula_23 is the set of yes instances, formula_24 is the set of no instances, and the intersection of these sets is such that formula_25. All of the previous complexity classes contain promise problems. BQP. 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 formula_26 and widely suspected, but not proven, that formula_27, 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 formula_28; 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 formula_29; 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: It is also known that BQP is contained in the complexity class (or more precisely in the associated class of decision problems ), which is a subset of PSPACE. Simulation of quantum circuits. There is no known way to efficiently simulate a quantum computational model with a classical computer. This means that a classical computer cannot simulate a quantum computational model in polynomial time. However, a quantum circuit of formula_31 qubits with formula_8 quantum gates can be simulated by a classical circuit with  formula_33 classical gates. This number of classical gates is obtained by determining how many bit operations are necessary to simulate the quantum circuit. In order to do this, first the amplitudes associated with the formula_31 qubits must be accounted for. Each of the states of the formula_31 qubits can be described by a two-dimensional complex vector, or a state vector. These state vectors can also be described a linear combination of its component vectors with coefficients called amplitudes. These amplitudes are complex numbers which are normalized to one, meaning the sum of the squares of the absolute values of  the amplitudes must be one. The entries of the state vector are these amplitudes. Which entry each of the amplitudes are correspond to the none-zero component of the component vector which they are the coefficients of in the linear combination description. As an equation this is described as formula_36 or formula_37 using Dirac notation. The state of the entire formula_31 qubit system can be described by a single state vector. This state vector describing the entire system is the tensor product of the state vectors describing the individual qubits in the system. The result of the tensor products of  the formula_31 qubits is a single state vector which has formula_40 dimensions and entries that are the amplitudes associated with each basis state or component vector. Therefore, formula_40amplitudes must be accounted for with a formula_40 dimensional complex vector which is the state vector for the formula_31 qubit system. In order to obtain an upper bound for the number of gates required to simulate a quantum circuit we need a sufficient upper bound for the amount data used to specify the information about each of the formula_40 amplitudes. To do this formula_1 bits of precision are sufficient for encoding each amplitude . So it takes formula_46 classical bits to account for the state vector of the formula_31 qubit system. Next the application of the formula_8 quantum gates on formula_40 amplitudes must be accounted for. The quantum gates can be represented as formula_50 sparse matrices. So to account for the application of each of the formula_8 quantum gates, the state vector must be multiplied by a formula_50 sparse matrix for each of the formula_8 quantum gates. Every time the state vector is multiplied by a formula_50 sparse matrix, formula_55 arithmetic operations must be performed. Therefore, there are formula_56 bit operations for every quantum  gate applied to the state vector. So formula_56 classical gate are needed to simulate formula_31 qubit circuit with just one quantum gate. Therefore, formula_33 classical gates are needed to simulate a quantum circuit of formula_31 qubits with formula_8 quantum gates. While there is no known way to efficiently simulate a quantum computer with a classical computer, it is possible to efficiently simulate a classical computer with a quantum computer. This is evident from the belief that formula_26. 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 formula_63, 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 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: formula_64, with formula_65, if and only if formula_66. Adjacency array model. Next, there is the slightly more complicated adjacency  array model built on the idea of adjacency lists, where every vertex, formula_67"," is associated with an array of neighboring vertices such that formula_68, for the out-degrees of vertices formula_69, where formula_70 is the minimum value of the upper bound of this model, and formula_71 returns the "formula_72" vertex adjacent to formula_73. Additionally, the adjacency array model satisfies the simple graph condition, formula_74, 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. 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 formula_75, but when the array model is used, the complexity is formula_76. Additionally, for brevity, we use the shorthand formula_77 in certain cases, where formula_78. 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 formula_79, a quadratic improvement over the best possible classical query complexity formula_80, which is a linear search. Grover's algorithm is asymptotically optimal; in fact, it uses at most a formula_81 fraction more queries than the best possible algorithm. Deutsch-Jozsa algorithm. The Deutsch-Jozsa algorithm is a quantum algorithm designed to solve a toy problem with a smaller query complexity than is possible with a classical algorithm. The toy problem asks whether  a function formula_82 is constant or balanced, those being the only two possibilities. The only way to evaluate the function formula_83 is to consult a black box or oracle. A classical deterministic algorithm will have to check more than half of the possible inputs to be sure of whether or not the function is constant or balanced. With formula_84 possible inputs, the query complexity of the most efficient classical deterministic algorithm is formula_85. The Deutsch-Jozsa algorithm takes advantage of quantum parallelism to check all of the elements of the domain at once and only needs to query the oracle  once, making its query complexity formula_86.