In short

A circuit identity is an equation of the form "circuit A = circuit B" that lets you rewrite one diagram into another without changing what it computes. Good circuit readers know a handful of these cold — they are the algebraic moves that turn a tangled diagram into a clean one. On single qubits: every Pauli is self-inverse (X^2 = Y^2 = Z^2 = I), Hadamard is self-inverse (H^2 = I), and Hadamard conjugates the Paulis into each other (HXH = Z, HZH = X, HYH = -Y). The phase gates climb a ladder: T^2 = S, S^2 = Z, T^8 = I. On two qubits: CNOT is self-inverse (\text{CNOT}^2 = I), Hadamards on both wires flip CNOT's direction ((H\otimes H)\,\text{CNOT}_{0\to 1}\,(H\otimes H) = \text{CNOT}_{1 \to 0}), and a single Hadamard on the target converts CNOT to CZ. CNOT "translates" a Pauli X from the control to both wires and a Pauli Z from the target to the control — the second of which is phase kickback, the mechanism behind Deutsch, Grover, and Shor. These rewrites are how every quantum compiler works.

Good circuit readers cheat.

When they see a long string of gates, they do not check it line by line — they recognise pieces. They see a CNOT followed immediately by another CNOT with the same control and target, and they mentally delete both: the pair is the identity. They see a Hadamard-Z-Hadamard sandwich and rewrite it as an X. They see a SWAP and know it is really three CNOTs. They see a string of Ts and count them mod 8. Reading circuits becomes pattern matching once you have the catalogue of moves memorised, and simplifying circuits becomes a game of spotting which rewrite applies.

This chapter is that catalogue. About a dozen identities — some obvious, some surprising — that together make up the vocabulary of every quantum-circuit compiler, every optimiser, and every human who wants to read a circuit the way a programmer reads code. You do not need to rediscover these each time you see them. Learn them, and the next circuit you meet will simplify itself.

What a circuit identity is

Two circuits are equal if they compute the same unitary. Two circuits are equivalent up to a global phase if the unitaries they compute differ only by a phase factor e^{i\alpha} that multiplies the whole state and therefore never shows up in any measurement. For all practical quantum-computing purposes, equivalence-up-to-global-phase is as good as equality — physically, the states |\psi\rangle and e^{i\alpha}|\psi\rangle are the same state, as you already met in the global-vs-relative phase article.

An identity is an equation of the form

\text{(left circuit)} = \text{(right circuit)}

where both sides are claimed to compute the same unitary (possibly up to a global phase). The left side is what you have; the right side is what you want to rewrite it into. Sometimes the right side is cheaper (fewer gates, fewer CNOTs, smaller T-count); sometimes it is easier to reason about; sometimes it just reveals what the circuit actually does.

Every identity you meet in this chapter has a short proof — usually a matrix multiplication or a check on basis states — and you should write that proof out at least once in your life. After that, memorise the identity, not the proof.

Single-qubit identities

Start with the easy ones. These are all 2×2 matrix facts in disguise.

Every Pauli is self-inverse

X^2 = Y^2 = Z^2 = I.

Quickest proof — the Paulis are Hermitian (X^\dagger = X, and similarly for Y, Z) and unitary (X^\dagger X = I). Put those together: X^2 = X \cdot X = X^\dagger X = I. Same for Y and Z.

Visually: a Pauli is a 180° rotation of the Bloch sphere about the axis matching its name. Two 180° rotations about the same axis is a 360° rotation, which is the identity (up to a global phase of -1, but that is unobservable).

Why this matters: any time you see two of the same Pauli next to each other in a circuit, you can delete both. X \cdot X \cdot H = H. Z \cdot Z \cdot \text{CNOT} \cdot Z \cdot Z = \text{CNOT}. Self-inverse gates are the first thing a compiler looks for.

Hadamard is self-inverse

H^2 = I.

Check by direct multiplication:

H^2 = \tfrac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = \tfrac{1}{2}\begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} = I.

Geometrically: H is a 180° rotation about the axis halfway between the +x and +z axes of the Bloch sphere. Two such rotations compose to a 360° rotation, which is the identity.

