Editing Quantum logic gate (section)

== Circuit composition ==
=== Serially wired gates ===
[[File:Serially_wired_quantum_logic_gates.png|thumb|right|upright=2|Two gates ''Y'' and ''X'' in series. The order in which they appear on the wire is reversed when multiplying them together.]]Assume that we have two gates ''A'' and ''B'' that both act on <math>n</math> qubits. When ''B'' is put after ''A'' in a series circuit, then the effect of the two gates can be described as a single gate ''C''.

: <math>C = B \cdot A</math>

where <math>\cdot</math> is [[Matrix multiplication#Definition|matrix multiplication]]. The resulting gate ''C'' will have the same dimensions as ''A'' and ''B''. The order in which the gates would appear in a circuit diagram is reversed when multiplying them together.{{r|Nielsen-Chuang|p=17–18,22–23,62–64}}{{r|Yanofsky-Mannucci|p=147–169}}

For example, putting the Pauli ''X'' gate after the Pauli ''Y'' gate, both of which act on a single qubit, can be described as a single combined gate ''C'':

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

The product symbol (<math>\cdot</math>) is often omitted.

==== Exponents of quantum gates ====
All [[real number|real]] exponents of [[unitary matrix|unitary matrices]] are also unitary matrices, and all quantum gates are unitary matrices.

Positive integer exponents are equivalent to sequences of serially wired gates (e.g. {{nowrap|<math>X^3 = X \cdot X \cdot X</math>),}} and the real exponents is a generalization of the series circuit. For example, <math>X^\pi</math> and <math>\sqrt{X}=X^{1/2}</math> are both valid quantum gates.

<math>U^0=I</math> for any unitary matrix <math>U</math>. The [[identity matrix]] (<math>I</math>) behaves like a [[NOP (code)|NOP]]<ref>{{cite web|url=https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.i|title=I operation|website=docs.microsoft.com|date=28 July 2023 }}</ref><ref>{{cite web|url=https://qiskit.org/documentation/stubs/qiskit.circuit.library.IGate.html#qiskit.circuit.library.IGate|title=IGate|website=qiskit.org}} [[Qiskit]] online documentation.</ref> and can be represented as bare wire in quantum circuits, or not shown at all.

All gates are unitary matrices, so that <math>U^\dagger U = UU^\dagger = I</math> and {{nowrap|<math>U^\dagger = U^{-1}</math>,}} where <math>\dagger</math> is the [[conjugate transpose]]. This means that negative exponents of gates are [[#Unitary inversion of gates|unitary inverses]] of their positively exponentiated counterparts: {{nowrap|<math>U^{-n} = (U^n)^{\dagger}</math>.}} For example, some negative exponents of the [[#Phase gate|phase shift gates]] are <math>T^{-1}=T^{\dagger}</math> and {{nowrap|<math>T^{-2}=(T^2)^{\dagger}=S^{\dagger}</math>.}}

Note that for a [[Hermitian matrix]] <math>H^\dagger=H,</math> and because of unitarity, <math>HH^\dagger=I,</math> so <math>H^2 = I</math> for all Hermitian gates. They are [[Involutory matrix|involutory]]. Examples of Hermitian gates are the [[#X|Pauli gates]], [[#Hadamard gate|Hadamard]], [[#Controlled gates|CNOT]], [[#Swap gate|SWAP]] and [[#Toffoli|Toffoli]]. Each Hermitian unitary matrix <math>H</math> [[Sylvester's formula#Special case|has the property]] that <math>e^{i\theta H}=(\cos \theta)I+(i\sin \theta) H</math> where <math>H=e^{i\frac{\pi}{2}(I-H)}=e^{-i\frac{\pi}{2}(I-H)}.</math>

The exponent of a gate is a multiple of the duration of time that the [[#Relation to the time evolution operator|time evolution operator]] is applied to a quantum state. E.g. in a [[spin qubit quantum computer]] the <math>\sqrt{\mathrm{SWAP}}</math> gate could be realized via [[exchange interaction]] on the [[Spin (physics)|spin]] of two [[electron]]s for half the duration of a full exchange interaction.<ref name="Loss-DiVincenzo"/>

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

=== Unitary inversion of gates ===
[[File:The_unitary_inverse_of_hadamard-cnot.png|thumb|right|upright=0.6|'''Example:''' The unitary inverse of the Hadamard-CNOT product. The three gates {{nowrap|<math>H</math>,}} <math>I</math> and <math>\mathrm{CNOT}</math> are their own unitary inverses.]]Because all quantum logical gates are [[reversible computing|reversible]], any composition of multiple gates is also reversible. All products and tensor products (i.e. [[#Serially wired gates|series]] and [[#Parallel gates|parallel]] combinations) of [[unitary matrix|unitary matrices]] are also unitary matrices. This means that it is possible to construct an inverse of all algorithms and functions, as long as they contain only gates.

Initialization, measurement, [[Input/Output|I/O]] and spontaneous [[quantum decoherence|decoherence]] are [[Side effect (computer science)|side effects]] in quantum computers. Gates however are [[pure function|purely functional]] and [[bijective]].

If <math>U</math> is a [[unitary matrix]], then <math>U^\dagger U = UU^\dagger = I</math> and {{nowrap|<math>U^\dagger = U^{-1}</math>.}} The dagger (<math>\dagger</math>) denotes the [[conjugate transpose]]. It is also called the [[Hermitian adjoint]].

If a function <math>F</math> is a product of <math>m</math> gates, {{nowrap|<math>F = A_1 \cdot A_2 \cdot \dots \cdot A_m</math>,}} the unitary inverse of the function <math>F^\dagger</math> can be constructed:

Because <math>(UV)^\dagger = V^\dagger U^\dagger</math> we have, after repeated application on itself

:<math>F^\dagger = \left(\prod_{i=1}^{m} A_i\right)^\dagger = \prod_{i=m}^{1} A^\dagger_{i} = A_m^\dagger \cdot \dots \cdot A_2^\dagger \cdot A_1^\dagger</math>

Similarly if the function <math>G</math> consists of two gates <math>A</math> and <math>B</math> in parallel, then <math>G=A\otimes B</math> and {{nowrap|<math>G^\dagger = (A \otimes B)^\dagger = A^\dagger \otimes B^\dagger</math>.}}

Gates that are their own unitary inverses are called [[Hermitian matrix|Hermitian]] or [[self-adjoint operator]]s. Some elementary gates such as the [[#Hadamard|Hadamard]] (''H'') and the [[Pauli matrices|Pauli gates]] (''I'', ''X'', ''Y'', ''Z'') are Hermitian operators, while others like the [[#Phase shift|phase shift]] (''S'', ''T'', ''P'', [[List of quantum logic gates#Relative phase gates|CPhase]]) gates generally are not.

For example, an algorithm for addition can be used for subtraction, if it is being "run in reverse", as its unitary inverse. The [[Quantum Fourier transform#Unitarity|inverse quantum Fourier transform]] is the unitary inverse. Unitary inverses can also be used for [[uncomputation]]. Programming languages for quantum computers, such as [[Microsoft]]'s [[Q Sharp|Q#]],<ref name="adjoint-controlled-qsharp">[https://docs.microsoft.com/en-us/quantum/user-guide/using-qsharp/operations-functions?view=qsharp-preview#controlled-and-adjoint-operations Operations and Functions (Q# documentation)]</ref> Bernhard Ömer's [[Quantum Computation Language|QCL]],{{r|Oemer|page=61}} and [[IBM]]'s [[Qiskit]],<ref>{{cite web|url=https://docs.quantum.ibm.com/api/qiskit/qiskit.circuit.library.UnitaryGate#adjoint|title=UnitaryGate § UnitaryGate adjoint()|website=docs.quantum.ibm.com}}</ref> contain function inversion as programming concepts.