Simple Algorithm
Quantum Computing · Ground State · 17 min

Gates & Circuits

Programming a quantum computer: rotations, controls and the circuit model.

A quantum program is a list of gates. On one qubit, every gate is simply a rotation of the Bloch sphere; on two qubits, a gate can bind them into a single entangled state. In this lesson you will rotate, flip, phase and entangle qubits by hand, and see why a toolbox of just three gates is enough to run any quantum algorithm.

What you’ll learn

  • Picture the single-qubit gates XX, YY, ZZ, HH, SS and TT as rotations of the Bloch sphere.
  • Read a circuit diagram and turn a sequence of gates into a product of matrices, in the right order.
  • Use the CNOT to entangle two qubits and the Toffoli gate to compute AND reversibly.
  • Explain why quantum gates must be reversible and what makes a gate set universal.

Gates are rotations

In an ordinary computer, logic gates such as NOT, AND and OR transform bits. A quantum gate transforms qubits under two strict rules: it must keep the total probability equal to 1, and it must be reversible, so no information is ever destroyed. Matrices that obey both rules are called unitary.

For a single qubit this has a beautiful geometric meaning: every one-qubit gate is a rotation of the Bloch sphere. The three Pauli gates XX, YY and ZZ are half-turns (180°) about the xx, yy and zz axes.

Think first ZZ left ∣0⟩\ket0 and ∣1⟩\ket1 exactly where they were. Is it a useless gate?

No. Z∣0⟩=∣0⟩Z\ket0=\ket0 and Z∣1⟩=−∣1⟩Z\ket1=-\ket1: on a pole it only multiplies the state by a sign, an unobservable global phase. On a superposition, though, the sign lands on one amplitude only and becomes a relative phase: ZZ turns ∣+⟩\ket+ into ∣−⟩\ket-, a half-turn around the equator. A rotation leaves the points on its own axis fixed and moves everything else.

Hadamard and the phase gates

Two more gates appear in almost every algorithm. The Hadamard gate HH is a half-turn about the diagonal axis halfway between xx and zz. It swaps the poles with the equator, H∣0⟩=∣+⟩H\ket0=\ket+ and H∣1⟩=∣−⟩H\ket1=\ket-, and applying it twice brings you home.

The phase gates turn the sphere about the zz-axis by smaller angles: SS by a quarter-turn (90°) and the T gate by an eighth of a turn (45°). Like ZZ, they never change the odds of measuring 0 or 1. They only shift the relative phase.

GateRotation of the Bloch sphereExample
XXhalf-turn about xx∣0⟩↔∣1⟩\ket0\leftrightarrow\ket1 (bit flip)
ZZhalf-turn about zz∣+⟩↔∣−⟩\ket+\leftrightarrow\ket- (phase flip)
HHhalf-turn about the xx–zz diagonal∣0⟩↔∣+⟩\ket0\leftrightarrow\ket+ and ∣1⟩↔∣−⟩\ket1\leftrightarrow\ket-
SSquarter-turn about zz∣+⟩→∣+i⟩\ket+\to\ket{+i}
TTeighth-turn about zz∣+⟩→\ket+\to a point 45° further along the equator
Predict before you look

How many TT gates in a row bring every state back to exactly where it started?

Show the answer

8 T gates

Each TT is a 45° turn about zz, so eight of them make a full 360° turn: T8=IT^8=\id exactly. Along the way, T2=ST^2=S and T4=ZT^4=Z.

Reading a circuit

A circuit diagram is a quantum program written like a musical score. Each horizontal line, a wire, is a qubit that starts in ∣0⟩\ket0 on the left. Time runs from left to right, and each box is a gate applied at that moment.

There is one trap. If a circuit applies AA first and then BB, the state becomes B(A∣ψ⟩)B(A\ket\psi), so the whole circuit is the matrix product BABA. Matrices are written in the reverse of the order in which you read the circuit. And order matters: in general BA≠ABBA\ne AB.

Check your understanding

A circuit applies HH first and then SS. Which matrix describes the whole circuit?

  1. HSHS
  2. H+SH+S
  3. SHSH
  4. S−1HS^{-1}H
Show the answer

C. SHSH

