Simple Algorithm
Quantum Computing · Excited State · 22 min

Multi-Qubit & Controlled Gates

CNOT, CZ, SWAP, Toffoli and controlled-U.

One entangling gate plus single-qubit rotations is enough to build every multi-qubit operation. In this lesson you will write two-qubit gates as 4×44\times4 matrices, prove the standard identities (CZ from a CNOT, SWAP from three, CNOTs reversed by Hadamards, phase kickback), and assemble controlled-UU and Toffoli gates from smaller pieces.

What you’ll learn

  • Write CNOT, CZ, SWAP and controlled-UU as 4×44\times4 matrices, with qubit 0 as the leftmost bit.
  • Prove CZ=(I⊗H) CNOT (I⊗H)CZ=(\id\otimes H)\,\mathrm{CNOT}\,(\id\otimes H), the reversal of a CNOT by Hadamards, and SWAP=CNOT0→1CNOT1→0CNOT0→1\mathrm{SWAP}=\mathrm{CNOT}_{0\to1}\mathrm{CNOT}_{1\to0}\mathrm{CNOT}_{0\to1}.
  • Explain phase kickback and why a controlled global phase is a physical phase gate.
  • Build controlled rotations and the Toffoli gate from CNOTs and single-qubit gates, and count their cost.

Two-qubit gates as matrices

Two qubits live in C2⊗C2=C4\C^2\otimes\C^2=\C^4, with the computational basis ∣00⟩,∣01⟩,∣10⟩,∣11⟩\ket{00},\ket{01},\ket{10},\ket{11}; the left bit is qubit 0, the top wire. A gate acting only on qubit 0 is U⊗IU\otimes\id, one acting only on qubit 1 is I⊗U\id\otimes U. The CNOT with control 0 and target 1 is block-diagonal:

CNOT=∣0⟩ ⁣⟨0∣⊗I+∣1⟩ ⁣⟨1∣⊗X=(1000010000010010),∣a,b⟩↦∣a, a⊕b⟩\mathrm{CNOT}=\dyad{0}\otimes\id+\dyad{1}\otimes X=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix},\qquad\ket{a,b}\mapsto\ket{a,\,a\oplus b}
The upper-left block (control ∣0⟩\ket0) is I\id; the lower-right block (control ∣1⟩\ket1) is XX.

A gate is entangling if it can turn a product state into an entangled one, and the CNOT is:

CNOT ∣+⟩∣0⟩=12(∣00⟩+∣11⟩)=∣Φ+⟩.\mathrm{CNOT}\,\ket{+}\ket{0}=\tfrac{1}{\sqrt2}(\ket{00}+\ket{11})=\ket{\Phi^+}.

In general, HH on qubit 0 followed by the CNOT maps the four inputs ∣ab⟩\ket{ab} to the four Bell states: ∣00⟩↦∣Φ+⟩\ket{00}\mapsto\ket{\Phi^+}, ∣01⟩↦∣Ψ+⟩\ket{01}\mapsto\ket{\Psi^+}, ∣10⟩↦∣Φ−⟩\ket{10}\mapsto\ket{\Phi^-}, ∣11⟩↦∣Ψ−⟩\ket{11}\mapsto\ket{\Psi^-}.

Check your understanding

Consider the CNOT with control qubit 1 and target qubit 0, X⊗∣1⟩ ⁣⟨1∣+I⊗∣0⟩ ⁣⟨0∣X\otimes\dyad1+\id\otimes\dyad0. Which basis states does it exchange?

  1. ∣10⟩↔∣11⟩\ket{10}\leftrightarrow\ket{11}
  2. ∣01⟩↔∣11⟩\ket{01}\leftrightarrow\ket{11}
  3. ∣00⟩↔∣01⟩\ket{00}\leftrightarrow\ket{01}
  4. ∣01⟩↔∣10⟩\ket{01}\leftrightarrow\ket{10}
Show the answer

B. ∣01⟩↔∣11⟩\ket{01}\leftrightarrow\ket{11}

Now the right bit is the control: it flips the left bit when the right bit is 1, so ∣01⟩↔∣11⟩\ket{01}\leftrightarrow\ket{11}, while ∣00⟩\ket{00} and ∣10⟩\ket{10} stay put. Its matrix differs from that of CNOT0→1\mathrm{CNOT}_{0\to1}, so ordering conventions matter.

CZ, controlled phases and phase kickback

