Editing Quantum logic gate (section)

== Logic function synthesis ==
[[File:Quantum Full Adder.png|upright=1.5|thumb|A quantum [[full adder]], given by Feynman in 1986.<ref name="Feynman-QMC"/> It consists of only [[#Toffoli|Toffoli]] and [[#CNOT|CNOT]] gates. The gate that is surrounded by the dotted square in this picture can be omitted if [[uncomputation]] to restore the ''B output'' is not required.]]
Functions and routines that only use gates can themselves be described as matrices, just like the smaller gates. The matrix that represents a quantum function acting on <math>q</math> qubits has size {{nowrap|<math>2^q \times 2^q</math>.}} For example, a function that acts on a "qubyte" (a [[Quantum register|register]] of 8 qubits) would be represented by a matrix with <math>2^8 \times 2^8 = 256 \times 256</math> elements.

Unitary transformations that are not in the set of gates natively available at the quantum computer (the primitive gates) can be synthesised, or approximated, by combining the available primitive gates in a [[quantum circuit|circuit]]. One way to do this is to factor the matrix that encodes the unitary transformation into a product of tensor products (i.e. [[#Serially wired gates|series]] and [[#Parallel gates|parallel]] circuits) of the available primitive gates. The [[Group (mathematics)|group]] [[Unitary group|U(2<sup>''q''</sup>)]] is the [[symmetry group]] for the gates that act on <math>q</math> qubits.<ref name="Barenco"/> Factorization is then the [[Computational problem|problem]] of finding a path in U(2<sup>''q''</sup>) from the [[Generating set of a group|generating set]] of primitive gates. The [[Solovay–Kitaev theorem]] shows that given a sufficient set of primitive gates, there exist an efficient approximate for any gate. For the general case with a large number of qubits this direct approach to circuit synthesis is [[Computational complexity theory#Intractability|intractable]].<ref>{{Cite journal|last1=Dawson|first1=Christopher M.|last2=Nielsen|first2=Michael|date=2006-01-01|title=The Solovay-Kitaev algorithm|at=Section 5.1, equation 23|url=https://dl.acm.org/doi/abs/10.5555/2011679.2011685|journal=Quantum Information and Computation|volume=6|issue=1|doi=10.26421/QIC6.1-6|language=EN|arxiv=quant-ph/0505030}}</ref><ref>{{Cite journal|last1=Matteo|first1=Olivia Di|title=Parallelizing quantum circuit synthesis|journal=Quantum Science and Technology|year=2016|url=http://dx.doi.org/10.1088/2058-9565/1/1/015003|volume=1|issue=1|page=015003|doi=10.1088/2058-9565/1/1/015003|arxiv=1606.07413|bibcode=2016QS&T....1a5003D|s2cid=62819073}}</ref> This puts a limit on how large functions can be brute-force factorized into primitive quantum gates. Typically quantum programs are instead built using relatively small and simple quantum functions, similar to normal classical programming.

Because of the gates [[unitary matrix|unitary]] nature, all functions must be [[reversible computing|reversible]] and always be [[bijective]] mappings of input to output. There must always exist a function <math>F^{-1}</math> such that {{nowrap|<math>F^{-1}(F(|\psi\rangle)) = |\psi\rangle</math>.}} Functions that are not invertible can be made invertible by adding [[Ancilla bit|ancilla qubits]] to the input or the output, or both. After the function has run to completion, the ancilla qubits can then either be [[Uncomputation|uncomputed]] or left untouched. Measuring or otherwise collapsing the quantum state of an ancilla qubit (e.g. by re-initializing the value of it, or by its spontaneous [[Quantum decoherence|decoherence]]) that have not been uncomputed may result in errors,<ref>{{Cite journal|arxiv=quant-ph/0209060|last1=Aaronson|first1=Scott|title=Quantum Lower Bound for Recursive Fourier Sampling|journal=Quantum Information and Computation|volume=3|issue=2|pages=165–174|year=2002|doi=10.26421/QIC3.2-7|bibcode=2002quant.ph..9060A}}</ref><ref>[https://docs.microsoft.com/en-us/quantum/user-guide/language/statements/quantummemorymanagement?view=qsharp-preview Q# online manual: Quantum Memory Management]</ref> as their state may be entangled with the qubits that are still being used in computations.

Logically irreversible operations, for example addition modulo <math>2^n</math> of two <math>n</math>-qubit registers ''a'' and ''b'', {{nowrap|<math>F(a, b) = a+b \pmod{2^n}</math>,}}{{efn|The input is <math>2n</math> qubits, but the output is just <math>n</math> qubits. Information erasure is not a reversible (or [[Unitarity (physics)|unitary]]) operation, and therefore not allowed. See also [[Landauer's principle]].}} can be made logically reversible by adding information to the output, so that the input can be computed from the output (i.e. there exists a function {{nowrap|<math>F^{-1}</math>).}} In our example, this can be done by passing on one of the input registers to the output: {{nowrap|<math>F(|a\rangle \otimes |b\rangle) = |a+b \pmod{2^n}\rangle \otimes |a\rangle</math>.}} The output can then be used to compute the input (i.e. given the output <math>a+b</math> and {{nowrap|<math>a</math>,}} we can easily find the input; <math>a</math> is given and {{nowrap|<math>(a+b) - a = b</math>)}} and the function is made bijective.

All [[Boolean algebra]]ic expressions can be encoded as unitary transforms (quantum logic gates), for example by using combinations of the [[#Pauli X|Pauli-X]], [[#CNOT|CNOT]] and [[#CCNOT|Toffoli]] gates. These gates are [[Functional completeness|functionally complete]] in the Boolean logic domain.

There are many unitary transforms available in the libraries of [[Q Sharp|Q#]], [[Quantum Computation Language|QCL]], [[Qiskit]], and other [[quantum programming]] languages. It also appears in the literature.<ref>{{Cite journal |title=Quantum circuit for the fast Fourier transform |journal=Quantum Information Processing |volume=19 |issue=277 |year=2020 |first1=Asaka |last1=Ryo |first2=Sakai |last2=Kazumitsu |first3=Yahagi |last3=Ryoko |page=277|doi=10.1007/s11128-020-02776-5 |arxiv=1911.03055 |bibcode=2020QuIP...19..277A |s2cid=207847474 |url=https://link.springer.com/article/10.1007/s11128-020-02776-5}}</ref><ref>{{Cite journal |last1=Montaser |first1=Rasha |title=New Design of Reversible Full Adder/Subtractor using R gate |journal=[[International Journal of Theoretical Physics]] |year=2019 |volume=58 |issue=1 |pages=167–183 |doi=10.1007/s10773-018-3921-1 |arxiv=1708.00306 |bibcode=2019IJTP...58..167M |s2cid=24590164}}</ref>

For example, <math>\mathrm{inc}(|x\rangle) = |x + 1 \pmod{2^{x_\text{length}}}\rangle</math>, where <math>x_\text{length}</math> is the number of qubits that constitutes the [[Quantum register|register]] {{nowrap|<math>x</math>,}} is implemented as the following in QCL:<ref>[http://tph.tuwien.ac.at/~oemer/tgz/qcl-0.6.4.tgz QCL 0.6.4 source code, the file "lib/examples.qcl"]</ref><ref name="Oemer">{{cite thesis|last=Ömer |first=Bernhard |date=2000-01-20 |title=Quantum Programming in QCL |publisher=Institute for Theoretical Physics, Vienna University of Technology |url=http://tph.tuwien.ac.at/~oemer/doc/quprog.pdf |access-date=2021-05-24 |archive-url=https://web.archive.org/web/20220601141903/http://tph.tuwien.ac.at/~oemer/doc/quprog.pdf |archive-date=June 1, 2022}}</ref><ref name="Oemer2">{{cite journal |last=Ömer |first=Bernhard |title=Classical Concepts in Quantum Programming |journal=International Journal of Theoretical Physics |date=29 Apr 2003 |volume=44 |issue=7 |pages=943–955 |doi=10.1007/s10773-005-7071-x |arxiv=quant-ph/0211100 |s2cid=119373370}}</ref>

<syntaxhighlight lang="Verilog">
cond qufunct inc(qureg x) { // increment register
  int i;
  for i = #x-1 to 0 step -1 {
    CNot(x[i], x[0::i]);     // apply controlled-not from
  }                          // MSB to LSB
}
</syntaxhighlight>

[[File:Increment_with_one_on_four_qubits_using_controlled_Pauli_X_gates_only.png|upright=1.6|thumb|right|The generated circuit, when {{nowrap|<math>x_{\text{length}}=4</math>}}. The symbols <math>\oplus</math>, <math>\land</math> and <math>\neg</math> denotes [[Exclusive or|XOR]], [[Logical conjunction|AND]] and [[Negation|NOT]] respectively, and comes from the Boolean representation of Pauli-''X'' with zero or more control qubits when applied to states that are in the computational basis.]]

In QCL, decrement is done by "undoing" increment. The prefix <code>!</code> is used to instead run the [[#Unitary inversion of gates|unitary inverse]] of the function. <code>!inc(x)</code> is the inverse of <code>inc(x)</code> and instead performs the operation {{nowrap|<math>\mathrm{inc}^\dagger |x\rangle = \mathrm{inc}^{-1}(|x\rangle) = |x - 1 \pmod{2^{x_\text{length}}}\rangle</math>.}} The <code>cond</code> keyword means that the function can be [[#Controlled gates|conditional]].<ref name="Oemer-structured-programming"/>

In the [[model of computation]] used in this article (the [[quantum circuit]] model), a classic computer generates the gate composition for the quantum computer, and the quantum computer behaves as a [[coprocessor]] that receives instructions from the classical computer about which primitive gates to apply to which qubits.{{r|Oemer|pages=36–43}}<ref name="cryo-controller">{{cite journal |vauthors=Pauka SJ, Das W, Kalra R, Moini A, Yang Y, Trainer M, Bousquet A, Cantaloube C, Dick N, Gardner GC, Manfra MJ, Reilly DJ|journal=[[Nature Electronics]]|title=A cryogenic CMOS chip for generating control signals for multiple qubits |year=2021 |volume=4 |issue=4 |pages=64–70 |doi=10.1038/s41928-020-00528-y |arxiv=1912.01299 |s2cid=231715555}}</ref> Measurement of quantum registers results in binary values that the classical computer can use in its computations. [[Quantum algorithm]]s often contain both a classical and a quantum part. Unmeasured [[Input/output|I/O]] (sending qubits to remote computers without collapsing their quantum states) can be used to create [[Quantum network|networks of quantum computers]]. [[Quantum teleportation#Entanglement swapping|Entanglement swapping]] can then be used to realize [[distributed algorithms]] with quantum computers that are not directly connected. Examples of distributed algorithms that only require the use of a handful of quantum logic gates are [[superdense coding]], the [[quantum Byzantine agreement]] and the [[BB84]] [[Quantum key distribution|cipherkey exchange protocol]].