User:ColeDU/Quantum complexity theory

Background[edit]

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.

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 $O(T(n))$, $\Omega (T(n))$, and $\Theta (T(n))$. $O(T(n))$ expresses that something is bounded above by $cT(n)$ where $c$ is a constant such that $c>0$ and $T(n)$ is a function of $n$, $\Omega (T(n))$ expresses that something is bounded below by $cT(n)$ where $c$ is a constant such that $c>0$ and $T(n)$ is a function of $n$, and $\Theta (T(n))$ expresses both $O(T(n))$ and $\Omega (T(n))$. These notations also their own names. $O(T(n))$ is called Big O notation, $\Omega (T(n))$ is called Big Omega notation, and $\Theta (T(n))$ is called Big Theta notation.

Complexity Classes Overview

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 $A=(A_{yes},A_{no})$. $A_{yes}$ is the set of yes instances, $A_{no}$ is the set of no instances, and the intersection of these sets is such that $A_{yes}\cap A_{no}=\emptyset$. All of the previous complexity classes contain promise problems.

Complexity Class	Criteria
P	Promise problems for which a polynomial time deterministic Turing machine accepts all strings in $A_{yes}$ and rejects all strings in $A_{no}$
BPP	Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in $A_{yes}$ with a probability of at least ${\frac {2}{3}}$, and accepts every string in $A_{no}$ with a probability of at most ${\frac {1}{3}}$
BQP	Promise problems such that for functions $a,b:\mathbb {N} \rightarrow [0,1]$, there exists a polynomial time generated family of quantum circuits $Q={\{Q_{n}:n\in \mathbb {N} \}}$, where $Q_{n}$ is a circuit which accepts $n$ qubits and gives an output of one qubit. An element $x$ of $A_{yes}$ is accepted by $Q$ with a probability greater than or equal to $a(\left\vert x\right\vert )$. An element $x$ of $A_{no}$ is accepted by $Q$ with a probability less than or equal to $b(\left\vert x\right\vert )$.
PP	Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in $A_{yes}$ with a probability greater than ${\frac {1}{2}}$, and accepts every string in $A_{no}$ with a probability of at most ${\frac {1}{2}}$
P-SPACE	Promise problems for which a deterministic Turing machine, that runs in polynomial space, accepts every string in $A_{yes}$ and rejects all strings in $A_{no}$

Simulating 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 $S(n)$ qubits with $T(n)$ quantum gates can be simulated by a classical circuit with $O(2^{S(n)}T(n)^{3})$ 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 $S(n)$ qubits must be accounted for. Each of the the states of the $S(n)$ 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 $\alpha {\begin{bmatrix}1\\0\end{bmatrix}}+\beta {\begin{bmatrix}0\\1\end{bmatrix}}={\begin{bmatrix}\alpha \\\beta \end{bmatrix}}$ or $\alpha \left\vert 1\right\rangle +\beta \left\vert 0\right\rangle ={\begin{bmatrix}\alpha \\\beta \end{bmatrix}}$ using Dirac notation. The state of the entire $S(n)$ 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 $S(n)$ qubits is a single state vector which has $2^{S(n)}$ dimensions and entries that are the amplitudes associated with each basis state or component vector. Therefore, $2^{S(n)}$amplitudes must be accounted for with a $2^{S(n)}$ dimensional complex vector which is the state vector for the $S(n)$ 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 $2^{S(n)}$ amplitudes. To do this $O(T(n))$ bits of precision are sufficient for encoding each amplitude. So it takes $O(2^{S(n)}T(n))$ classical bits to account for the state vector of the $S(n)$ qubit system. Next the application of the $T(n)$ quantum gates on $2^{S(n)}$ amplitudes must be accounted for. The quantum gates can be represented as $2^{S(n)}\times 2^{S(n)}$ sparse matrices. So to account for the application of each of the $T(n)$ quantum gates, the state vector must be multiplied by a $2^{S(n)}\times 2^{S(n)}$ sparse matrix for each of the $T(n)$ quantum gates. Every time the state vector is multiplied by a $2^{S(n)}\times 2^{S(n)}$ sparse matrix, $O(2^{S(n)})$ arithmetic operations must be preformed. Therefore, there are $O(2^{S(n)}T(n)^{2})$ bit operations for every quantum gate applied to the state vector. So $O(2^{S(n)}T(n)^{2})$ classical gate are needed to simulate $S(n)$ qubit circuit with just one quantum gate. Therefore, $O(2^{S(n)}T(n)^{3})$ classical gates are needed to simulate a quantum circuit of $S(n)$ qubits with $T(n)$ 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 $BBP\subseteq BQP$.

Query Complexity

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 $f:\{0,1\}^{n}\rightarrow \{0,1\}$ is constant or balanced, those being the only two possibilities. The only way to evaluate the function $f$ 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 $2^{n}$ possible inputs, the query complexity of the most efficient classical deterministic algorithm is $2^{n-1}+1$. 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. Meaning the query complexity of the Deutsch-Jozsa algorithm is $1$.