C3X and C4X Gates
The three- and four-control NOT gates, the small fixed cases of the multi-controlled X most often synthesized directly.
Definition
C3X (CCCX) flips the target when three controls are all |1⟩; C4X flips it when four controls are all set. They sit between the Toffoli (two controls) and general multi-controlled X, and are common enough that compilers ship hand-optimized templates for them.
Truth behavior
| c1 | c2 | c3 | t_in | t_out |
|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 |
The target only changes on the top two rows, where all three controls are one; every other control pattern leaves the target untouched.
Decomposition strategies
With one clean ancilla, C3X = two Toffolis compute the AND of the first two controls into the ancilla, a Toffoli combines that with the third control onto the target, then the first Toffolis are uncomputed. This uses a handful of Toffolis, each itself six CNOTs plus single-qubit gates.
Ancilla-free C3X and C4X use the √X and ⁴√X relative-phase recursion of Barenco. Relative-phase (dirty) variants that permit an extra phase on unused computational states are cheaper and are safe when the gate is uncomputed later — the Margolus gate is the two-control example.
# clean-ancilla C3X sketch
# ccx(c1,c2,anc); ccx(anc,c3,target); ccx(c1,c2,anc) # uncompute
def c3x_toffoli_budget():
return {'toffolis': 3, 'ancillas': 1}Uses
C3X and C4X appear in Grover oracles that test three or four condition bits at once and in modular arithmetic where several carry bits gate a flip. In amplitude-amplification diffusion operators, a multi-control-Z (obtained from C^nX conjugated by Hadamards on the target) marks the all-ones state.
See multi-controlled X for the general-n scaling and Margolus gate for the relative-phase trick.