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 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
| Identity | Reason |
|---|---|
| , , | self-inverse gates cancel when adjacent |
| ; diagonal gates commute | same axis; diagonal matrices commute |
| or on the control commutes with a CNOT | the CNOT is block-diagonal in the control's basis |
| or on the target commutes with a CNOT | the target blocks are and , which commute with |
| CNOTs sharing a control commute, and so do CNOTs sharing a target | XOR of one bit into two places, or of two bits into one place, is order-independent |
| swaps , exchanging the roles of control and target | |
| is symmetric | |
| three XORs | |
| CNOTs that meet head-to-tail do not commute: reordering them creates a third |
A error hits the target just before a CNOT. What error is present just after it?
- on the target only
- on the control only
- on both qubits
- on both qubits
Show the answer
C. on both qubits
: 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
The maximally entangled state of two -dimensional systems.
Expand .
The same coefficients: a gate on one half of can slide to the other half, transposed.
The Choi state determines : the fidelity is 1 iff . 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 on its partner, before everything else.
Slide from a system qubit across onto its reference partner. Which gate appears on the reference?
Show the answer
C.
The partner receives the transpose. is real, so . By contrast, and 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 rotations, every acts on a wire that holds some parity of the region's inputs, and up to a global phase the region acts as
where is an invertible linear map over . Two rotations on the same parity merge into one wherever they sit in the region. This rotation merging is the engine of -count and -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 - and -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 -count reductions.
Think first In a CNOT+ region, can two gates on different wires merge into a single ?
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
Normalize first: the criterion is stated for , and .
SWAP is real and symmetric, and it commutes with the symmetric operator .
is quadratic in . The trace is not real, so two CNOTs cannot suffice and SWAP needs exactly three. (The other normalizations, with odd, give : 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 reduces to checking , 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 and , and swaps , which reverses CNOTs and turns them into CZs.
- The ricochet identity makes Choi states a one-shot test of operator identities.
- In CNOT+ 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.
Which Pauli equals , with control qubit 0?
Show the answer
B.
The CNOT maps , so the sign read on the target in the middle equals in terms of the input bits: that is . A on the target propagates to the control.
Which pair of CNOTs does not commute?
- and
- and
- and
- and
Show the answer
C. and
They meet head-to-tail: qubit 1 is the first one's target and the second one's control. Reordering them creates an extra .
For one finds . What does the criterion say?
- One CNOT: and
- No CNOT is needed
- Three CNOTs are needed
- The criterion does not apply to a CNOT
Show the answer
A. One CNOT: and
and : exactly the one-CNOT condition, as it must be for a CNOT itself.
What is ?
- SWAP
Show the answer
D.
Write . Conjugating by swaps on both qubits, giving .
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).