CZ=∣0⟩ ⁣⟨0∣⊗I+∣1⟩ ⁣⟨1∣⊗Z=diag⁡(1,1,1,−1)CZ=\dyad0\otimes\id+\dyad1\otimes Z=\diag(1,1,1,-1)
CZ multiplies ∣11⟩\ket{11} by −1-1 and does nothing else, so it is symmetric: there is no distinction between control and target.
DerivationCZ from a CNOT, and reversing a CNOT
  1. (I⊗H) CNOT (I⊗H)=∣0⟩ ⁣⟨0∣⊗HIH+∣1⟩ ⁣⟨1∣⊗HXH(\id\otimes H)\,\mathrm{CNOT}\,(\id\otimes H)=\dyad0\otimes H\id H+\dyad1\otimes HXH

    Conjugate the block form by HH on the target.

  2. =∣0⟩ ⁣⟨0∣⊗I+∣1⟩ ⁣⟨1∣⊗Z=CZ=\dyad0\otimes\id+\dyad1\otimes Z=CZ

    Use H2=IH^2=\id and HXH=ZHXH=Z.

  3. (H⊗H) CNOT0→1 (H⊗H)=(H⊗I) CZ (H⊗I)=CNOT1→0(H\otimes H)\,\mathrm{CNOT}_{0\to1}\,(H\otimes H)=(H\otimes\id)\,CZ\,(H\otimes\id)=\mathrm{CNOT}_{1\to0}

    CZ is symmetric, so conjugating its other side by HH yields a CNOT pointing the other way. Hadamards on both qubits reverse a CNOT.

Write Λ(U)=∣0⟩ ⁣⟨0∣⊗I+∣1⟩ ⁣⟨1∣⊗U\Lambda(U)=\dyad0\otimes\id+\dyad1\otimes U for a controlled-UU. The controlled phase CP(φ)=Λ(P(φ))=diag⁡(1,1,1,eiφ)CP(\varphi)=\Lambda(P(\varphi))=\diag(1,1,1,e^{i\varphi}) is symmetric for the same reason as CZ, and that symmetry is the heart of phase kickback. If the target is an eigenstate, U∣u⟩=eiφ∣u⟩U\ket u=e^{i\varphi}\ket u, then the target is left alone and the phase lands on the control:

Λ(U) (α∣0⟩+β∣1⟩)∣u⟩=(α∣0⟩+eiφβ∣1⟩)∣u⟩\Lambda(U)\,\big(\alpha\ket0+\beta\ket1\big)\ket u=\big(\alpha\ket0+e^{i\varphi}\beta\ket1\big)\ket u
This is the mechanism inside Deutsch–Jozsa, phase estimation and Shor's algorithm: the "target" holds an eigenvector, and the information flows back into the control.
Check your understanding

What does a CNOT (control 0, target 1) do to ∣−⟩∣−⟩\ket-\ket-?

  1. Nothing: ∣−⟩∣−⟩\ket-\ket-
  2. It gives ∣+⟩∣−⟩\ket+\ket-
  3. It gives ∣−⟩∣+⟩\ket-\ket+
  4. It creates an entangled state
Show the answer

B. It gives ∣+⟩∣−⟩\ket+\ket-

X∣−⟩=−∣−⟩X\ket-=-\ket-, so the CNOT multiplies the control's ∣1⟩\ket1 branch by −1-1, turning ∣−⟩=12(∣0⟩−∣1⟩)\ket-=\tfrac{1}{\sqrt2}(\ket0-\ket1) into ∣+⟩\ket+. The target is untouched: the eigenvalue was kicked back onto the control.

SWAP from three CNOTs

SWAP∣a,b⟩=∣b,a⟩,SWAP=12(I⊗I+X⊗X+Y⊗Y+Z⊗Z)\mathrm{SWAP}\ket{a,b}=\ket{b,a},\qquad\mathrm{SWAP}=\tfrac12\big(\id\otimes\id+X\otimes X+Y\otimes Y+Z\otimes Z\big)
DerivationThree XORs make a swap
  1. ∣a, b⟩→ CNOT0→1 ∣a, a⊕b⟩\ket{a,\,b}\xrightarrow{\ \mathrm{CNOT}_{0\to1}\ }\ket{a,\,a\oplus b}

    Write the XOR into qubit 1.

  2. → CNOT1→0 ∣a⊕(a⊕b), a⊕b⟩=∣b, a⊕b⟩\xrightarrow{\ \mathrm{CNOT}_{1\to0}\ }\ket{a\oplus(a\oplus b),\,a\oplus b}=\ket{b,\,a\oplus b}

    XOR it back into qubit 0, using a⊕a=0a\oplus a=0.

  3. → CNOT0→1 ∣b, b⊕a⊕b⟩=∣b, a⟩\xrightarrow{\ \mathrm{CNOT}_{0\to1}\ }\ket{b,\,b\oplus a\oplus b}=\ket{b,\,a}

    Once more. The circuit agrees with SWAP on a basis, so by linearity they agree on every state, entangled ones included.

This is the classical XOR-swap trick, made quantum by linearity. It matters on hardware with limited connectivity: moving a qubit one step along a chain costs a SWAP, that is three CNOTs, which is why compilers work hard to minimize routing.