Why this matters: Hadamards often appear at the start and end of a sub-routine — put qubits into the X-basis, do stuff, bring them back. If the "stuff" is the identity, the two flanking Hs cancel. More subtly, HHH = H — three Hadamards is one Hadamard, because the middle two cancel. Compilers look for these runs and prune them.

Hadamard swaps X and Z

HXH = Z, \qquad HZH = X, \qquad HYH = -Y.

Check HXH:

HXH = \tfrac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}.

Multiply the first two matrices:

\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix}.

Why: top-left of the product is (row 1 of H) · (col 1 of X) = 1\cdot 0 + 1\cdot 1 = 1; top-right is 1\cdot 1 + 1\cdot 0 = 1; bottom-left is 1\cdot 0 + (-1)\cdot 1 = -1; bottom-right is 1\cdot 1 + (-1)\cdot 0 = 1.

Now multiply by the remaining H and the \tfrac{1}{2} prefactor:

\tfrac{1}{2}\begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = \tfrac{1}{2}\begin{pmatrix} 2 & 0 \\ 0 & -2 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} = Z.

So HXH = Z. By an identical calculation, HZH = X.

The Y case picks up a minus sign: HYH = -Y. The reason is that Y's axis on the Bloch sphere is perpendicular to the Hadamard rotation axis, so conjugating by H reflects Y's axis through the origin — which is a sign flip.

H X H equals Z as a circuit rewriteTwo single-qubit circuits drawn side by side with an equals sign between them. On the left, a wire passes through three boxes labelled H, X, H in order. On the right, a wire passes through one box labelled Z. A caption notes Hadamard conjugates Pauli X to Pauli Z.HXH|ψ⟩=Z|ψ⟩H conjugates X into Z — swaps bit-flips for phase-flips.
The identity $HXH = Z$ as a circuit rewrite. Wrapping an $X$ in Hadamards turns it into a $Z$. The same move with $Z$ in the middle gives $X$.

Pauli conjugation — sign flips all around

XZX = -Z, \qquad ZXZ = -X, \qquad XYX = -Y, \qquad YZY = -Z, \ldots

Different Paulis anticommute (XZ = -ZX), so conjugating one Pauli by another picks up a minus sign: XZX = -ZXX = -Z \cdot I = -Z. The same argument works for any two distinct Paulis. Same-Pauli conjugation is trivial: XXX = X.

Why this matters: in the stabiliser formalism (covered in the QEC chapters), gates are described by how they push Paulis around. Every Clifford gate — H, S, CNOT — maps Paulis to Paulis (possibly with sign flips). That is the whole content of the Clifford group.

The phase-gate ladder

The phase gate is S = \text{diag}(1, i) and the T gate is S^{1/2} = \text{diag}(1, e^{i\pi/4}). They climb a ladder:

T^2 = S, \qquad S^2 = Z, \qquad T^4 = Z, \qquad T^8 = I.

Direct matrix check for T^2:

T \cdot T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/2} \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} = S.

Why the phase multiplies: both matrices are diagonal, so the product is diagonal with the diagonal entries multiplied. e^{i\pi/4} \cdot e^{i\pi/4} = e^{i\pi/2} = i.

Square again: S^2 = \text{diag}(1, i^2) = \text{diag}(1, -1) = Z. Square once more: Z^2 = I. So four Ts make a Z, eight Ts make the identity. The T gate has order 8 on the Bloch sphere.

Inverses: S^\dagger = S^3 = Z \cdot S (three Ss or equivalently a Z followed by an S); T^\dagger = T^7. You almost never write T^7 — you use T^\dagger — but it is good to know the two are the same operation.

Phase-gate ladder T S Z IA horizontal ladder of four boxes labelled T, S, Z, I. Arrows between boxes labelled squared link them. The sequence reads T squared equals S, S squared equals Z, Z squared equals I. A bottom strip shows T to the eighth equals identity.Tπ/4 phaseSπ/2 phaseZπ phaseI2π phase(·)²(·)²(·)²T⁸ = I — the T gate has order 8.count T-gates mod 8 when optimising.
The phase-gate ladder. Squaring each gate climbs the ladder by one rung: $T \to S \to Z \to I$. Eight $T$s return to the identity.

