Simple Algorithm
Quantum Computing · Rydberg State · 26 min

Circuit Identities & Rewriting

Commutation rules and the algebra of circuit optimization.

Two circuits can look nothing alike and still be the same unitary. Compilers exploit this constantly: they cancel, commute, merge and re-synthesize. This lesson collects the identities that matter, proves them in the Heisenberg picture, and maps the limits: why SWAP needs three CNOTs, and why deciding circuit equivalence is hard in general.

What you’ll learn

  • Derive commutation and propagation rules for CNOT, CZ and phase gates, and push Paulis through Clifford circuits in the Heisenberg picture.
  • Prove the ricochet identity (A⊗I)∣Φ+⟩=(I⊗AT)∣Φ+⟩(A\otimes\id)\ket{\Phi^+}=(\id\otimes A^T)\ket{\Phi^+} and use Choi states to test identities on all inputs at once.
  • Explain rotation merging in phase polynomials and the rewriting approach of the ZX-calculus.
  • Apply the CNOT-count criteria for two-qubit gates (SWAP needs three) and state the complexity of circuit equivalence checking.

A working catalog

IdentityReason
HH=IHH=\id, CNOT2=I\mathrm{CNOT}^2=\id, CZ2=ICZ^2=\idself-inverse gates cancel when adjacent
Rz(a)Rz(b)=Rz(a+b)R_z(a)R_z(b)=R_z(a+b); diagonal gates commutesame axis; diagonal matrices commute
ZZ or RzR_z on the control commutes with a CNOTthe CNOT is block-diagonal in the control's ZZ basis
XX or RxR_x on the target commutes with a CNOTthe target blocks are I\id and XX, which commute with XX
CNOTs sharing a control commute, and so do CNOTs sharing a targetXOR of one bit into two places, or of two bits into one place, is order-independent
(H⊗H) CNOT0→1 (H⊗H)=CNOT1→0(H\otimes H)\,\mathrm{CNOT}_{0\to1}\,(H\otimes H)=\mathrm{CNOT}_{1\to0}HH swaps X↔ZX\leftrightarrow Z, exchanging the roles of control and target
CZ01=CZ10=(I⊗H) CNOT0→1 (I⊗H)CZ_{01}=CZ_{10}=(\id\otimes H)\,\mathrm{CNOT}_{0\to1}\,(\id\otimes H)diag⁡(1,1,1,−1)\diag(1,1,1,-1) is symmetric
SWAP=CNOT0→1 CNOT1→0 CNOT0→1\mathrm{SWAP}=\mathrm{CNOT}_{0\to1}\,\mathrm{CNOT}_{1\to0}\,\mathrm{CNOT}_{0\to1}three XORs
CNOT1→2 CNOT0→1=CNOT0→1 CNOT1→2 CNOT0→2\mathrm{CNOT}_{1\to2}\,\mathrm{CNOT}_{0\to1}=\mathrm{CNOT}_{0\to1}\,\mathrm{CNOT}_{1\to2}\,\mathrm{CNOT}_{0\to2}CNOTs that meet head-to-tail do not commute: reordering them creates a third
Operator products: the rightmost gate acts first.
Check your understanding

A ZZ error hits the target just before a CNOT. What error is present just after it?

  1. ZZ on the target only
  2. ZZ on the control only
  3. ZZ on both qubits
  4. XX on both qubits
Show the answer

C. ZZ on both qubits

CNOT Zt=(CNOT Zt CNOT) CNOT=ZcZt CNOT\mathrm{CNOT}\,Z_t=(\mathrm{CNOT}\,Z_t\,\mathrm{CNOT})\,\mathrm{CNOT}=Z_cZ_t\,\mathrm{CNOT}: phase errors propagate from target to control, the opposite direction to bit flips. This is why syndrome-extraction circuits must be scheduled with care.

Ricochet: testing identities on all inputs

