Began a larger section on Quantum Circuits and used a source 2 as an in text citation for this section. Made Simulating Quantum Circuits a subsection of the larger Quantum Circuits section. Created a ne heading for a section on Prime Factorization to be added to later.
[[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.<ref name=":1" />
=== 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 <math>S(n)</math> qubits with <math>O(T(n))</math> [[quantum gates]] can be simulated by a classical circuit with <math>O(2^{S(n)}T(n)^3)</math> [[Logic gate|classical gates]].<ref name=":1">{{Citation|last=Cleve|first=Richard|title=An Introduction to Quantum Complexity Theory|date=2000|url=http://dx.doi.org/10.1142/9789810248185_0004|work=Quantum Computation and Quantum Information Theory|volume=|pages=103–127|publisher=WORLD SCIENTIFIC|isbn=978-981-02-4117-9|access-date=October 10, 2020}}</ref> 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 <math>S(n)</math> qubits must be accounted for. Therefore, <math>2^{S(n)}</math>amplitudes must be accounted for with a <math>2^{S(n)}</math> dimensional complex vector which it the state vector for the <math>S(n)</math> qubit system.<ref>{{Cite journal|last=Häner|first=Thomas|last2=Steiger|first2=Damian S.|date=2017-11-12|title=0.5 petabyte simulation of a 45-qubit quantum circuit|url=http://dx.doi.org/10.1145/3126908.3126947|journal=Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis|___location=New York, NY, USA|publisher=ACM|doi=10.1145/3126908.3126947|isbn=978-1-4503-5114-0}}</ref> Next the application of the <math>T(n)</math> quantum gates on <math>2^{S(n)}</math> amplitudes must be accounted for. Therefore, <math>O(T(n))</math> bits of precision will be required required for encoding each amplitude.<ref name=":1" /> So it takes <math>O(2^{S(n)}T(n))</math> classical bits to account for the state vector. The quantum gates can be represented as <math>2^{S(n)}\times2^{S(n)}</math> [[Sparse matrix|sparse matrices]].<ref name=":1" /> So to account for the each application of all of the quantum gates, the state vector must be multiplied by a <math>2^{S(n)}\times2^{S(n)}</math> sparse matrix for every quantum gate. Every time the state vector is multiplied by a <math>2^{S(n)}\times2^{S(n)}</math> sparse matrix <math>O(2^{S(n)})</math> arithmetic operations must be preformed.<ref name=":1" /> Therefore, there are <math>O(2^{S(n)}T(n)^2)</math> bit operations for every quantum gate applied to the state vector. So <math>O(2^{S(n)}T(n)^2)</math> classical gate are needed to simulate <math>S(n)</math> qubit circuit with just one quantum gate. Therefore, <math>O(2^{S(n)}T(n)^3)</math> classical gates can simulate a quantum circuit of <math>S(n)</math> qubits with <math>O(T(n))</math> quantum gates.<ref name=":1" />
