A *universal gate set* is a set of [[Logic Gate|logic]] or [[Quantum Gates|quantum gates]] that can represent every other gate. In the case of logic gates on [[Classical Computer|classical computers]], a combination of two gates can be used to represent all other gates, the so-called NAND (short for NOT-AND) gate and the FANOUT gate. The FANOUT is nothing else than a copy operation: It sends its input to all of its outputs. Since the NAND is more interesting, we will spend a bit of time looking at it in more detail. Following the idea of a truth table (see [[Boolean Logic|Boolean logic]]), we can write all possible outputs of the NAND operation as | NAND | 0 | 1 | | ----- | --- | --- | | **0** | 1 | 1 | | **1** | 1 | 0 | In a picture, the $NAND$ gate is usually drawn ![[nand-gate.excalidraw.light.svg]] The small circle at the right side symbolizes the additional NOT in comparison to an AND gate. To show how the NAND is used to construct other gates, we will construct a NOT gate from a NAND gate ![[not_as_nand_gate.excalidraw.light.svg]] By using the same input on both input legs, we effectively use the diagonal of the matrix above: If we enter $0$, it returns 1 (and the other way around). It acts like a NOT gate. In [[Quantum Computer|quantum computing]], there is not a single gate to construct all other gates. Instead, we need multiple gates to cover all possible [[Quantum Gates|quantum gates]]. Two famous options are - Clifford gates and a $T$ gate - Matchgates and a $SWAP$ gate >[!read]- Further Reading > - [[Quantum Gates]] > - [[Quantum Computer]] > - [[Boolean Logic]] >[!ref]- References