Circuit Identities and Equivalences

Circuit identities are the arithmetic inside every quantum compiler. IBM's Qiskit transpiler and the Quantinuum tket compiler apply exactly these rewrites — cancelling adjacent inverses ($\mathrm{CNOT}^2=I$, $HH=I$), merging same-axis rotations, and converting CZ to CNOT — to lower a program onto a device's native gate set, since Google's chips supply CZ while IBM's supply CNOT and ECR. The ZX-calculus, and its implementation PyZX, recasts the same identities as graph rewrites and routinely removes a large fraction of the $T$ gates in a circuit, the gates that dominate the cost of fault-tolerant computation. In error correction, Craig Gidney's Stim simulator uses the CNOT and Hadamard propagation tables to push Pauli errors through Clifford encoders and sample syndromes for codes with millions of qubits — a direct application of the Gottesman–Knill machinery, far beyond any amplitude-vector simulator. And on connectivity-limited hardware, the three-CNOT SWAP identity is why routing is a real cost: a compiler inserts physical SWAPs to bring distant qubits together, and minimizing their number is a live optimization in every mapping pass, since each SWAP is three noisy entangling gates the algorithm never asked for.

Think of a circuit as a recipe and identities as the substitutions that leave the finished dish identical. Every substitution is certified by multiplying the relevant $2\times2$ or $4\times4$ matrices and confirming they agree — up to an overall phase that no measurement can detect. The Hadamard is the master key of the whole catalogue: it relabels the $X$ and $Z$ axes of the Bloch sphere, so any rule stated in the $Z$ basis has a mirror image in the $X$ basis obtained by sandwiching with $H$. That is precisely why the controlled-$Z$ and the controlled-NOT are, at bottom, the same gate wearing two different bases — the first figure makes that equivalence a picture rather than a matrix computation.

Commutation, meanwhile, is geometric rather than mysterious: single-qubit gates commute exactly when they rotate about the same Bloch axis and anticommute when their Pauli axes are orthogonal, so $XZ=-ZX$ is not an accident but the statement that $X$ and $Z$ point at right angles. Reordering gates is licensed precisely by this picture. The unifying move behind the two-qubit rules is "pushing a Pauli through a gate" — each of $H$, $S$, and CNOT carries a simple rule for how a Pauli entering one side re-emerges (possibly larger) on the other. The second figure follows a concrete basis state through the three-CNOT SWAP, watching the two bit values physically trade places.

The starting point is the equivalence criterion itself: two gate sequences $U_A$ and $U_B$ implement the same physics exactly when their unitaries coincide up to an overall phase. That phase is unobservable for a closed circuit because measurement probabilities depend on $|\langle\psi|U|\phi\rangle|^2$, which is blind to a common factor $e^{i\phi}$.

where: $U_A,U_B$ — the two unitaries being compared; $e^{i\phi}$ — a global phase, invisible to any measurement of the standalone circuit; $\equiv$ — physical equivalence. Reading: an identity is a proof that two circuits satisfy this relation, so one may be substituted for the other anywhere it appears alone. The single-qubit backbone is a short table of involutions and powers. Each is verified by squaring or cubing a $2\times2$ matrix, and each licenses a cancellation a compiler will use thousands of times.

where: $X,Y,Z$ — the Pauli gates; $H$ — Hadamard; $S=\mathrm{diag}(1,i)$ and $T=\mathrm{diag}(1,e^{i\pi/4})$ — the phase gates; $I$ — identity. Reading: any gate meeting its own inverse annihilates ($HH=I$), and the phase gates form a ladder $I\to T\to S\to Z$ in steps of $\pi/4$ on the Bloch $z$-axis. The Pauli algebra records how the three flips multiply and, crucially, that distinct Paulis anticommute. This is the origin of every "you may not simply reorder these gates" warning.

where: $\{A,B\}=AB+BA$ — the anticommutator. Reading: $XZ=-ZX$, so swapping an adjacent $X$ and $Z$ flips a sign; the products $XY=iZ$ close the group with factors of $i$ that must be tracked when the block is later controlled. The Hadamard conjugations are the most-used identities in the whole catalogue, because they convert any $Z$-basis statement into its $X$-basis mirror. They are the reason CZ and CNOT are interconvertible.

