Editing Quantum logic gate (section)

==== Computational complexity and the tensor product ====
The [[Computational complexity of matrix multiplication|time complexity for multiplying]] two <math>n \times n</math>-matrices is at least {{nowrap|<math>\Omega(n^2 \log n)</math>,<ref>{{cite book | last1 = Raz | first1 = Ran | title = Proceedings of the thiry-fourth annual [[ACM Symposium on Theory of Computing]] | chapter = On the complexity of matrix product | author-link = Ran Raz | year = 2002| pages = 144–151 | doi = 10.1145/509907.509932 | isbn = 1581134959 | s2cid = 9582328 }}</ref>}} if using a classical machine. Because the size of a gate that operates on <math>q</math> qubits is <math>2^q \times 2^q</math> it means that the time for simulating a step in a quantum circuit (by means of multiplying the gates) that operates on generic entangled states is {{nowrap|<math>\Omega({2^q}^2 \log({2^q}))</math>.}} For this reason it is believed to be [[Computational complexity theory#Intractability|intractable]] to simulate large entangled quantum systems using classical computers. Subsets of the gates, such as the [[Clifford gates]], or the trivial case of circuits that only implement classical Boolean functions (e.g. combinations of [[#X|X]], [[#CNOT|CNOT]], [[#Toffoli|Toffoli]]), can however be efficiently simulated on classical computers.

The state vector of a [[quantum register]] with <math>n</math> qubits is <math>2^n</math> complex entries. Storing the [[probability amplitude]]s as a list of [[Floating-point arithmetic|floating point]] values is not tractable for large <math>n</math>.