Editing Quantum logic gate (section)

== Universal quantum gates ==
[[Image:Qcircuit CNOTsqrtSWAP2.svg|upright=1.5|thumb|Both CNOT and <math>\sqrt{\mbox{SWAP}}</math> are universal two-qubit gates and can be transformed into each other.]]
A set of '''universal quantum gates''' is any set of gates to which any operation possible on a quantum computer can be reduced, that is, any other unitary operation can be expressed as a finite sequence of gates from the set. Technically, this is impossible with anything less than an [[uncountable]] set of gates since the number of possible quantum gates is uncountable, whereas the number of finite sequences from a finite set is [[countable]]. To solve this problem, we only require that any quantum operation can be approximated by a sequence of gates from this finite set. Moreover, for [[Unitary transformation (quantum mechanics)|unitaries]] on a constant number of qubits, the [[Solovay–Kitaev theorem]] guarantees that this can be done efficiently. Checking if a set of quantum gates is universal can be done using [[group theory]] methods<ref>{{Cite journal |last1=Sawicki |first1=Adam |last2=Karnas |first2=Katarzyna |date=2017-11-01 |title=Universality of Single-Qudit Gates |url=https://doi.org/10.1007/s00023-017-0604-z |journal=[[Annales Henri Poincaré]] |language=en |volume=18 |issue=11 |pages=3515–3552 |doi=10.1007/s00023-017-0604-z |arxiv=1609.05780 |bibcode=2017AnHP...18.3515S |s2cid=253594045 |issn=1424-0661}}</ref> and/or relation to (approximate) [[Quantum t-design|unitary t-designs]]<ref>{{Cite journal |last1=Sawicki |first1=Adam |last2=Mattioli |first2=Lorenzo |last3=Zimborás |first3=Zoltán |date=2022-05-12 |title=Universality verification for a set of quantum gates |url=https://link.aps.org/doi/10.1103/PhysRevA.105.052602 |journal=[[Physical Review A]] |volume=105 |issue=5 |pages=052602 |doi=10.1103/PhysRevA.105.052602|arxiv=2111.03862 |bibcode=2022PhRvA.105e2602S |s2cid=248761038 }}</ref>

Some universal quantum gate sets include:

* The [[List of quantum logic gates#Rotation operator gates|rotation operators]] {{Math|''R<sub>x</sub>''(''&theta;'')}}, {{Math|''R<sub>y</sub>''(''&theta;'')}}, {{Math|''R<sub>z</sub>''(''&theta;'')}}, the [[#Phase shift gates|phase shift gate]] {{Math|''P''(''&phi;'')}}{{efn|Either the {{math|''P''}} or [[List of quantum logic gates#Identity gate and global phase|{{math|Ph}}]] gate can be used, as <math>R_z(\delta)\operatorname{Ph}(\delta/2)=P(\delta)</math>{{r|Barenco|page=11}}{{r|Williams|pages=76–83}}}} and [[#CNOT|CNOT]] are commonly used to form a universal quantum gate set.<ref name=":0">{{Citation |last=Williams |first=Colin P. |title=Quantum Gates |date=2011 |url=https://doi.org/10.1007/978-1-84628-887-6_2 |work=Explorations in Quantum Computing |pages=51–122 |editor-last=Williams |editor-first=Colin P. |series=Texts in Computer Science |place=London |publisher=Springer |language=en |doi=10.1007/978-1-84628-887-6_2 |isbn=978-1-84628-887-6 |access-date=2021-05-14|url-access=subscription }}</ref>{{efn|This set generates every possible unitary gate exactly. However as the global phase is irrelevant in the  measurement output, universal quantum subsets can be constructed e.g. the set containing {{Math|''R<sub>y</sub>''(''&theta;'')}},{{Math|''R<sub>z</sub>''(''&theta;'')}} and CNOT only spans all unitaries with determinant ±1 but it is sufficient for quantum computation.}}   
* The [[Clifford gates|Clifford]] set {CNOT, ''H'', ''S''} + ''T'' gate. The Clifford set alone is not a universal quantum gate set, as it can be efficiently simulated classically according to the [[Gottesman–Knill theorem]].
* The [[Toffoli gate]] + Hadamard gate.<ref name="Aharonov" /> The Toffoli gate alone forms a set of universal gates for reversible [[Boolean algebra]]ic logic circuits, which encompasses all classical computation.

=== Deutsch gate ===
A single-gate set of universal quantum gates can also be formulated using the parametrized three-qubit Deutsch gate <math>D(\theta)</math>,<ref>{{Citation |last=Deutsch |first=David |title=Quantum computational networks |date=September 8, 1989 |journal=[[Proc. R. Soc. Lond. A]] |volume=425 |issue=1989 |pages=73–90 |bibcode=1989RSPSA.425...73D |doi=10.1098/rspa.1989.0099 |author-link=David Deutsch |s2cid=123073680}}</ref> named after physicist [[David Deutsch]]. It is a general case of ''CC-U'', or ''controlled-controlled-unitary'' gate, and is defined as

: <math>|a, b, c\rangle \mapsto \begin{cases}
 i \cos(\theta) |a, b , c\rangle + \sin(\theta) |a, b, 1 - c\rangle & \text{for}\ a = b = 1, \\
 |a, b, c\rangle & \text{otherwise}.
\end{cases}</math>

Unfortunately, a working Deutsch gate has remained out of reach, due to lack of a protocol. There are some proposals to realize a Deutsch gate with dipole–dipole interaction in neutral atoms.<ref>{{Cite journal |last=Shi |first=Xiao-Feng |date=2018-05-22 |title=Deutsch, Toffoli, and cnot Gates via Rydberg Blockade of Neutral Atoms |url=https://link.aps.org/doi/10.1103/PhysRevApplied.9.051001 |journal=Physical Review Applied |language=en |volume=9 |issue=5 |pages=051001 |arxiv=1710.01859 |bibcode=2018PhRvP...9e1001S |doi=10.1103/PhysRevApplied.9.051001 |issn=2331-7019 |s2cid=118909059}}</ref>

{{anchor|Universal gates|Deutsch gate}}

A universal logic gate for reversible classical computing, the Toffoli gate, is reducible to the Deutsch gate <math>D(\pi/2)</math>, thus showing that all reversible classical logic operations can be performed on a universal quantum computer.

There also exist single two-qubit gates sufficient for universality. In 1996, Adriano Barenco showed that the Deutsch gate can be decomposed using only a single two-qubit gate ([[List of quantum logic gates#Barenco|Barenco gate]]), but it is hard to realize experimentally.{{r|Williams|pages=93}} This feature is exclusive to quantum circuits, as there is no classical two-bit gate that is both reversible and universal.{{r|Williams|pages=93}} Universal two-qubit gates could be implemented to improve classical reversible circuits in fast low-power microprocessors.{{r|Williams|pages=93}}