---
# System prepended metadata

title: Universality in Quantum Gates

---

In classical computing, we have logic gates such as the NAND and NOR gate which are regarded as universal. This is because we have limited number of classical operations. 
In quantum computing, however, the number of gates are uncountable. Any arbitary unitary can act as a quantum gate. However, when it comes to hardware realisation, it is not really very convenient to build all the gates. 

A good roadmap would be as follows:
1. **Toffoli and Fredkin Gates for classical computation**: Attempt to show universality in classical computing using reversible gates.
2. **An analysis of well known universal gate sets**, which can go over most standard gate operations:
    1. Toffoli + H set
    2. Rotation/Phase + CNOT Set
    3. Clifford + T set
3. **Analysis of the Clifford + T set to replicate arbitary unitary** (you can try to read a bit about the Solvay-Kitaev Theorem but the math might be a bit too scary).
4. **The DEUTSCH and BARENCO Gates**: These are parameterised gates which can singlehandedly be used to obtain any unitary. Do look into this. Mathematics of both of these are similar but can be tricky.

## Resources

Here are some resources/papers which I have referred to in the past:

1. Williams, C.P. (2011). Quantum Gates. In: Explorations in Quantum Computing. Texts in Computer Science. Springer, London. https://doi.org/10.1007/978-1-84628-887-6_2
2. Journal Article Deutsch, David Elieser, Penrose, Roger, Quantum computational networks, 1989, Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 73-90, 425, 1868, https://royalsocietypublishing.org/doi/abs/10.1098/rspa.1989.0099
3. Ashok Muthukrishnan, “Classical and Quantum Logic Gates: An Introduction to Quantum Computing” Quantum Information Seminar, Friday, Sep. 3, 1999, Rochester Center for Quantum Information (RCQI) http://www2.optics.rochester.edu/~stroud/presentations/muthukrishnan991/LogicGates.pdf
4. Barenco Adriano 1995A universal two-bit gate for quantum computation Proc. R. Soc. Lond. A449679–683 http://doi.org/10.1098/rspa.1995.0066
5. A. Y. Kitaev, “Quantum Computations: Algorithms and Error Correction,” Russ. Math. Surv., Volume 52, Issue 6 (1997) pp. 1191–1249. https://doi.org/10.1070/RM1997v052n06ABEH002155

(If any of these are not accessible, use https://sci-hub.se/)