The first gate acts first on the ket, so it sits rightmost: S(H∣ψ⟩)=(SH)∣ψ⟩S(H\ket\psi)=(SH)\ket\psi. Check on ∣0⟩\ket0: SH∣0⟩=S∣+⟩=∣+i⟩SH\ket0=S\ket+=\ket{+i}, whereas HS∣0⟩=H∣0⟩=∣+⟩HS\ket0=H\ket0=\ket+.

Two qubits: the controlled-NOT

With two qubits, a gate can make one qubit's fate depend on the other's. The CNOT (controlled-NOT) has a control, drawn as a dot, and a target, drawn as ⊕\oplus. It flips the target if and only if the control is ∣1⟩\ket1.

InputOutputWhat happened
∣00⟩\ket{00}∣00⟩\ket{00}control is 0: nothing
∣01⟩\ket{01}∣01⟩\ket{01}control is 0: nothing
∣10⟩\ket{10}∣11⟩\ket{11}control is 1: target flipped
∣11⟩\ket{11}∣10⟩\ket{10}control is 1: target flipped
Qubit 0 (the left bit, top wire) is the control. In short, ∣a,b⟩↦∣a, a⊕b⟩\ket{a,b}\mapsto\ket{a,\,a\oplus b}: a reversible XOR.

On basis states the CNOT is ordinary reversible logic. The quantum surprise comes when the control is in superposition: the CNOT acts on both branches at once, and the two qubits become entangled. Neither qubit has a state of its own any more; only the pair does.

Toffoli: logic without erasure

Ordinary AND is not reversible: if it outputs 0, you cannot tell whether the inputs were 00, 01 or 10. The Toffoli gate avoids this by keeping its inputs. It has two controls and one target, and flips the target only when both controls are ∣1⟩\ket1:

∣a,b,c⟩↦∣a, b, c⊕ab⟩.\ket{a,b,c}\mapsto\ket{a,\,b,\,c\oplus ab}.

With the target starting in ∣0⟩\ket0, it writes a∧ba\wedge b there. Since AND and NOT can build any Boolean function, a quantum computer can run any classical computation, reversibly.

Check your understanding

Why can't a quantum circuit simply use an ordinary AND gate, with two inputs and one output?

  1. AND is too slow on quantum hardware
  2. AND only accepts the inputs 0 and 1, never superpositions
  3. AND erases information (output 0 has three possible inputs), but quantum gates must be reversible
  4. Quantum computers never need AND; they only use rotations
Show the answer

C. AND erases information (output 0 has three possible inputs), but quantum gates must be reversible

Every quantum gate is unitary, hence invertible: the input must be recoverable from the output. A two-to-one AND cannot be inverted. The Toffoli keeps its inputs, so it is reversible and works on superpositions too.

A small toolbox is enough

How many different gates does a quantum computer need? Remarkably few. Sequences of just HH and TT can approximate any single-qubit rotation as closely as you like, and adding the CNOT gives a universal gate set: {H, T, CNOT}\{H,\,T,\,\text{CNOT}\} can approximate any quantum computation on any number of qubits.

Think first If HH and TT only approximate most rotations, how can a computer run an algorithm exactly?

It does not need to. Errors from approximating each gate add up at most linearly, so if each of GG gates is within ε/G\varepsilon/G of its target, the whole circuit is within ε\varepsilon. The Solovay–Kitaev theorem guarantees that this costs only a modest overhead: the number of HH and TT gates per rotation grows like a power of log⁡(1/ε)\log(1/\varepsilon).

The circuit model, and what comes next

Put it all together and you have the circuit model of quantum computing: prepare qubits in ∣0⟩\ket0, apply a sequence of gates, then measure. Two numbers describe a circuit's size: its width (how many qubits) and its depth (how many layers of gates must run one after another). Depth matters because real qubits suffer noise: the longer the circuit runs, the more errors creep in.

