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 matrices, prove the standard identities (CZ from a CNOT, SWAP from three, CNOTs reversed by Hadamards, phase kickback), and assemble controlled- and Toffoli gates from smaller pieces.
What you’ll learn
- Write CNOT, CZ, SWAP and controlled- as matrices, with qubit 0 as the leftmost bit.
- Prove , the reversal of a CNOT by Hadamards, and .
- 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 , with the computational basis ; the left bit is qubit 0, the top wire. A gate acting only on qubit 0 is , one acting only on qubit 1 is . The CNOT with control 0 and target 1 is block-diagonal:
A gate is entangling if it can turn a product state into an entangled one, and the CNOT is:
In general, on qubit 0 followed by the CNOT maps the four inputs to the four Bell states: , , , .
Consider the CNOT with control qubit 1 and target qubit 0, . Which basis states does it exchange?
Show the answer
B.
Now the right bit is the control: it flips the left bit when the right bit is 1, so , while and stay put. Its matrix differs from that of , so ordering conventions matter.
CZ, controlled phases and phase kickback
Conjugate the block form by on the target.
Use and .
CZ is symmetric, so conjugating its other side by yields a CNOT pointing the other way. Hadamards on both qubits reverse a CNOT.
Write for a controlled-. The controlled phase is symmetric for the same reason as CZ, and that symmetry is the heart of phase kickback. If the target is an eigenstate, , then the target is left alone and the phase lands on the control:
What does a CNOT (control 0, target 1) do to ?
- Nothing:
- It gives
- It gives
- It creates an entangled state
Show the answer
B. It gives
, so the CNOT multiplies the control's branch by , turning into . The target is untouched: the eigenvalue was kicked back onto the control.
SWAP from three CNOTs
Write the XOR into qubit 1.
XOR it back into qubit 0, using .
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
The claim, as an operator product: the rightmost CNOT acts first.
Without the 's, the two half-rotations cancel.
anticommutes with , so : the 's flip the second half-rotation, and the halves add instead of cancelling.
The same idea handles every . By the Euler decomposition, any single-qubit gate can be written with , and then . 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 , , is universal for classical reversible logic: with the target ancilla prepared in it computes NAND, . Its sibling CCZ is symmetric in all three qubits, and .
Hardware has no native three-qubit gate. How many -type gates ( or ) 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+ circuits. The Rydberg State lesson derives the seven from the bit identity .
Larger controls are built recursively. With clean ancillas, takes 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, and ; on qubit 0 followed by a CNOT maps to the four Bell states.
- is symmetric, Hadamards on both qubits reverse a CNOT, and three alternating CNOTs make a SWAP.
- Controlled gates turn global phases into relative ones, , and eigenphases of kick back onto the control.
- Two CNOTs suffice for any controlled single-qubit gate; the Toffoli needs 6 CNOTs and 7 gates; takes Toffolis with ancillas.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which statement about is true?
- It has a control and a target that cannot be exchanged
- It equals and is symmetric under swapping the qubits
- It entangles every product input
- It is not a Clifford gate
Show the answer
B. It equals and is symmetric under swapping the qubits
only marks , so it treats both qubits alike, and conjugating a CNOT's target by turns its block into .
What does followed by , only two CNOTs, do to ?
Show the answer
D.
First ; then qubit 0 receives . The result is a cyclic reshuffle, not a swap; the third CNOT finishes the job.
What is , the controlled version of the gate ?
- , since is just a global phase
Show the answer
C.
: a on the control. A global phase of the target gate becomes a relative phase of the control.
A controlled- acts on , where . What is the output?
- An entangled state of the two qubits
- , unchanged
Show the answer
A.
Only the control's branch applies , which multiplies it by ; the target factors out. The phase ends up on the control: phase kickback.
How many CNOTs, together with single-qubit gates, suffice to implement for an arbitrary single-qubit ?
- 1
- 2
- 3
- 4
Show the answer
B. 2
Two: writing with gives .
Go deeper
- Building Controlled-U: the ABC Construction · Controlled gates from CNOTs and single-qubit rotations.
- Toffoli, T-Count & Multi-Controlled Gates · Decomposing big controls into Clifford+T.
- Circuit Identities & Rewriting · Commutation rules and the algebra of circuit optimization.
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).