Multi-Controlled X Gate (MCX)

Flips a target qubit only when every one of several control qubits is set, the multi-input generalization of CNOT and Toffoli.

Definition

The multi-controlled X gate, MCX or C^nX, applies an X to the target if and only if all n control qubits are in state |1⟩. For n = 1 it is CNOT; for n = 2 it is the Toffoli (CCX); for n = 3 it is CCCX. It is the quantum analogue of a many-input logical AND driving a NOT.

Cost and ancillas

A C^nX with no borrowed workspace requires a number of two-qubit gates that grows with n. With one clean ancilla the count is linear in n; without ancillas the best known constructions still scale roughly linearly but with larger constants. Barenco et al. gave the classic recursive bounds still used by compilers.

V-and-V-dagger recursion

The core trick: pick V with V² = X (so V = √X). Then C^nX is built from a controlled-V, a C^{n-1}X, a controlled-V†, another C^{n-1}X, and a controlled-V. Unrolling the recursion trades control count for gate count. See controlled-U.

# Qiskit-style relative sizes
# C^nX with n-1 clean ancillas: ~ (n-1) Toffolis + 1
# using the 'v-chain' construction
from math import inf
def toffoli_count(n, ancillas):
    if ancillas >= n-1:
        return 2*(n-1)-1  # v-chain, roughly
    return None  # ancilla-free is costlier

Uses

MCX gates implement multi-bit boolean conditions in Grover oracles and in arithmetic circuits, where a carry or a comparison must fire only when a whole pattern of control bits holds. Reversible-logic synthesis compiles classical AND/OR networks into cascades of MCX.

See C3X and C4X for the small fixed-arity cases and their standard decompositions.