Two-qubit identities

The real fun starts when gates talk to each other.

CNOT is its own inverse

\text{CNOT}^2 = I.

CNOT permutes the four basis states by swapping |10\rangle \leftrightarrow |11\rangle and leaving |00\rangle, |01\rangle fixed. Do that swap twice and everything goes back to where it started. Formally,

\text{CNOT} \cdot \text{CNOT} = \begin{pmatrix} I & 0 \\ 0 & X \end{pmatrix}\begin{pmatrix} I & 0 \\ 0 & X \end{pmatrix} = \begin{pmatrix} I & 0 \\ 0 & X^2 \end{pmatrix} = \begin{pmatrix} I & 0 \\ 0 & I \end{pmatrix} = I,

using the block-matrix multiplication rule and X^2 = I.

Two CNOTs equal the identityA two-wire circuit showing two consecutive CNOTs with the same control and target. On the right, an equals sign and then two empty wires labelled identity. A caption notes CNOT squared equals I.controltarget=identitytwo consecutive CNOTs with the same wiring cancel.
$\text{CNOT}^2 = I$. Two CNOTs with the same control and target cancel — and every compiler looks for this pattern.

Hadamards on both wires flip CNOT's direction

This is the big one.

(H \otimes H)\,\text{CNOT}_{0 \to 1}\,(H \otimes H) = \text{CNOT}_{1 \to 0}.

In words: a CNOT with control on qubit 0 and target on qubit 1, sandwiched between Hadamards on both wires, becomes a CNOT in the opposite direction — control on qubit 1, target on qubit 0.

Why this is surprising: the CNOT symbol looks asymmetric (the control is a filled dot, the target is a \oplus), so it feels like you should not be able to interchange them by local operations. But Hadamards rotate the computational basis into the X-basis, and in the X-basis CNOT looks like a "target-controls-source" gate. Applying Hadamards on both sides maps this rotated picture back to the computational basis — and you discover that the resulting gate is CNOT with the roles swapped.

A quick verification on basis states. Apply the sandwich to |10\rangle (qubit 0 is 1, qubit 1 is 0):

Step 1. (H \otimes H)|10\rangle = H|1\rangle \otimes H|0\rangle = |-\rangle|+\rangle = \tfrac{1}{2}(|0\rangle - |1\rangle)(|0\rangle + |1\rangle) = \tfrac{1}{2}(|00\rangle + |01\rangle - |10\rangle - |11\rangle).

Step 2. Apply \text{CNOT}_{0 \to 1}. This permutes the amplitudes on |10\rangle and |11\rangle: the amplitude -\tfrac{1}{2} on |10\rangle moves to |11\rangle, and the amplitude -\tfrac{1}{2} on |11\rangle moves to |10\rangle. Result: \tfrac{1}{2}(|00\rangle + |01\rangle - |11\rangle - |10\rangle) = \tfrac{1}{2}(|00\rangle + |01\rangle - |10\rangle - |11\rangle) — the state is unchanged. The CNOT does nothing to this superposition.

Step 3. Apply (H \otimes H) again. Hadamards are self-inverse, so this just undoes step 1: you get back |10\rangle.

So (H\otimes H)\,\text{CNOT}_{0\to 1}\,(H\otimes H)\,|10\rangle = |10\rangle. Compare with \text{CNOT}_{1 \to 0}\,|10\rangle: the control is qubit 1, which is 0, so the gate does nothing — the output is |10\rangle. Match.

You would run through the same calculation for each of the other three basis states and find the outputs match \text{CNOT}_{1 \to 0} every time. Since both sides are linear, matching on the four basis states is enough.

Flipping CNOT direction with HadamardsTwo equivalent two-wire circuits. Left circuit: Hadamards on both wires, then a CNOT with control on top and target on bottom, then Hadamards on both wires. Right circuit: a single CNOT with control on bottom and target on top. An equals sign connects them.HHHHq₀q₁=q₀q₁Hadamards on BOTH wires flip CNOT's direction. One Hadamard is not enough.
$(H\otimes H)\,\text{CNOT}_{0 \to 1}\,(H \otimes H) = \text{CNOT}_{1 \to 0}$. Sandwiching CNOT in Hadamards on both wires exchanges the roles of control and target.