DerivationThe ricochet (transpose) identity
  1. ∣Φ+⟩=1d∑j∣j⟩∣j⟩\ket{\Phi^+}=\tfrac{1}{\sqrt d}\sum_{j}\ket{j}\ket{j}

    The maximally entangled state of two dd-dimensional systems.

  2. (A⊗I)∣Φ+⟩=1d∑i,jAij∣i⟩∣j⟩(A\otimes\id)\ket{\Phi^+}=\tfrac{1}{\sqrt d}\sum_{i,j}A_{ij}\ket{i}\ket{j}

    Expand A∣j⟩=∑iAij∣i⟩A\ket j=\sum_iA_{ij}\ket i.

  3. (I⊗AT)∣Φ+⟩=1d∑i,j(AT)ji∣i⟩∣j⟩=1d∑i,jAij∣i⟩∣j⟩(\id\otimes A^T)\ket{\Phi^+}=\tfrac{1}{\sqrt d}\sum_{i,j}(A^T)_{ji}\ket{i}\ket{j}=\tfrac{1}{\sqrt d}\sum_{i,j}A_{ij}\ket{i}\ket{j}

    The same coefficients: a gate on one half of ∣Φ+⟩\ket{\Phi^+} can slide to the other half, transposed.

  4. J(U)=(I⊗U)∣Φ+⟩,∣⟨J(U)∣J(V)⟩∣=1d∣Tr⁡(U†V)∣J(U)=(\id\otimes U)\ket{\Phi^+},\qquad\abs{\braket{J(U)|J(V)}}=\tfrac1d\abs{\Tr(U^\dagger V)}

    The Choi state J(U)J(U) determines UU: the fidelity is 1 iff V=eiγUV=e^{i\gamma}U. Testing on half of a maximally entangled state tests every input at once.

Below, two Bell pairs link reference qubits 0 and 1 with system qubits 2 and 3, followed by a CNOT from 2 to 3. Your goal: using Hadamards alone, make the system's net operation the reversed CNOT, from 3 to 2. The catch is that there is no room for Hadamards before the CNOT on wires 2 and 3. The ricochet identity comes to the rescue: a Hadamard on a reference wire acts like HT=HH^T=H on its partner, before everything else.

Check your understanding

Slide Ry(θ)R_y(\theta) from a system qubit across ∣Φ+⟩\ket{\Phi^+} onto its reference partner. Which gate appears on the reference?

  1. Ry(θ)R_y(\theta)
  2. Rx(θ)R_x(\theta)
  3. Ry(−θ)R_y(-\theta)
  4. Rz(θ)R_z(\theta)
Show the answer

C. Ry(−θ)R_y(-\theta)

The partner receives the transpose. Ry(θ)R_y(\theta) is real, so Ry(θ)T=Ry(θ)†=Ry(−θ)R_y(\theta)^T=R_y(\theta)^\dagger=R_y(-\theta). By contrast, Rx(θ)R_x(\theta) and Rz(θ)R_z(\theta) are symmetric matrices, so they slide across unchanged.

Rewriting at scale: phase polynomials and ZX

Peephole rules cancel adjacent gates, but the big wins come from global structure. In a region built from CNOTs and RzR_z rotations, every Rz(θ)R_z(\theta) acts on a wire that holds some parity y⋅xy\cdot x of the region's inputs, and up to a global phase the region acts as

∣x⟩↦ei∑yθy χy(x)∣Lx⟩,\ket{x}\mapsto e^{i\sum_y\theta_y\,\chi_y(x)}\ket{Lx},

where LL is an invertible linear map over F2\mathbb{F}_2. Two rotations on the same parity merge into one wherever they sit in the region. This rotation merging is the engine of TT-count and TT-depth optimizers (Amy, Maslov & Mosca 2014) and of large-scale optimizers with continuous angles (Nam, Ross, Su, Childs & Maslov 2018).