Controlled-U

DerivationA controlled rotation from two CNOTs
  1. Λ(Ry(θ))=(I⊗Ry(θ2)) CNOT (I⊗Ry(−θ2)) CNOT\Lambda\big(R_y(\theta)\big)=\big(\id\otimes R_y(\tfrac\theta2)\big)\,\mathrm{CNOT}\,\big(\id\otimes R_y(-\tfrac\theta2)\big)\,\mathrm{CNOT}

    The claim, as an operator product: the rightmost CNOT acts first.

  2. control ∣0⟩:Ry(θ2) Ry(−θ2)=I\text{control }\ket0:\qquad R_y(\tfrac\theta2)\,R_y(-\tfrac\theta2)=\id

    Without the XX's, the two half-rotations cancel.

  3. control ∣1⟩:Ry(θ2) X Ry(−θ2) X=Ry(θ2) Ry(θ2)=Ry(θ)\text{control }\ket1:\qquad R_y(\tfrac\theta2)\,X\,R_y(-\tfrac\theta2)\,X=R_y(\tfrac\theta2)\,R_y(\tfrac\theta2)=R_y(\theta)

    XX anticommutes with YY, so XRy(ϕ)X=Ry(−ϕ)XR_y(\phi)X=R_y(-\phi): the XX's flip the second half-rotation, and the halves add instead of cancelling.

The same idea handles every UU. By the Euler decomposition, any single-qubit gate can be written U=eiαAXBXCU=e^{i\alpha}AXBXC with ABC=IABC=\id, and then Λ(U)=(P(α)⊗I)(I⊗A) CNOT (I⊗B) CNOT (I⊗C)\Lambda(U)=(P(\alpha)\otimes\id)(\id\otimes A)\,\mathrm{CNOT}\,(\id\otimes B)\,\mathrm{CNOT}\,(\id\otimes C). Two CNOTs suffice for any controlled single-qubit gate. The Rydberg State lesson on the ABC construction proves this, and shows exactly when one CNOT is enough.

Toffoli and many controls

The Toffoli gate Λ2(X)\Lambda_2(X), ∣a,b,c⟩↦∣a,b,c⊕ab⟩\ket{a,b,c}\mapsto\ket{a,b,c\oplus ab}, is universal for classical reversible logic: with the target ancilla prepared in ∣1⟩\ket1 it computes NAND, ∣a,b,1⟩↦∣a,b,¬(a∧b)⟩\ket{a,b,1}\mapsto\ket{a,b,\lnot(a\wedge b)}. Its sibling CCZ =diag⁡(1,1,1,1,1,1,1,−1)=\diag(1,1,1,1,1,1,1,-1) is symmetric in all three qubits, and Toffoli=(I⊗I⊗H) CCZ (I⊗I⊗H)\mathrm{Toffoli}=(\id\otimes\id\otimes H)\,\mathrm{CCZ}\,(\id\otimes\id\otimes H).

Predict before you look

Hardware has no native three-qubit gate. How many TT-type gates (TT or T†T^\dagger) does the standard ancilla-free decomposition of the Toffoli use?

Show the answer

7 T gates

Seven, together with 6 CNOTs and 2 Hadamards, and seven is optimal for ancilla-free Clifford+TT circuits. The Rydberg State lesson derives the seven from the bit identity 4abc=a+b+c−(a⊕b)−(a⊕c)−(b⊕c)+(a⊕b⊕c)4abc=a+b+c-(a\oplus b)-(a\oplus c)-(b\oplus c)+(a\oplus b\oplus c).

Larger controls are built recursively. With k−2k-2 clean ancillas, Λk(X)\Lambda_k(X) takes 2k−32k-3 Toffolis: compute the AND of the controls step by step into the ancillas, flip the target, then uncompute the ancillas so they can be reused and do not spoil interference.

Key takeaways

  • With qubit 0 as the left bit, CNOT=∣0⟩ ⁣⟨0∣⊗I+∣1⟩ ⁣⟨1∣⊗X\mathrm{CNOT}=\dyad0\otimes\id+\dyad1\otimes X and Λ(U)=∣0⟩ ⁣⟨0∣⊗I+∣1⟩ ⁣⟨1∣⊗U\Lambda(U)=\dyad0\otimes\id+\dyad1\otimes U; HH on qubit 0 followed by a CNOT maps ∣ab⟩\ket{ab} to the four Bell states.
  • CZ=(I⊗H) CNOT (I⊗H)CZ=(\id\otimes H)\,\mathrm{CNOT}\,(\id\otimes H) is symmetric, Hadamards on both qubits reverse a CNOT, and three alternating CNOTs make a SWAP.
  • Controlled gates turn global phases into relative ones, Λ(eiαI)=P(α)⊗I\Lambda(e^{i\alpha}\id)=P(\alpha)\otimes\id, and eigenphases of UU kick back onto the control.
  • Two CNOTs suffice for any controlled single-qubit gate; the Toffoli needs 6 CNOTs and 7 TT gates; Λk(X)\Lambda_k(X) takes 2k−32k-3 Toffolis with k−2k-2 ancillas.