where: $HAH$ — conjugation of $A$ by the (self-inverse) Hadamard. Reading: $H$ exchanges the $X$ and $Z$ axes of the Bloch sphere and reverses the $Y$ axis; the minus sign on $Y$ is a genuine operator sign, harmless alone but real inside a controlled gate. The phase gate $S$ rotates the equatorial Paulis into one another, sending $X\to Y\to -X$ while fixing $Z$. This is the other Clifford generator's conjugation rule.

where: $S^{\dagger}=\mathrm{diag}(1,-i)$ — the inverse phase gate. Reading: $S$ is a $90^\circ$ rotation about the Bloch $z$-axis, so it cycles the equatorial axes $X\to Y$ and leaves the pole axis $Z$ untouched. The two flagship two-qubit identities connect the entanglers and the wire-exchange. The first rebuilds a CNOT from a CZ by a basis change on the target; the second realizes a SWAP with three alternating CNOTs.

where: $\mathrm{CNOT}_{12}$ — control qubit 1, target qubit 2; $\mathrm{CZ}$ — controlled-$Z$, symmetric under exchange of its two qubits; $\mathrm{SWAP}$ — the map $|a,b\rangle\mapsto|b,a\rangle$. Reading: CZ and CNOT differ only by a Hadamard frame on the target, and exchanging two wires costs exactly three two-qubit gates on hardware. Finally, the Pauli-propagation rule for CNOT is the atom of stabilizer simulation: a Pauli on one input line re-emerges as a (possibly two-qubit) Pauli on the output, and same-axis rotations simply add their angles.

where: $X\otimes I$ — $X$ on the control, identity on the target; $X\otimes X$ — $X$ on both qubits. Reading: an $X$ on the control copies onto the target and a $Z$ on the target copies onto the control, while $\mathrm{CNOT}_{12}(Z\otimes I)\mathrm{CNOT}_{12}=Z\otimes I$ and $\mathrm{CNOT}_{12}(I\otimes X)\mathrm{CNOT}_{12}=I\otimes X$ pass through unchanged.

The identities are exact equalities, but several boundary conditions decide whether a given rewrite is actually valid in the surrounding context.

1 · Cancelling a redundant circuit (confidence builder)

A compiler receives the single-wire sequence $H\,H\,X\,Z\,X$ (applied left to right in time, so the operator is $X\,Z\,X\,H\,H$ read right to left). Simplify it to a single gate up to global phase, and count the two-qubit gates saved.

Step 1. Cancel the adjacent Hadamards. Reading the operator right to left, the two $H$'s meet: $HH=I$ by equation (2), so the operator reduces to $X\,Z\,X$. Two single-qubit gates removed at no cost.

Step 2. Collapse the Pauli sandwich. Using the anticommutation $XZ=-ZX$ from equation (3), push the left $X$ through the $Z$: $X\,Z\,X=(-ZX)\,X=-Z\,X^2=-Z\,I=-Z$, since $X^2=I$. The whole five-gate sequence is therefore $-Z$.

Step 3. Discard the phase. The factor $-1=e^{i\pi}$ is a global phase, invisible by equation (1), so as a standalone circuit $H\,H\,X\,Z\,X\equiv Z$. Result: a five-gate sequence compiles to the single gate $Z$ — provided this wire is never used as the target of a later control, in which case the $-1$ would have to be retained. The same cancellation logic ($\mathrm{CNOT}^2=I$) is what removes the expensive entangling gates in real circuits.

2 · The three-CNOT SWAP on a concrete input (fully worked)

Verify that $\mathrm{CNOT}_{12}\,\mathrm{CNOT}_{21}\,\mathrm{CNOT}_{12}$ exchanges the qubits by tracking the input $|1,0\rangle$, and confirm the two other nontrivial basis states.

Step 1. Input $|a,b\rangle=|1,0\rangle$. First $\mathrm{CNOT}_{12}$ (control qubit 1) adds $a=1$ into qubit 2: $|1,0\rangle\mapsto|1,\;0\oplus1\rangle=|1,1\rangle$.

Step 2. Then $\mathrm{CNOT}_{21}$ (control qubit 2, now $1$) adds into qubit 1: $|1,1\rangle\mapsto|1\oplus1,\;1\rangle=|0,1\rangle$.

Step 3. Then $\mathrm{CNOT}_{12}$ (control qubit 1, now $0$) adds $0$ into qubit 2: $|0,1\rangle\mapsto|0,\;1\oplus0\rangle=|0,1\rangle$. The output is $|0,1\rangle$, the exchange of the input $|1,0\rangle$. Input 1,0 → output 0,1, as a SWAP requires.

