Editing Quantum logic gate (section)

=== Parallel gates ===
[[File:Parallel_quantum_logic_gates.png|thumb|upright=1.8|right|Two gates <math>Y</math> and <math>X</math> in parallel is equivalent to the gate <math>Y \otimes X</math>.]]
The [[Tensor product#Tensor product of linear maps|tensor product]] (or [[Kronecker product]]) of two quantum gates is the gate that is equal to the two gates in parallel.{{r|Nielsen-Chuang|pages=71–75}}{{r|Yanofsky-Mannucci|pages=148}}

If we, as in the picture, combine the Pauli-''Y'' gate with the Pauli-''X'' gate in parallel, then this can be written as:

: <math>C = Y \otimes X = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} \otimes \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 0 \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} & -i \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \\ i \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} & 0 \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\end{bmatrix} = \begin{bmatrix} 0 & 0 & 0 & -i \\ 0 & 0 & -i & 0 \\ 0 & i & 0 & 0 \\ i & 0 & 0 & 0 \end{bmatrix}</math>

Both the Pauli-''X'' and the Pauli-''Y'' gate act on a single qubit. The resulting gate <math>C</math> act on two qubits.

Sometimes the tensor product symbol is omitted, and indexes are used for the operators instead.<ref name="Loss-DiVincenzo">{{cite journal | last1=Loss | first1=Daniel | last2=DiVincenzo | first2=David P. | title=Quantum computation with quantum dots | journal=Physical Review A | volume=57 | issue=1 | date=1998-01-01 | issn=1050-2947 | doi=10.1103/physreva.57.120 | pages=120–126|doi-access=free|arxiv=cond-mat/9701055| bibcode=1998PhRvA..57..120L }} Example in eq. 2.</ref>

==== Hadamard transform ====
{{Further|Hadamard transform}}
The gate <math>H_2 = H \otimes H</math> is the [[#Hadamard gate|Hadamard gate]] {{nowrap|(<math>H</math>)}} applied in parallel on 2 qubits. It can be written as:

:<math>H_2 = H \otimes H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \otimes \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} = \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix}</math>

This "two-qubit parallel Hadamard gate" will, when applied to, for example, the two-qubit zero-vector {{nowrap|(<math>|00\rangle</math>),}} create a quantum state that has equal probability of being observed in any of its four possible outcomes; {{nowrap|<math>|00\rangle</math>,}} {{nowrap|<math>|01\rangle</math>,}} {{nowrap|<math>|10\rangle</math>,}} and {{nowrap|<math>|11\rangle</math>.}} We can write this operation as:

:<math>H_2 |00\rangle = \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} = \frac{1}{2} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} = \frac{1}{2} |00\rangle + \frac{1}{2} |01\rangle +\frac{1}{2} |10\rangle +\frac{1}{2} |11\rangle = \frac{|00\rangle + |01\rangle + |10\rangle + |11\rangle}{2}</math>

[[File:Hadamard transform on 3 qubits.png|thumb|right|upright=2|'''Example:''' The Hadamard transform on a 3-[[qubit]] [[quantum register|register]] {{nowrap|<math>|\psi\rangle</math>.}}]]
Here the amplitude for each measurable state is {{frac|1|2}}. The probability to observe any state is the square of the absolute value of the measurable states amplitude, which in the above example means that there is one in four that we observe any one of the individual four cases. See [[#Measurement|measurement]] for details.

<math>H_2</math> performs the [[Hadamard transform]] on two qubits. Similarly the gate <math>\underbrace{ H \otimes H \otimes \dots \otimes H }_{n\text{ times}} = \bigotimes_{i=0}^{n-1} H = H^{\otimes n} = H_n</math> performs a Hadamard transform on a [[quantum register|register]] of <math>n</math> qubits.

When applied to a register of <math>n</math> qubits all initialized to {{nowrap|<math>|0\rangle</math>,}} the Hadamard transform puts the quantum register into a superposition with equal probability of being measured in any of its <math>2^n</math> possible states:

:<math>\bigotimes_{i=0}^{n-1}(H|0\rangle) = \frac{1}{\sqrt{2^n}} \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} = \frac{1}{\sqrt{2^n}} \Big( |0\rangle + |1\rangle + \dots + |2^n-1\rangle \Big)= \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^{n}-1}|i\rangle</math>

This state is a ''uniform superposition'' and it is generated as the first step in some search algorithms, for example in [[amplitude amplification]] and [[Quantum phase estimation algorithm|phase estimation]].

