quantum gate directory

The multi-controlled $X$ gate extends the family $X$ → CNOT → Toffoli to $n$ controls:

$$ \mathrm{C}^nX \, |c_1 \cdots c_n\rangle |t\rangle = |c_1 \cdots c_n\rangle |t \oplus c_1 c_2 \cdots c_n\rangle $$

As a matrix it is the identity, except for a $2 \times 2$ $X$ block on the last two basis states $|1{\cdots}10\rangle$ and $|1{\cdots}11\rangle$.

Properties

• Hermitian, self-inverse, and a permutation matrix (hence orthogonal).
• Computes the logical AND of all controls into the target — the quantum analog of an $n$-input AND gate, made reversible.
• Conjugating the target with Hadamards gives the multi-controlled $Z$, which is symmetric under any permutation of its qubits.

Decompositions

Cost grows with how many ancillas you can spare (counts from Barenco et al.):

• With $n - 2$ clean ancillas: a ladder of $2(n-2) + 1$ Toffolis (or Margolus gates, if compute–uncompute phase cancellation applies).
• With a single borrowed ancilla: still linear in $n$, via splitting into two half-sized MCX gates.
• With no ancillas: quadratic in $n$ — ancilla-free is expensive.

Usage

• The workhorse of oracle construction: any classical Boolean function built from AND/NOT logic compiles to MCX gates, which is how oracles and the Grover diffuser are realized in practice.