Step 4. Spot-check the rest: $|0,0\rangle\mapsto|0,0\rangle$ and $|1,1\rangle\mapsto|1,1\rangle$ trivially (symmetric, unchanged by exchange), and by the same arithmetic $|0,1\rangle\mapsto|1,0\rangle$. All four basis states obey $|a,b\rangle\mapsto|b,a\rangle$, confirming the identity and showing why a SWAP on connectivity-limited hardware costs three physical two-qubit gates rather than being free.

3 · Reversing a CNOT with Hadamards

Show that surrounding a CNOT with Hadamards on both wires exchanges control and target: $(H\otimes H)\,\mathrm{CNOT}_{12}\,(H\otimes H)=\mathrm{CNOT}_{21}$.

Step 1. Write $\mathrm{CNOT}_{12}=|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes X$ and rewrite the control projectors using $H$: since $H|0\rangle=|+\rangle$ and $H|1\rangle=|-\rangle$, conjugating the control factor by $H$ turns the $Z$-basis projectors $\{|0\rangle\langle0|,|1\rangle\langle1|\}$ into $X$-basis projectors $\{|+\rangle\langle+|,|-\rangle\langle-|\}$.

Step 2. Simultaneously conjugate the target factor: $HIH=I$ and $HXH=Z$ by equation (4). So $(H\otimes H)\,\mathrm{CNOT}_{12}\,(H\otimes H)=|+\rangle\langle+|\otimes I+|-\rangle\langle-|\otimes Z$, which is a gate that applies $Z$ to qubit 2 conditioned on qubit 1 being $|-\rangle$ — equivalently, a $Z$-controlled operation with the roles of the lines reflected.

Step 3. Recognize the result. Because CZ is symmetric, this expression equals $|0\rangle\langle0|_{2}\otimes I+|1\rangle\langle1|_{2}\otimes X$ acting with control on qubit 2, i.e. $\mathrm{CNOT}_{21}$. A CNOT sandwiched by Hadamards runs backward — a rewrite compilers use to match a fixed hardware control direction without a SWAP.

The circuit-identity catalogue is not a random list; almost every entry is an instance of one structural fact — that a distinguished set of gates maps Pauli operators to Pauli operators under conjugation. That set is the Clifford group, and it is the organizing concept behind stabilizer codes, fault-tolerant control, and the classical simulability boundary of quantum computing.

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §4.2–4.3 (single- and two-qubit gates, circuit identities, Exercises 4.20–4.25) · Preskill, Lecture Notes on Quantum Computation, Ch. 5–6 · Watrous, The Theory of Quantum Information, Ch. 2 · Wilde, Quantum Information Theory, Ch. 3–4 (Clifford gates) · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, §8 · Mermin, Quantum Computer Science, Ch. 2 · Gottesman, "The Heisenberg Representation of Quantum Computers" (1998) · Aaronson & Gottesman, "Improved Simulation of Stabilizer Circuits" (2004). All single-qubit identities (Pauli squares and products, $HXH=Z$, $HZH=X$, $HYH=-Y$, $SXS^{\dagger}=Y$, $S^2=Z$, $T^2=S$) can be confirmed by direct $2\times2$ matrix multiplication — in particular $HYH=-Y$ and $SYS^{\dagger}=-X$, the two carrying real signs. The CNOT/CZ/SWAP relations of equation (6) and the propagation rules of equation (7) can be verified by multiplying the $4\times4$ matrices or by checking all four basis states $\{00,01,10,11\}$, as done in Derivations 1–3. The Clifford Pauli-conjugation closure is Gottesman's stabilizer formalism, and the same-axis rotation-composition law follows from the $\mathrm{SU}(2)$ structure of the Bloch sphere.

Prerequisites. Quantum Circuit Model · Pauli Gates (X, Y, Z) · Hadamard Gate · CNOT Gate · Bloch Sphere Representation of Gates. Leads to. Universal Gate Sets · Controlled-U Gates · Z-Y Decomposition of Single-Qubit Gates · SWAP Gate.

Ask the tutor: Hand me any gate sequence and I will walk you through cancelling it to its shortest equivalent — or show you exactly why a reordering you tried is illegal.