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 and that 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))$.

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 fact that $BBP\subseteq BQP$.

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 $O(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. First the amplitudes associated with the $S(n)$ qubits must be accounted for. Therefore, $2^{S(n)}$amplitudes must be accounted for with a $2^{S(n)}$ dimensional complex vector which it the state vector for the $S(n)$ qubit system. Next the application of the $T(n)$ quantum gates on $2^{S(n)}$ amplitudes must be accounted for. Therefore, $O(T(n))$ bits of precision will be required required for encoding each amplitude. So it takes $O(2^{S(n)}T(n))$ classical bits to account for the state vector. The quantum gates can be represented as $2^{S(n)}\times 2^{S(n)}$ sparse matrices. So to account for the each application of all of the quantum gates, the state vector must be multiplied by a $2^{S(n)}\times 2^{S(n)}$ sparse matrix for every quantum gate. 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 can simulate a quantum circuit of $S(n)$ qubits with $O(T(n))$ quantum gates.