Check yourself

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

Question 1

Which statement about CZCZ is true?

  1. It has a control and a target that cannot be exchanged
  2. It equals (I⊗H) CNOT (I⊗H)(\id\otimes H)\,\mathrm{CNOT}\,(\id\otimes H) and is symmetric under swapping the qubits
  3. It entangles every product input
  4. It is not a Clifford gate
Show the answer

B. It equals (I⊗H) CNOT (I⊗H)(\id\otimes H)\,\mathrm{CNOT}\,(\id\otimes H) and is symmetric under swapping the qubits

CZ=diag⁡(1,1,1,−1)CZ=\diag(1,1,1,-1) only marks ∣11⟩\ket{11}, so it treats both qubits alike, and conjugating a CNOT's target by HH turns its XX block into ZZ.

Question 2

What does CNOT0→1\mathrm{CNOT}_{0\to1} followed by CNOT1→0\mathrm{CNOT}_{1\to0}, only two CNOTs, do to ∣a,b⟩\ket{a,b}?

  1. ∣b,a⟩\ket{b,a}
  2. ∣a,b⟩\ket{a,b}
  3. ∣a⊕b, b⟩\ket{a\oplus b,\,b}
  4. ∣b, a⊕b⟩\ket{b,\,a\oplus b}
Show the answer

D. ∣b, a⊕b⟩\ket{b,\,a\oplus b}

First ∣a,b⟩↦∣a,a⊕b⟩\ket{a,b}\mapsto\ket{a,a\oplus b}; then qubit 0 receives a⊕(a⊕b)=ba\oplus(a\oplus b)=b. The result ∣b, a⊕b⟩\ket{b,\,a\oplus b} is a cyclic reshuffle, not a swap; the third CNOT finishes the job.

Question 3

What is Λ(−I)\Lambda(-\id), the controlled version of the gate −I-\id?

  1. I⊗I\id\otimes\id, since −I-\id is just a global phase
  2. I⊗Z\id\otimes Z
  3. Z⊗IZ\otimes\id
  4. −I⊗I-\id\otimes\id
Show the answer

C. Z⊗IZ\otimes\id

Λ(−I)=∣0⟩ ⁣⟨0∣⊗I−∣1⟩ ⁣⟨1∣⊗I=Z⊗I\Lambda(-\id)=\dyad0\otimes\id-\dyad1\otimes\id=Z\otimes\id: a ZZ on the control. A global phase of the target gate becomes a relative phase of the control.

Question 4

A controlled-UU acts on ∣+⟩∣u⟩\ket+\ket u, where U∣u⟩=eiφ∣u⟩U\ket u=e^{i\varphi}\ket u. What is the output?

  1. 12(∣0⟩+eiφ∣1⟩)∣u⟩\tfrac{1}{\sqrt2}(\ket0+e^{i\varphi}\ket1)\ket u
  2. eiφ∣+⟩∣u⟩e^{i\varphi}\ket+\ket u
  3. An entangled state of the two qubits
  4. ∣+⟩∣u⟩\ket+\ket u, unchanged
Show the answer

A. 12(∣0⟩+eiφ∣1⟩)∣u⟩\tfrac{1}{\sqrt2}(\ket0+e^{i\varphi}\ket1)\ket u

Only the control's ∣1⟩\ket1 branch applies UU, which multiplies it by eiφe^{i\varphi}; the target factors out. The phase ends up on the control: phase kickback.

Question 5

How many CNOTs, together with single-qubit gates, suffice to implement Λ(U)\Lambda(U) for an arbitrary single-qubit UU?

  1. 1
  2. 2
  3. 3
  4. 4
Show the answer

B. 2

Two: writing U=eiαAXBXCU=e^{i\alpha}AXBXC with ABC=IABC=\id gives Λ(U)=(P(α)⊗I)(I⊗A) CNOT (I⊗B) CNOT (I⊗C)\Lambda(U)=(P(\alpha)\otimes\id)(\id\otimes A)\,\mathrm{CNOT}\,(\id\otimes B)\,\mathrm{CNOT}\,(\id\otimes C).

Go deeper

Further reading

  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §4.3 (Cambridge, 10th anniv. ed., 2010).
  • A. Barenco et al., "Elementary gates for quantum computation", Phys. Rev. A 52, 3457 (1995).
  • T. Toffoli, "Reversible computing", in Automata, Languages and Programming (ICALP 1980), Lecture Notes in Computer Science 85 (Springer, 1980).