The warning label here: Hadamard on one wire is not enough. (H \otimes I)\,\text{CNOT}\,(H \otimes I) is not CNOT in the reverse direction — it is a different gate entirely. You need both Hadamards.

A single Hadamard on the target converts CNOT and CZ

(I \otimes H)\,\text{CZ}\,(I \otimes H) = \text{CNOT}.

CZ is the controlled-Z gate — same block structure as CNOT, but with Z in the bottom-right block instead of X: \text{CZ} = \text{diag}(1, 1, 1, -1). The identity says: sandwich CZ in Hadamards on the target wire, and you get CNOT.

The reason is exactly HZH = X — the Hadamards on the target conjugate the Z inside the bottom-right block into an X, which is what CNOT has.

(I \otimes H)\,\text{CZ}\,(I \otimes H) = (I \otimes H)\begin{pmatrix} I & 0 \\ 0 & Z \end{pmatrix}(I \otimes H) = \begin{pmatrix} HIH & 0 \\ 0 & HZH \end{pmatrix} = \begin{pmatrix} I & 0 \\ 0 & X \end{pmatrix} = \text{CNOT}.

Why hardware cares: on most superconducting chips the native two-qubit gate is CZ, not CNOT. The compiler synthesises every CNOT in your program as "H, CZ, H" on the target wire. One CNOT costs exactly one CZ plus two cheap single-qubit Hadamards.

A corollary: CZ is symmetric in its two qubits. You can swap the roles of control and target and CZ is the same gate — because its matrix \text{diag}(1, 1, 1, -1) is symmetric under the |10\rangle \leftrightarrow |01\rangle swap. CNOT is not symmetric, which is why CNOT-reversing needs Hadamards on both wires while CZ needs none.

CNOT pushes Paulis around

\text{CNOT}\,(X \otimes I)\,\text{CNOT} = X \otimes X, \qquad \text{CNOT}\,(I \otimes X)\,\text{CNOT} = I \otimes X,
\text{CNOT}\,(Z \otimes I)\,\text{CNOT} = Z \otimes I, \qquad \text{CNOT}\,(I \otimes Z)\,\text{CNOT} = Z \otimes Z.

Four identities, one pattern: CNOT "translates" single-qubit Paulis between its control and target wires. An X on the control becomes an X on both wires. A Z on the target becomes a Z on both wires. A Z on the control and an X on the target each pass through unchanged.

Why this matters (phase kickback): the third identity, \text{CNOT}\,(I \otimes Z)\,\text{CNOT} = Z \otimes Z, is the first hint that CNOT can copy a phase from the target to the control. A pure phase on the target, conjugated by CNOT, produces a phase on both qubits. If you read it as "CNOT sandwich transforms an I \otimes Z into a Z \otimes Z," you see where the control picked up the phase: it was kicked back from the target.

You can derive each of these on the four basis states; it is six lines of algebra per identity and worth doing once. The pattern — often called the Clifford tableaux — tells you everything about how CNOT interacts with the Pauli group.

CNOT conjugation on PaulisFour small arrow diagrams. Row 1: X on control becomes X on both wires after CNOT sandwich. Row 2: X on target stays X on target. Row 3: Z on control stays Z on control. Row 4: Z on target becomes Z on both wires. Each is rendered as a schematic, labelled with the identity on the right.Pauli push-through rules for CNOT:CNOT · (X ⊗ I) · CNOT=X ⊗ XX on control propagates to target.CNOT · (I ⊗ X) · CNOT=I ⊗ XX on target stays put.CNOT · (Z ⊗ I) · CNOT=Z ⊗ IZ on control stays put.CNOT · (I ⊗ Z) · CNOT=Z ⊗ ZZ on target kicks back to control.Asymmetry: X moves control → target; Z moves target → control.
The four CNOT-Pauli push-through identities. $X$ moves in one direction (control to both), $Z$ moves in the opposite direction (target to both). The $Z$-rule is the phase-kickback identity.

SWAP = three CNOTs

