CCZ (doubly-controlled Z) gate

Definition

$$\mathrm{CCZ}|a,b,c\rangle = (-1)^{a\wedge b\wedge c}\,|a,b,c\rangle$$

As an $8\times 8$ diagonal matrix, $\mathrm{CCZ} = \mathrm{diag}(1,1,1,1,1,1,1,-1)$ in the ordered basis $|000\rangle,\dots,|111\rangle$ — the identity everywhere except a sign flip on $|111\rangle$.

Action on basis states and symmetry

Only $|111\rangle$ picks up a phase; the other seven computational-basis states are completely unaffected. Because the matrix is symmetric under any permutation of the three qubits, $\mathrm{CCZ}$ has no distinguished "target" — unlike Toffoli, where swapping the target with a control changes the gate.

Decomposition

$$\mathrm{CCZ} = (I\otimes I\otimes H)\;\mathrm{CCX}\;(I\otimes I\otimes H)$$

exactly mirroring the two-qubit identity $\mathrm{CZ} = (I\otimes H)\,\mathrm{CX}\,(I\otimes H)$: conjugating the Toffoli's target by Hadamard converts its controlled bit-flip ($X$ on the control-11 block) into a controlled phase-flip ($HXH=Z$ on that same block), leaving the control-not-both-1 blocks at identity in both cases.

Key identities

• $\mathrm{CCZ}^2 = I^{\otimes 3}$: applying the same doubly-controlled phase twice restores the input.
• $\mathrm{CCZ}$ is non-Clifford, exactly like Toffoli: it inherits the same resource cost (6 CNOT + 2 H + 7 T-family gates, via the Toffoli decomposition sandwiched by the extra pair of target Hadamards, which cancel two of Toffoli's own Hadamards).
• $\mathrm{CCZ}$ is the natural building block for multi-controlled-phase oracles in amplitude amplification and Grover-style search, since its full symmetry across all three qubits makes larger $C^nZ$ constructions compose more uniformly than $C^nX$ ones.