[[#Measurement|Measuring]] this state results in a [[Random number generation|random number]] between <math>|0\rangle</math> and {{nowrap|<math>|2^n-1\rangle</math>.}}{{efn|name="stochastic-interpretations"|If this actually is a [[stochastic]] effect depends on which [[Interpretations of quantum mechanics|interpretation of quantum mechanics]] that is correct (and if any interpretation can be correct). For example, [[De Broglie–Bohm theory]] and the [[many-worlds interpretation]] asserts [[determinism]]. (In the many-worlds interpretation, a quantum computer is a machine that runs programs ([[quantum circuit]]s) that selects a reality where the probability of it having the solution states of a [[computational problem|problem]] is large. That is, the machine more often than not ends up in a reality where it gives the correct answer. Because ''all'' outcomes are realized in separate universes according to the many-worlds interpretation, the total outcome is deterministic. This ''interpretation'' does however not change the [[quantum mechanics|mechanics]] by which the machine operates.)}} How random the number is depends on the [[Quantum fidelity|fidelity]] of the logic gates. If not measured, it is a quantum state with equal [[probability amplitude]] <math>\frac{1}{\sqrt{2^n}}</math> for each of its possible states.

The Hadamard transform acts on a register <math>|\psi\rangle</math> with <math>n</math> qubits such that <math display="inline">|\psi\rangle = \bigotimes_{i=0}^{n-1} |\psi_i\rangle</math> as follows:
:<math>\bigotimes_{i=0}^{n-1}H|\psi\rangle = \bigotimes_{i=0}^{n-1}\frac{|0\rangle + (-1)^{\psi_i}|1\rangle}{\sqrt{2}} = \frac{1}{\sqrt{2^n}}\bigotimes_{i=0}^{n-1}\Big(|0\rangle + (-1)^{\psi_i}|1\rangle\Big) = H|\psi_0\rangle \otimes H|\psi_1\rangle \otimes \cdots \otimes H|\psi_{n-1}\rangle</math>

==== Application on entangled states ====
If two or more qubits are viewed as a single quantum state, this combined state is equal to the tensor product of the constituent qubits. Any state that can be written as a tensor product from the constituent subsystems are called ''[[separable states]]''. On the other hand, an ''[[Quantum entanglement|entangled state]]'' is any state that cannot be tensor-factorized, or in other words: ''An entangled state can not be written as a tensor product of its constituent qubits states.'' Special care must be taken when applying gates to constituent qubits that make up entangled states.

If we have a set of ''N'' qubits that are entangled and wish to apply a quantum gate on ''M'' < ''N'' qubits in the set, we will have to extend the gate to take ''N'' qubits. This application can be done by combining the gate with an [[identity matrix]] such that their tensor product becomes a gate that act on ''N'' qubits. The identity matrix {{nowrap|(<math>I</math>)}} is a representation of the gate that maps every state to itself (i.e., does nothing at all). In a circuit diagram the identity gate or matrix will often appear as just a bare wire.

[[File:Shows_the_application_of_a_hadamard_gate_on_a_state_that_span_two_qubits.png|thumb|right|upright=1.8|The example given in the text. The Hadamard gate <math>H</math> only act on 1 qubit, but <math>|\psi\rangle</math> is an entangled quantum state that spans 2 qubits. In our example, <math>|\psi\rangle = \frac{|00\rangle + |11\rangle}{\sqrt{2}}</math>.]]
For example, the Hadamard gate {{nowrap|(<math>H</math>)}} acts on a single qubit, but if we feed it the first of the two qubits that constitute the [[quantum entanglement|entangled]] [[Bell state]] {{nowrap|<math>\frac{|00\rangle + |11\rangle}{\sqrt{2}}</math>,}} we cannot write that operation easily. We need to extend the Hadamard gate <math>H</math> with the identity gate <math>I</math> so that we can act on quantum states that span ''two'' qubits:

:<math>K = H \otimes I = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \otimes \begin{bmatrix} 1 & 0 \\ 0 & 1\end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1\end{bmatrix}</math>

The gate <math>K</math> can now be applied to any two-qubit state, entangled or otherwise. The gate <math>K</math> will leave the second qubit untouched and apply the Hadamard transform to the first qubit. If applied to the Bell state in our example, we may write that as:

:<math>K \frac{|00\rangle + |11\rangle}{\sqrt{2}} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1\end{bmatrix} \frac{1}{\sqrt{2}} \begin{bmatrix}1 \\ 0 \\ 0 \\ 1\end{bmatrix} = \frac{1}{2} \begin{bmatrix} 1 \\ 1 \\ 1 \\ -1 \end{bmatrix} = \frac{|00\rangle + |01\rangle + |10\rangle - |11\rangle}{2}</math>

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