The ZX-calculus goes further. It represents circuits as graphs of "spiders", generalized ZZ- and XX-phase maps, together with a small set of rewrite rules that are known to be complete: any two diagrams for the same linear map can be rewritten into one another. Graph-theoretic simplification in the ZX-calculus (Duncan, Kissinger, Perdrix & van de Wetering 2020) and phase teleportation (Kissinger & van de Wetering 2020) give some of the best known TT-count reductions.

Think first In a CNOT+RzR_z region, can two TT gates on different wires merge into a single SS?

Yes, if at their respective moments both wires hold the same parity of the region's inputs. Merging depends on the parity a wire carries, not on which wire it is or how far apart the gates are, as long as no Hadamard intervenes.

Limits: lower bounds and hardness

DerivationSWAP needs three CNOTs
  1. det⁡SWAP=−1⟹U=eiπ/4 SWAP∈SU(4)\det\mathrm{SWAP}=-1\quad\Longrightarrow\quad U=e^{i\pi/4}\,\mathrm{SWAP}\in SU(4)

    Normalize first: the criterion is stated for SU(4)SU(4), and (eiπ/4)4=−1(e^{i\pi/4})^4=-1.

  2. SWAP (Y⊗Y) SWAPT=Y⊗Y⟹γ(SWAP)=(Y⊗Y)2=I\mathrm{SWAP}\,(Y\otimes Y)\,\mathrm{SWAP}^T=Y\otimes Y\quad\Longrightarrow\quad\gamma(\mathrm{SWAP})=(Y\otimes Y)^2=\id

    SWAP is real and symmetric, and it commutes with the symmetric operator Y⊗YY\otimes Y.

  3. γ(U)=(eiπ/4)2 γ(SWAP)=i I,Tr⁡γ(U)=4i∉R\gamma(U)=\big(e^{i\pi/4}\big)^2\,\gamma(\mathrm{SWAP})=i\,\id,\qquad\Tr\gamma(U)=4i\notin\R

    γ\gamma is quadratic in UU. The trace is not real, so two CNOTs cannot suffice and SWAP needs exactly three. (The other normalizations, eikπ/4e^{ik\pi/4} with kk odd, give ±4i\pm4i: same conclusion.)

Deciding equivalence is hard in general. Deciding whether a circuit is close to the identity (up to phase) or far from it is QMA-complete (Janzing, Wocjan & Beth 2005), and comparing two circuits U1,U2U_1,U_2 reduces to checking U1†U2U_1^\dagger U_2, so no efficient general algorithm is expected. Special classes are easy: Clifford circuits can be compared in polynomial time with stabilizer tableaux. Practical equivalence checkers combine rewriting, decision diagrams and simulation.

Key takeaways

  • Clifford rewriting is Pauli bookkeeping: a CNOT maps Xc↦XcXtX_c\mapsto X_cX_t and Zt↦ZcZtZ_t\mapsto Z_cZ_t, and HH swaps X↔ZX\leftrightarrow Z, which reverses CNOTs and turns them into CZs.
  • The ricochet identity (A⊗I)∣Φ+⟩=(I⊗AT)∣Φ+⟩(A\otimes\id)\ket{\Phi^+}=(\id\otimes A^T)\ket{\Phi^+} makes Choi states a one-shot test of operator identities.
  • In CNOT+RzR_z regions, rotations on the same parity merge regardless of position; the ZX-calculus extends this to complete graphical rewriting.
  • Two-qubit gates need at most three CNOTs and SWAP needs exactly three; deciding general circuit equivalence is QMA-complete.

Check yourself

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

Question 1

Which Pauli equals CNOT (I⊗Z) CNOT\mathrm{CNOT}\,(\id\otimes Z)\,\mathrm{CNOT}, with control qubit 0?

  1. I⊗Z\id\otimes Z
  2. Z⊗ZZ\otimes Z
  3. Z⊗IZ\otimes\id
  4. X⊗ZX\otimes Z
Show the answer

B. Z⊗ZZ\otimes Z