Excited State lessonWhat you will do there
Single-Qubit Gates as RotationsDerive Rn^(θ)=e−iθ n^⋅σ⃗/2R_{\hat n}(\theta)=e^{-i\theta\,\hat n\cdot\vec\sigma/2} and write every gate, HH, SS and TT included, as a rotation.
Multi-Qubit & Controlled GatesBuild CZ, SWAP and controlled-UU gates out of CNOTs, and prove the identities you used here.
Universality & Gate SetsSee why {H,T,CNOT}\{H, T, \text{CNOT}\} is universal, and meet the Solovay–Kitaev and Gottesman–Knill theorems.
The Circuit ModelFormalize depth and width, mid-circuit measurement and classical control.
In the Excited State level you will make everything in this lesson precise.

Key takeaways

  • Single-qubit gates are rotations of the Bloch sphere: XX, YY, ZZ are half-turns, HH swaps the poles with the equator, and SS and TT are quarter- and eighth-turns about zz.
  • Gates are unitary, hence reversible. A circuit that applies AA and then BB is the matrix product BABA, and order matters.
  • Phase gates change only the relative phase, yet sandwiched between Hadamards a phase flip becomes a bit flip: HZH=XHZH=X.
  • The CNOT flips its target when the control is ∣1⟩\ket1; with the control in superposition it creates entanglement. The Toffoli computes AND reversibly.
  • {H,T,CNOT}\{H, T, \text{CNOT}\} is universal. The Clifford gates HH, SS and CNOT alone are classically simulable; TT supplies the missing power.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Which gate takes ∣0⟩\ket0 to ∣+⟩\ket+?

  1. XX
  2. ZZ
  3. HH
  4. SS
Show the answer

C. HH

HH is a half-turn about the xx–zz diagonal; it swaps the north pole with the point +x+x on the equator, so H∣0⟩=∣+⟩H\ket0=\ket+.

Question 2

Which gates never change the probabilities of measuring 0 or 1, whatever state they act on?

  1. ZZ, SS and TT
  2. XX and HH
  3. Only the identity
  4. HH and TT
Show the answer

A. ZZ, SS and TT

ZZ, SS and TT are rotations about the zz-axis. They change the longitude φ\varphi (the relative phase) but never the latitude θ\theta, which alone sets P(0)=cos⁡2(θ/2)P(0)=\cos^2(\theta/2).

Question 3

A CNOT with qubit 0 as control acts on ∣10⟩\ket{10}. What comes out?

  1. ∣10⟩\ket{10}
  2. ∣01⟩\ket{01}
  3. 12(∣10⟩+∣11⟩)\tfrac{1}{\sqrt2}(\ket{10}+\ket{11})
  4. ∣11⟩\ket{11}
Show the answer

D. ∣11⟩\ket{11}

The control (left bit) is 1, so the target (right bit) flips: ∣10⟩↦∣11⟩\ket{10}\mapsto\ket{11}.

Question 4

Starting from ∣00⟩\ket{00}, which circuit produces the Bell state 12(∣00⟩+∣11⟩)\tfrac{1}{\sqrt2}(\ket{00}+\ket{11})?

  1. A CNOT, then HH on qubit 0
  2. HH on qubit 0, then a CNOT with control 0 and target 1
  3. HH on both qubits
  4. XX on qubit 0, then a CNOT
Show the answer

B. HH on qubit 0, then a CNOT with control 0 and target 1

HH puts the control in 12(∣0⟩+∣1⟩)\tfrac{1}{\sqrt2}(\ket0+\ket1); the CNOT then flips the target only in the ∣1⟩\ket1 branch, giving 12(∣00⟩+∣11⟩)\tfrac{1}{\sqrt2}(\ket{00}+\ket{11}).

Question 5

Which gate set is universal, able to approximate any quantum computation?

  1. {H,S,CNOT}\{H, S, \text{CNOT}\}
  2. {X,Z,CNOT}\{X, Z, \text{CNOT}\}
  3. {H,T,CNOT}\{H, T, \text{CNOT}\}
  4. {Toffoli}\{\text{Toffoli}\}
Show the answer

C. {H,T,CNOT}\{H, T, \text{CNOT}\}

HH and TT generate rotations that approximate any single-qubit gate, and CNOT supplies entanglement; together they are universal.

Go deeper

Further reading

  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §1.3 and §§4.1–4.3 (Cambridge, 10th anniv. ed., 2010).
  • R. de Wolf, Quantum Computing: Lecture Notes, chapter on the circuit model (arXiv:1907.09415).