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.

This introduction is very clear and insightful, but it could use some citations. I also love the inclusion of the wikilinks. Notice how most wiki articles begin with a summary of the subject and then jump into the background and more details. A quick summary will let readers know right away if your article is the info they're interested in

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.

 The last sentence of this paragraph is rather long and complex. I think it would be clearer if you broke it down into 3-4 short sentences, even if you feel it sounds redenudant, sometimes redundancy improves clarity

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.

 Is asymptotic notation the same a Big O notation 

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

the above is a great insight but it kind comes out of no where. How does it relate to what you have already discusses or what you will discuss later on

Quantum Circuits

Quantum gates always have a degree of imperfection in their implementation. We can not implement a quantum gate without some inaccuracy, so there is a need to approximately apply quantum gates.

When looking at a set of quantum gates that are exactly universal the complexity of the quantum circuit only varies linearly. When looking at a set of quantum gates that are approximately universal the complexity of the quantum circuit varies by factors that are bounded polylogarithmically.

This section needs more work and clarification.

I agree with the other peer reviewer -- more clarification is needed. What does it mean to "approximately apply quantum gates?" You may also want to insert a parenthetical clarification on what it means for quantum gates to be "exactly universal".

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.

I don' know how difficult it is to include graphics, but I think perhaps a graphic here be helpful. Personally, anything I read with just equations is immediately disregarded in my mind. Or perhaps if you could give an example here (or a link to an example) that could help. Would the Deutsch algorithm we discuss in class be applicable?

I am a bit confused about the sentence "Therefore, $O(T(n))$ bits of precision will be required required for encoding each amplitude". What is a bit of precision? I agree with the other peer reviewer's suggestion to include an example, if you can find one. That would certainly clear the idea up. I am sure the math and logic here is sound, but the explanation could be improved. Also, there are some little grammatical errors that need to be resolved.

Prime Factorization

Prime factorization is believed to be a hard problem in classical computing. There is no known algorithm which can factor any integer into its prime factors in polynomial time with a classical computing. However, there are polynomially bounded quantum algorithms which can find the prime factorization of any integer.

This section needs more work