\text{SWAP} = \text{CNOT}_{0 \to 1} \cdot \text{CNOT}_{1 \to 0} \cdot \text{CNOT}_{0 \to 1}.

The SWAP gate exchanges the states of two qubits: \text{SWAP}|\alpha\rangle|\beta\rangle = |\beta\rangle|\alpha\rangle. You can build it from three alternating CNOTs, as derived step-by-step in the SWAP and iSWAP article. The identity is load-bearing on hardware that does not have a native SWAP — which is almost every platform — because it tells the compiler the standard cost of moving one qubit's state to another wire.

Controlled-U commutativity

Two controlled gates with the same control commute with each other:

C\text{-}U_a \cdot C\text{-}U_b \;=\; C\text{-}U_b \cdot C\text{-}U_a

as long as both gates have the same control wire (they may have different targets and different Us). The reason: when the control is |0\rangle both do nothing; when the control is |1\rangle both fire and, since they act on different wires (or on the same wire with single-qubit gates that the compiler groups), they commute.

Two controlled gates on disjoint wires also commute, for the same "they act on different qubits" reason that single-qubit gates on different wires commute.

What does not commute: controlled gates whose control wires interact with each other's target wires — a CNOT from qubit 0 to qubit 1 does not commute with a CNOT from qubit 1 to qubit 2, because the second gate's control reads a wire the first gate wrote.

Why this matters: when you see a stack of controlled gates with the same control, you can freely rearrange them. Compilers look for this and group gates that can be fused.

Phase kickback — the identity that powers Deutsch, Grover, and Shor

One identity gets its own section.

Set up a CNOT with the control in |+\rangle and the target in |-\rangle. First expand both states in the computational basis:

|+\rangle|-\rangle = \tfrac{1}{\sqrt 2}(|0\rangle + |1\rangle) \otimes \tfrac{1}{\sqrt 2}(|0\rangle - |1\rangle) = \tfrac{1}{2}(|00\rangle - |01\rangle + |10\rangle - |11\rangle).

Apply CNOT term by term. The |00\rangle and |01\rangle pieces (control = 0) pass through untouched. The |10\rangle and |11\rangle pieces (control = 1) have their target flipped: |10\rangle \to |11\rangle and |11\rangle \to |10\rangle. Putting it together:

\text{CNOT}(|+\rangle|-\rangle) = \tfrac{1}{2}(|00\rangle - |01\rangle + |11\rangle - |10\rangle) = \tfrac{1}{2}(|00\rangle - |01\rangle - |10\rangle + |11\rangle).

Now factor. Pull the target ket (|0\rangle - |1\rangle) out of each pair:

\tfrac{1}{2}(|00\rangle - |01\rangle - |10\rangle + |11\rangle) = \tfrac{1}{2}|0\rangle(|0\rangle - |1\rangle) - \tfrac{1}{2}|1\rangle(|0\rangle - |1\rangle) = \tfrac{1}{\sqrt 2}(|0\rangle - |1\rangle) \otimes \tfrac{1}{\sqrt 2}(|0\rangle - |1\rangle) = |-\rangle|-\rangle.

Why the normalisation works out: \tfrac{1}{2} pulled through as \tfrac{1}{\sqrt 2} \cdot \tfrac{1}{\sqrt 2}, and the minus sign on the second term of the control pairs with |1\rangle to give the |-\rangle form.

So \text{CNOT}(|+\rangle|-\rangle) = |-\rangle|-\rangle. The control changed from |+\rangle to |-\rangle, while the target stayed at |-\rangle.

That result should stop you. CNOT is advertised as "flip the target if the control is 1." How did the control change?

The answer: phase kickback. When the target is in the eigenstate |-\rangle of X with eigenvalue -1, the X that CNOT wants to apply becomes a multiplication by -1 on the target branch:

X|-\rangle = -|-\rangle.

Because CNOT only fires on the |1\rangle branch of the control, the minus sign only attaches to the |1\rangle branch of the control. The |0\rangle branch of the control still has its original |-\rangle target, unmultiplied. So the control ends up as \tfrac{1}{\sqrt 2}(|0\rangle - |1\rangle) = |-\rangle. The minus sign kicked back from the target to the control.