The CNOT maps ∣a,b⟩↦∣a,a⊕b⟩\ket{a,b}\mapsto\ket{a,a\oplus b}, so the sign (−1)b(-1)^{b} read on the target in the middle equals (−1)a⊕b(-1)^{a\oplus b} in terms of the input bits: that is Z⊗ZZ\otimes Z. A ZZ on the target propagates to the control.

Question 2

Which pair of CNOTs does not commute?

  1. CNOT0→1\mathrm{CNOT}_{0\to1} and CNOT0→2\mathrm{CNOT}_{0\to2}
  2. CNOT0→2\mathrm{CNOT}_{0\to2} and CNOT1→2\mathrm{CNOT}_{1\to2}
  3. CNOT0→1\mathrm{CNOT}_{0\to1} and CNOT1→2\mathrm{CNOT}_{1\to2}
  4. CNOT0→1\mathrm{CNOT}_{0\to1} and CNOT2→3\mathrm{CNOT}_{2\to3}
Show the answer

C. CNOT0→1\mathrm{CNOT}_{0\to1} and CNOT1→2\mathrm{CNOT}_{1\to2}

They meet head-to-tail: qubit 1 is the first one's target and the second one's control. Reordering them creates an extra CNOT0→2\mathrm{CNOT}_{0\to2}.

Question 3

For U=eiπ/4 CNOT∈SU(4)U=e^{i\pi/4}\,\mathrm{CNOT}\in SU(4) one finds γ(U)=−i Z⊗X\gamma(U)=-i\,Z\otimes X. What does the criterion say?

  1. One CNOT: Tr⁡γ(U)=0\Tr\gamma(U)=0 and γ(U)2=−I\gamma(U)^2=-\id
  2. No CNOT is needed
  3. Three CNOTs are needed
  4. The criterion does not apply to a CNOT
Show the answer

A. One CNOT: Tr⁡γ(U)=0\Tr\gamma(U)=0 and γ(U)2=−I\gamma(U)^2=-\id

Tr⁡(Z⊗X)=0\Tr(Z\otimes X)=0 and (−iZ⊗X)2=−I(-iZ\otimes X)^2=-\id: exactly the one-CNOT condition, as it must be for a CNOT itself.

Question 4

What is (H⊗H) CNOT0→1 (H⊗H)(H\otimes H)\,\mathrm{CNOT}_{0\to1}\,(H\otimes H)?

  1. CNOT0→1\mathrm{CNOT}_{0\to1}
  2. CZCZ
  3. SWAP
  4. CNOT1→0\mathrm{CNOT}_{1\to0}
Show the answer

D. CNOT1→0\mathrm{CNOT}_{1\to0}

Write CNOT0→1=12(I⊗I+Z⊗I+I⊗X−Z⊗X)\mathrm{CNOT}_{0\to1}=\tfrac12(\id\otimes\id+Z\otimes\id+\id\otimes X-Z\otimes X). Conjugating by H⊗HH\otimes H swaps X↔ZX\leftrightarrow Z on both qubits, giving 12(I⊗I+X⊗I+I⊗Z−X⊗Z)=CNOT1→0\tfrac12(\id\otimes\id+X\otimes\id+\id\otimes Z-X\otimes Z)=\mathrm{CNOT}_{1\to0}.

Further reading

  • D. Gottesman, "The Heisenberg representation of quantum computers" (1998), arXiv:quant-ph/9807006.
  • V. V. Shende, S. S. Bullock & I. L. Markov, "Recognizing small-circuit structure in two-qubit operators", Phys. Rev. A 70, 012310 (2004).
  • D. Janzing, P. Wocjan & T. Beth, "Non-identity check is QMA-complete", Int. J. Quantum Inf. 3, 463 (2005).
  • Y. Nam, N. J. Ross, Y. Su, A. M. Childs & D. Maslov, "Automated optimization of large quantum circuits with continuous parameters", npj Quantum Inf. 4, 23 (2018).
  • R. Duncan, A. Kissinger, S. Perdrix & J. van de Wetering, "Graph-theoretic simplification of quantum circuits with the ZX-calculus", Quantum 4, 279 (2020).