Universal Gates

Definition

Universal gates are the gates, or sets of gates, from which we can build any quantum circuit to arbitrary accuracy. In classical computing, the NAND gate is universal because we can use it to build any classical logic circuit. In quantum computing, the idea is similar, but the implementation is more subtle because quantum gates must be reversible and unitary.

When we say a gate set is universal, we usually mean that by combining those gates enough times, we can approximate any unitary transformation on any number of qubits.

PS: one single gate is usually not enough for full quantum universality. Most of the time we talk about a universal gate set rather than just one universal gate.

Why universal gates matter

If we know a small set of gates is universal, then:

1. We do not need infinitely many primitive gates in hardware.
2. Complex quantum algorithms can be broken into simpler building blocks.
3. Quantum compilers can translate large circuits into a standard gate library.
4. Real quantum devices can focus on implementing a limited family of high-quality gates.

In short, universal gates are the alphabet of quantum computation.

Common universal gate sets

There are many universal gate sets in quantum computing. Some of the most common ones are:

• Hadamard + T + CNOT
• All single-qubit gates + CNOT
• Hadamard + Phase + CNOT + T

Among these, the set {H, T, CNOT} is one of the most famous universal gate sets.

Gates commonly discussed as universal building blocks

Pauli-X, Pauli-Y and Pauli-Z gates

The Pauli gates are not by themselves universal for full quantum computation, but they are fundamental building blocks. They perform bit flips, phase flips, and bit-phase flips. They appear in error correction, gate decompositions, and circuit simplification.

Hadamard gate

The Hadamard gate is important because it changes the basis of the qubit. It connects the computational basis and the superposition basis. Without basis changes, many quantum algorithms would not be possible.

CNOT gate

The CNOT gate is the standard entangling gate. A quantum computer needs both single-qubit control and entangling multi-qubit control. The CNOT gate provides that second ingredient. In fact, any multi-qubit universality discussion almost always includes CNOT or some equivalent entangling gate.

T gate

The T gate provides a non-Clifford phase rotation. This is extremely important because gates like Hadamard, Phase, and CNOT alone form the Clifford group, and Clifford-only circuits are not sufficient for universal quantum computation. The T gate breaks that limitation.

Toffoli gate

The Toffoli gate is universal for classical reversible computation. That means any classical logic circuit can be embedded into a reversible circuit using Toffoli gates. It is therefore very important in oracle construction and reversible arithmetic.

SWAP gate

The SWAP gate is not usually called universal by itself, but it is practically important. In hardware, two qubits may not be physically adjacent, so SWAP gates help move quantum states across the device.

Fredkin gate

The Fredkin gate is another reversible three-qubit gate. Similar to the Toffoli gate, it is powerful for reversible classical-style logic inside quantum circuits.

A deeper view of universality

To understand universality properly, it helps to separate two ideas:

1. Universal for classical reversible computation

Gates like Toffoli and Fredkin are universal in the reversible classical sense. They can reproduce classical logic without losing information.

2. Universal for quantum computation

For full quantum universality, we need:

1. Arbitrary single-qubit control, or a discrete set that can approximate it.
2. At least one entangling two-qubit gate.

This is why sets such as {H, T, CNOT} are called universal. The Hadamard and T gates give rich enough single-qubit behavior, while CNOT gives entanglement.

Example

Let us understand the idea with a simple example.

Suppose we want to build a circuit that:

1. Creates a superposition.
2. Introduces a non-trivial phase.
3. Entangles two qubits.

We can do that using only the universal set {H, T, CNOT}.

Start with the two-qubit state:

$$|q_0q_1\rangle = |00\rangle \tag{1}$$

Step 1: Apply Hadamard on the first qubit

$$(H \otimes I)|00\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle) \tag{2}$$

This creates superposition.

Step 2: Apply T gate on the first qubit

The T gate changes the phase of the $|1\rangle$ component of the first qubit, so:

$$(T \otimes I)\frac{1}{\sqrt{2}}(|00\rangle + |10\rangle) = \frac{1}{\sqrt{2}}(|00\rangle + e^{i\pi/4}|10\rangle) \tag{3}$$

Now we have a non-Clifford phase.

Step 3: Apply CNOT with first qubit as control

$$CNOT\left(\frac{1}{\sqrt{2}}(|00\rangle + e^{i\pi/4}|10\rangle)\right) = \frac{1}{\sqrt{2}}(|00\rangle + e^{i\pi/4}|11\rangle) \tag{4}$$

Now the two qubits are entangled.

This simple example shows why the set {H, T, CNOT} is so powerful. One gate creates superposition, one gate gives a richer phase structure, and one gate creates entanglement.

Properties

Universal gate sets have the following properties:

• They can approximate any quantum computation to arbitrary accuracy.
• They reduce the number of primitive gates needed in hardware.
• They allow quantum compilers to decompose large circuits into standard blocks.
• They combine single-qubit flexibility with at least one entangling operation.

Conjugate Transpose

Universal gates are not a single matrix, so there is no single conjugate transpose for "the universal gate". Instead, each gate in a universal set has its own conjugate transpose. For example:

• H^\dagger = H
• T^\dagger = \begin{bmatrix}1 & 0 \\ 0 & e^{-i\pi/4}\end{bmatrix}
• CNOT^\dagger = CNOT

Inverse

Similarly, each gate in a universal set has its own inverse:

• H^{-1} = H
• T^{-1} = T^\dagger
• CNOT^{-1} = CNOT

Dagger

The dagger operation for universal gate sets is understood gate by gate. In practice, when we reverse a quantum circuit made of universal gates, we apply the daggers of the gates in the reverse order.

PS: this is exactly why conjugate transpose, inverse, and dagger keep appearing throughout quantum gate theory. They are necessary for reversing circuits and preserving unitarity.