This is the phase-kickback identity in its cleanest form:

\text{CNOT}(|+\rangle|-\rangle) = |-\rangle|-\rangle, \qquad \text{CNOT}(|-\rangle|-\rangle) = |+\rangle|-\rangle.

The target is an eigenstate of X (the "phase target") and remains unchanged. The control has its X-basis label flipped — from |+\rangle to |-\rangle or vice versa — because the eigenvalue -1 of the target was recorded into the control's relative phase.

Phase kickback schematicA two-wire CNOT circuit. Control on top starts in ket plus, target on bottom starts in ket minus. After CNOT, the control is labelled ket minus in accent red and the target is labelled ket minus unchanged. A curved arrow from target up to control is labelled phase kickback.|+⟩|−⟩|−⟩|−⟩phase −1 kicks backtarget is an X-eigenstate; its eigenvalue rides back onto the control's phase.
Phase kickback. When the target is an eigenstate of the gate ($|-\rangle$ for the $X$ that CNOT applies), the eigenvalue $-1$ attaches to the control's $|1\rangle$ branch — which flips the control's $X$-basis label from $|+\rangle$ to $|-\rangle$.

Phase kickback is the mechanism behind every celebrated quantum algorithm. Deutsch's algorithm uses kickback once (the single-query version of "is this function constant?"). Grover's search uses kickback inside the oracle to mark the correct answer with a phase. Shor's algorithm — and the whole quantum phase-estimation subroutine that powers it — uses kickback repeatedly, reading a phase off an eigenvector of an operator U into a register of control qubits. Memorise this identity. Memorise the word "kickback." It is the technique.

Example 1: simplify a tangled circuit using the catalogue

Here is a little circuit puzzle. You are handed this single-qubit circuit:

H \cdot H \cdot Z \cdot H \cdot X \cdot H \cdot X.

Simplify it to a single gate (or to the identity) using only the identities in this chapter.

Step 1 — cancel the adjacent Hadamards at the left. H \cdot H = I, so the first two gates drop out:

I \cdot Z \cdot H \cdot X \cdot H \cdot X = Z \cdot H \cdot X \cdot H \cdot X.

Why: H^2 = I is the first move every simplifier makes. Always scan for consecutive copies of a self-inverse gate.

Step 2 — fold up the HXH sandwich in the middle. H \cdot X \cdot H = Z by our earlier identity. Substituting:

Z \cdot Z \cdot X.

Step 3 — cancel the two Zs. Z \cdot Z = I:

I \cdot X = X.

Result. The whole circuit H \cdot H \cdot Z \cdot H \cdot X \cdot H \cdot X simplifies to a single Pauli X. Seven gates have collapsed to one.

What just happened pedagogically: by spotting the HXH sandwich and the adjacent copies, a seven-gate circuit became a one-gate circuit. On hardware, the compiled version of this circuit would be one single-qubit gate instead of seven — a ~7× reduction in gate count and a ~7× reduction in the noise budget. This is the sort of optimisation every real QC compiler (Qiskit's transpile, Cirq's merge_single_qubit_gates, Braket's rewriter) is trying to do on every circuit it sees.

Simplification from seven gates to oneThree stages of a single-qubit circuit shown one above the other. Top: seven boxes H, H, Z, H, X, H, X. Middle: five boxes Z, H, X, H, X after cancelling the two Hadamards. Bottom: one box X after folding HXH into Z and cancelling ZZ. Arrows link the stages.start:HHZHXHXcancel HH:ZHXHXfold HXH=Z, cancel ZZ:X
A seven-gate single-qubit circuit collapses to a single $X$ via two rewrites: cancel the $HH$ pair, then fold $HXH$ into $Z$ and cancel the resulting $ZZ$.

Example 2: verify CNOT · (X ⊗ I) · CNOT = X ⊗ X by matrix multiplication

The Pauli push-through identities are worth computing in full at least once, so pick the first one and do it by hand.

Setup. Write CNOT and X \otimes I as 4×4 matrices in the \{|00\rangle, |01\rangle, |10\rangle, |11\rangle\} basis.

\text{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}, \qquad X \otimes I = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}.

Why X \otimes I looks like that: X swaps the |0\rangle and |1\rangle of the first qubit, so it swaps the "00 and 10" pair of basis states and the "01 and 11" pair. That corresponds to permuting rows/columns 1↔3 and 2↔4, which gives the matrix shown.

Step 1 — compute \text{CNOT} \cdot (X \otimes I). Row-by-column multiplication:

\text{CNOT} \cdot (X \otimes I) = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}.

Why: row 1 of CNOT is (1, 0, 0, 0), which picks out row 1 of X \otimes I = (0, 0, 1, 0). Row 2 of CNOT is (0, 1, 0, 0), picking row 2 = (0, 0, 0, 1). Row 3 of CNOT is (0, 0, 0, 1), picking row 4 = (0, 1, 0, 0). Row 4 of CNOT is (0, 0, 1, 0), picking row 3 = (1, 0, 0, 0). Stacked, these are the matrix above.

Step 2 — right-multiply by CNOT. Now compute [\text{CNOT} \cdot (X \otimes I)] \cdot \text{CNOT}. The columns of the result are CNOT applied to the rows you got above, but viewed as column vectors. Easier: act CNOT on the right by permuting columns 3 and 4.

\begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix} \xrightarrow{\text{swap cols 3, 4}} \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}.

Why "swap columns 3, 4": multiplying on the right by CNOT permutes columns the same way CNOT permutes basis states — columns 1 and 2 are fixed, columns 3 and 4 swap.

Step 3 — check that this is X \otimes X. Write down X \otimes X:

X \otimes X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \otimes \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}.

Match. So \text{CNOT}\,(X \otimes I)\,\text{CNOT} = X \otimes X is verified by direct matrix arithmetic.

Result. The identity holds. An X attached to the control wire of a CNOT sandwich propagates to both wires — an algebraic fact that you should now trust by memory, having verified it by matrices once.

Push-through rule CNOT X I CNOT equals X XOn the left, a two-wire circuit with CNOT, then an X gate on the top wire, then another CNOT. On the right, an equals sign followed by a two-wire circuit with X gates on both wires.X=XXX on the control propagates through CNOTs to become X ⊗ X.
The CNOT push-through identity $\text{CNOT}\,(X \otimes I)\,\text{CNOT} = X \otimes X$ as a circuit rewrite. An $X$ attached to the control passes through the two CNOTs and becomes an $X$ on both wires.

Common confusions

Going deeper

You have the working catalogue. The rest of this article shows where these identities come from structurally — the Clifford group, ZX calculus, and T-count optimisation — and gestures at the research frontier on circuit synthesis.

The Clifford group, in one paragraph

The Clifford group on n qubits is the group of unitaries generated by \{H, S, \text{CNOT}\}. It has the special property that conjugating any Pauli by a Clifford gives another Pauli (with a possible sign). This is exactly what the push-through identities say: CNOT conjugation sends X \otimes I to X \otimes X, sends I \otimes Z to Z \otimes Z, etc. Together with H X H = Z and S X S^\dagger = Y (you can check this by matrix), these relations define the Clifford group's action on the Pauli group — and that action determines every circuit-identity rule.

The Gottesman-Knill theorem (1998) says: a quantum circuit made entirely of Clifford gates and computational-basis measurements on initial states in the computational basis can be simulated in polynomial time on a classical computer. So Clifford circuits — despite containing CNOT and apparently creating entanglement — are not where the quantum speedup lives. The speedup comes from non-Clifford gates, most commonly T.

ZX calculus — circuit identities as graph rewrites

The ZX calculus is an alternative notation for quantum circuits in which single-qubit gates become coloured "spiders" on a graph and CNOTs become wires connecting green to red spiders. In this notation, the circuit identities you met in this chapter become graph rewrite rules: local patterns you can apply anywhere on the graph without changing the unitary.

The advantage is that ZX exposes more identities than the circuit notation hides. A string of single-qubit Z-rotations, three CNOTs, and another Z-rotation might be written as a seven-gate circuit with no obvious simplification — but the ZX graph for the same thing might reduce to a single-spider diagram via a sequence of basic rewrite rules. Modern compilers (the pyzx library, the Quantinuum tket compiler) use ZX rewrites as part of their optimisation pipeline, and the approach regularly outperforms traditional circuit-based optimisation.

A famous example: the ZX-based compiler discovered a lower T-count implementation of many standard quantum subroutines than anyone had previously found using circuit rewrites. T-count is the dominant cost on fault-tolerant hardware — see below.

T-count optimisation — where the money is

On a noisy near-term quantum computer (NISQ), CNOTs are the expensive gates. On a fault-tolerant quantum computer, the picture flips: CNOTs (and all Clifford gates) are cheap, but every T or T^\dagger gate requires a fresh magic state, produced by an expensive distillation protocol. The total resource cost of a fault-tolerant quantum algorithm is dominated by its T-count — the number of T gates in its compiled form.

So a whole subfield of QC compilation is devoted to reducing T-count. The landmark paper is Nam, Ross, Su, Childs, Maslov (2018) [1], which introduced a suite of rewrites — some classical, some from the T^8 = I identity, some from ancilla-based tricks — that reduced T-counts on common benchmark circuits by 30-70% compared to earlier optimisers. Their techniques rely heavily on the identities you met in this chapter, applied automatically by a search procedure.

A rough mental model: the Ts in a circuit commute past Clifford gates by the push-through rules (at the cost of modifying the Clifford part); once you collect all the Ts onto the same wire, you count them mod 8 and drop multiples of 8. The more aggressively you can push Ts around, the more cancellations you find.

Pauli-tracking compilers

A practical trick used in almost every real-world compiler: do not execute the Pauli gates at all. Track them symbolically through the circuit, and push them to the end using the push-through identities. At the end, a Pauli on a qubit just before measurement simply flips the classical outcome — which is a classical post-processing step, with zero quantum-gate cost.

The algorithm: whenever a Pauli appears in the circuit, use the push-through rules to commute it past each subsequent Clifford gate. The Pauli may morph (an X on the control of a CNOT becomes an X \otimes X after passing through), but it stays a Pauli and requires no quantum resources — it is just a bookkeeping tag attached to the Clifford frame. The physical quantum device only executes the Clifford part, saving the cost of every Pauli gate in the original circuit.

Qiskit's transpile does this by default. Cirq's optimisers do it. Any compiler that hopes to be competitive on NISQ hardware does it. It is pure circuit-identity technology.

Why the "CNOT, Hadamard, T" set is universal

The final payoff of memorising this identity catalogue: you can now see why \{H, T, \text{CNOT}\} is universal.

  1. H and T together generate a dense subgroup of the single-qubit unitaries (Solovay-Kitaev). So any single-qubit gate can be built from Hs and Ts.
  2. CNOT plus any universal single-qubit gate set is universal for all unitaries on any number of qubits (the Barenco-Bennett-Cleve-DiVincenzo-Margolus-Shor-Sleator-Smolin-Weinfurter theorem from 1995).

Chain those two facts and \{H, T, \text{CNOT}\} is universal. In practice, compilers also include S = T^2 as an explicit gate (so you have "Clifford+T") because S is cheap on fault-tolerant hardware and catching T^2 patterns is common.

The full universal-gate-set discussion lives in the chapter on universal gate sets.

Where this leads next

References

  1. Nam, Ross, Su, Childs, Maslov, Automated optimization of large quantum circuits with continuous parameters (2018) — state-of-the-art T-count reduction using circuit identities. arXiv:1710.07345.
  2. Nielsen and Chuang, Quantum Computation and Quantum Information (2010), §4.2–§4.3 (identities, Clifford group, decomposition theorems) — Cambridge University Press.
  3. John Preskill, Lecture Notes on Quantum Computation, Ch. 5 and 6 (Clifford group and stabiliser formalism) — theory.caltech.edu/~preskill/ph229.
  4. Coecke and Kissinger, Picturing Quantum Processes (2017) — textbook introduction to ZX calculus, with identities as graph rewrites. arXiv:1706.09571 (survey).
  5. Qiskit Textbook, Single Qubit Gates and Multiple Qubits and Entangled States — identities with runnable code.
  6. Wikipedia, Quantum logic gate — matrix forms, identities, and circuit symbols in one place.