Multi-Controlled Gates and Their Decompositions

A controlled- $U$ gate is the smallest conditional in the quantum circuit model: it fires a unitary on a target only when one control reads $|1\rangle$ . A multi-controlled gate raises the bar — $C^nU$ acts as the identity on the whole $2^{n+1}$ -dimensional space except on the single sector where all $n$ controls are $|1\rangle$ , where it applies $U$ to the target. In the computational basis it is block-diagonal: the identity on every control string but the all-ones one, which carries $U$ . This is the natural language of conditional logic — "do $U$ only if every one of these predicates holds" — and it is how oracles, arithmetic carries, and the Grover reflection are written down. But no hardware executes $C^nU$ for $n\ge 1$ natively; a backend offers one- and two-qubit gates and nothing more. The entire subject is therefore a compilation problem: how to build a high-fanin conditional out of a fixed universal set of CNOTs and single-qubit rotations, and how cheaply. The answer has three moving parts, and they organize everything below. First, the algebra: a doubly-controlled $U$ splits into single-controlled square roots $V$ and $V^\dagger$ with $V^2=U$ , which interfere so that two controls behave like a logical AND. Second, the recursion: that same interference pattern, applied with multi-controls in place of single controls, reduces $C^nU$ to smaller multi-controlled gates. Third, and decisively, the space–time tradeoff: the gate count of a multi-controlled NOT depends almost entirely on the ancilla budget — clean scratch qubits buy a linear circuit, a single borrowed qubit still buys linear, and zero scratch forces quadratic. The reference for all of it is Barenco et al. (1995), which proved two-qubit gates universal and gave the sharp ancilla–gate tradeoffs a fault-tolerant compiler still uses.

Key takeaways

A multi-controlled gate $C^nU$ applies $U$ to a target only when all $n$ controls are $|1\rangle$ , leaving every other basis state untouched; the smallest nontrivial case is the Toffoli, $C^2X$ .
Any $C^nU$ can be built from CNOTs and single-qubit gates alone — but the cost is governed by the ancilla budget, not by $U$ .
The square-root identity $V^2=U$ turns a doubly-controlled $U$ into single-controlled $V$ , $V^\dagger$ and a CNOT between the controls, whose interference encodes the logical AND.
With $n-1$ clean ancillas, $C^nX$ costs $2(n-1)$ Toffolis (a compute–fire–uncompute AND ladder); with one borrowed dirty ancilla it is still $O(n)$ ; with none it is $O(n^2)$ (Barenco et al.).
Controlling on $|0\rangle$ instead of $|1\rangle$ is free — sandwich that wire between two $X$ gates — so the whole theory needs only the all-ones case.
These primitives are the guts of the Grover diffusion operator, modular arithmetic in Shor's algorithm, reversible oracle synthesis, and the Fredkin controlled-SWAP.
Key idea: every multi-controlled gate is built by recursion on the number of controls — a control on $U$ splits via $U=V^2$ into interfering controls on $V$ and $V^\dagger$ , and a high-fanin control collapses to a chain of Toffolis that compute the AND of the controls into ancillas; the gate cost is set by the ancilla budget, not by $U$ .

The core insight

Every multi-controlled gate is built by recursion on the number of controls: a control on $U$ splits using $U=V^2$ into controls on $V$ and $V^\dagger$ that interfere as a logical AND, and a high-fanin control collapses to a chain of Toffolis that compute the AND of the controls into ancillas. The gate cost is governed by the ancilla budget, not by $U$ itself.

Where this lives today

Multi-controlled gates are the connective tissue of every serious quantum algorithm, and their compilation is an active optimization frontier. In Grover's search the diffusion operator is a multi-controlled- $Z$ on all qubits, so each of the roughly $\sqrt{N}$ iterations pays for one $C^{n-1}Z$ ; the choice of ancilla budget for that gate sets the circuit's width-versus-depth balance. In Shor's algorithm the modular-exponentiation core — the dominant cost of fault-tolerant factoring — is assembled from controlled adders and comparators, each a nest of multi-controlled gates, and Gidney and Ekerå's 2021 estimate for breaking 2048-bit RSA is dominated by roughly $3\times10^{9}$ Toffolis, every one of which is a two-control gate compiled by exactly the constructions here. Reversible oracle synthesis lays down one multi-controlled- $X$ per satisfying assignment of a Boolean predicate, so SAT-style oracles and lookup tables are literally stacks of $C^kX$ gates. The Fredkin controlled-SWAP, a Toffoli flanked by CNOTs, powers the SWAP test that estimates state overlap $|\langle\psi|\phi\rangle|^2$ for fidelity and entanglement diagnostics. And because the non-Clifford cost dominates on a surface-code machine, cheaper multi-controls are a live research target: measured "temporary AND" constructions spend only four $T$ gates per Toffoli when the result will be uncomputed, borrowed-ancilla and catalytic schemes trade a spare qubit for depth, and layout-aware synthesis under lattice surgery shaves the cost of every high-fanin conditional in the machine.

The physical picture

Read a multi-controlled gate as a logical AND wired to an enable line: the target gate fires only when every control reads $1$ . There are two ways to realize that AND from two-qubit pieces, and both are the whole subject. The first is interference. If $V$ is a square root of $U$ , so $V^2=U$ , then a $V$ and a $V^\dagger$ placed on the target and toggled by a CNOT between the two controls arrange themselves so that both controls set apply $V\cdot V=U$ , exactly one set applies $V\cdot V^\dagger=I$ , and neither set does nothing. The controls never touch the target directly; they interfere two half-turns into either a full turn or nothing. The first figure is this mechanism in full, with the four control settings tabulated.

Figure

The square-root construction of a doubly-controlled gate: with V² = U the two controls interfere a V and a V† on the target so that only the all-ones setting survives — control 11 applies V·V = U, either single control applies V·V† = I, and 00 does nothing. Taking V = √X (the square root of NOT) turns this circuit into a Toffoli

The second way to realize the AND is storage. Compute the conjunction of the controls step by step into a scratch (ancilla) qubit with a ladder of Toffoli gates — $a_1=c_1\wedge c_2$ , then $a_2=a_1\wedge c_3$ , and so on — use the last scratch qubit as one ordinary control on the target, then run the ladder backward to erase every scratch qubit to $|0\rangle$ . Bennett's uncomputation principle guarantees the ancillas come back clean and disentangled, so they factor out and the controls are undisturbed. This trades qubits for gates: with enough clean scratch the whole thing is linear in $n$ ; with none you must fall back on nested square roots and pay quadratically. The second figure is the object a compiler actually costs — the ancilla ladder and the three scaling regimes it lives in.

Figure

The ancilla budget sets the cost of an n-control NOT. With n−1 clean ancillas the AND ladder computes the conjunction upward, fires the target once, and uncomputes downward — 2(n−1) Toffolis total; for n = 5 that is 4 ancillas and 8 Toffolis ≈ 56 T gates. One borrowed dirty ancilla still buys O(n); zero ancillas force the O(n²) square-root recursion

Finally, conditioning on $|0\rangle$ instead of $|1\rangle$ costs nothing: since $X|0\rangle=|1\rangle$ , sandwiching that control wire between two $X$ gates converts a zero-control into a standard one-control, adding no two-qubit gates and no ancillas. The whole theory therefore needs only the all-ones-controlled case, and everything else is a change of basis on the control wires.

The core equations

A multi-controlled gate is defined by what it does on each control string: nothing, unless the string is all ones, in which case the target sees $U$ . Written with projectors onto the control register, this is a sum that is the identity on every sector but one.

C^nU = \sum_{x\in\{0,1\}^n} |x\rangle\langle x|\otimes U^{\,[x=1^n]} = \Big(I - |1^n\rangle\langle 1^n|\Big)\otimes I \;+\; |1^n\rangle\langle 1^n|\otimes U \qquad (1)

where: $n$ — number of control qubits; $|x\rangle\langle x|$ — projector onto the control bitstring $x$ ; $1^n$ — the all-ones string; $[\,\cdot\,]$ — the Iverson bracket, equal to $1$ when the condition holds and $0$ otherwise; $U$ — the single- (or multi-) qubit target unitary. Reading: the operator is block-diagonal in the control basis — the identity on the $2^{n+1}-2$ -dimensional complement, and $U$ on the two states $|1^n\rangle|0\rangle,\,|1^n\rangle|1\rangle$ . The smallest nontrivial case, $n=2$ and $U=X$ , is the Toffoli gate, the reversible AND that anchors the whole recursion. It writes the conjunction of the controls onto the target, modulo 2.

C^2X\,|a,b,c\rangle = |a,\,b,\,c\oplus(a\wedge b)\rangle \qquad (2)

where: $a,b$ — control-qubit values in $\{0,1\}$ ; $c$ — target-qubit value; $\oplus$ — addition modulo 2 (XOR); $\wedge$ — logical AND. Reading: the target flips exactly when both controls are set; fixing $c=0$ leaves $a\wedge b$ in the target, a reversible AND. The algebraic heart of single-target multi-control is the square-root identity: a doubly-controlled $U$ is built from single-controlled square roots and a CNOT between the controls, provided $V^2=U$ .

C^2U = (C_{2,3}V)\,(C_{1,2}X)\,(C_{2,3}V^\dagger)\,(C_{1,2}X)\,(C_{1,3}V),\qquad V^2=U \qquad (3)

where: $C_{i,j}V$ — the gate $V$ on qubit $j$ controlled by qubit $i$ ; $C_{1,2}X$ — CNOT from control 1 onto control 2; $V$ — a square root of $U$ , $V^2=U$ ; qubits $1,2$ are controls and $3$ is the target. Reading: read right-to-left — the inter-control CNOT toggles which of $V$ , $V^\dagger$ is live so that only the all-ones branch accumulates $V\cdot V=U$ . Reducing $C^2U$ to single controls needs one more ingredient: a single-controlled $U$ itself, from the Z-Y (ABC) decomposition of a one-qubit unitary. Any $U$ factors so that a CNOT-conjugated pair of rotations rebuilds it, with the global phase pushed onto the control.

U=e^{i\alpha}\,A\,X\,B\,X\,C,\quad ABC=I \;\Rightarrow\; C^1U=(\Phi(\alpha)\otimes A)\,C_{12}X\,(I\otimes B)\,C_{12}X\,(I\otimes C) \qquad (4)

where: $A,B,C$ — single-qubit unitaries with $ABC=I$ ; $\alpha$ — global phase of $U$ ; $\Phi(\alpha)=\mathrm{diag}(1,e^{i\alpha})$ — a phase gate on the control that absorbs the global phase. Reading: on control $0$ the target sees $ABC=I$ ; on control $1$ it sees $A X B X C=e^{-i\alpha}U$ , and $\Phi(\alpha)$ restores the phase. For a multi-controlled NOT with clean ancillas, the cost is a linear count of Toffolis: compute the AND upward, fire once, uncompute downward.

C^nX \;=\; \underbrace{2(n-1)\ \text{Toffolis}}_{\text{compute + uncompute}} \;+\; 1\ \text{CNOT},\qquad \text{ancillas } a_1\dots a_{n-1}\in|0\rangle \qquad (5)

where: $a_i$ — clean ancillas, all starting and ending in $|0\rangle$ ; the ladder computes $\bigwedge_i c_i$ into $a_{n-1}$ , fires the target, then reverses. Reading: $n-1$ Toffolis build the conjunction, one CNOT fires the target, and $n-1$ Toffolis erase the scratch — linear in $n$ . Without any scratch space the same reduction must be done by nested square roots, and the cost climbs to quadratic — the best general bound for an arbitrary target unitary.

C^nU_{\text{no anc}} = O(n^2)\ \text{elementary gates},\qquad C^nX_{\text{1 borrowed anc}} = O(n)\ \text{elementary gates} \qquad (6)

where: elementary — CNOT plus single-qubit gates; $O(n^2)$ — quadratic scaling with zero scratch; $O(n)$ — the linear cost restored by a single borrowed (dirty) ancilla. Reading: even one work qubit of unknown state, returned to that state at the end, collapses the quadratic back to linear (Barenco et al.). The Fredkin gate — the controlled-SWAP — shows how a controlled two-qubit operation reduces to a single Toffoli flanked by CNOTs, the template for turning any controlled permutation into multi-controlled NOTs.

\text{Fredkin} = C\text{-}\mathrm{SWAP} = (I\otimes C_{23}X)\,\big(C^2X_{\,1\to(2,3)}\big)\,(I\otimes C_{23}X) \qquad (7)

where: $C_{23}X$ — CNOT between the two swap targets; $C^2X_{1\to(2,3)}$ — a Toffoli with control $1$ and controls/target on qubits $2,3$ . Reading: the outer CNOTs express SWAP as three CNOTs, and controlling the middle one promotes it to a controlled-SWAP.

Derivation AThe square-root construction of a doubly-controlled gate

The goal is to prove the central identity of the whole subject — that a doubly-controlled unitary $C^2U$ is exactly the five-gate sequence of equation (3), built from single-controlled square roots $V,V^\dagger$ with $V^2=U$ and one CNOT between the controls — by tracking the operation applied to the target for each of the four control settings and showing it is $I$ on three of them and $U$ on the fourth. This is the base case of every multi-control recursion, so its correctness underwrites everything downstream. We read the circuit right-to-left, remembering that the inter-control CNOT changes which controlled- $V$ is active.

Step 1. Take both controls unset, $c_1=c_2=0$ . The first gate $C_{1,3}V$ is inactive (control 1 is $0$ ); the CNOTs are inactive (control 1 is $0$ ), so qubit 2 stays $0$ ; and both $C_{2,3}V^\dagger$ and $C_{2,3}V$ are inactive (control 2 is $0$ ). The target sees the identity. Why: with no control set, no controlled gate fires, and the circuit must reduce to $I$ — the trivial but necessary boundary.

Step 2. Take $c_1=1,c_2=0$ . Now $C_{1,3}V$ fires and applies $V$ to the target. The first CNOT flips qubit 2 to $1$ , so $C_{2,3}V^\dagger$ fires and applies $V^\dagger$ ; the second CNOT flips qubit 2 back to $0$ , so the final $C_{2,3}V$ is inactive. The target sees $V^\dagger V=I$ . Why: this is the interference at work — a lone control triggers exactly one $V$ and one $V^\dagger$ , which annihilate by unitarity regardless of what $V$ is.

Step 3. Take $c_1=0,c_2=1$ . Here $C_{1,3}V$ is inactive; the CNOTs are inactive (control 1 is $0$ ), so qubit 2 stays $1$ throughout; thus $C_{2,3}V^\dagger$ then $C_{2,3}V$ both fire, giving $V\cdot V^\dagger=I$ . Why: the symmetric single-control case, again cancelling to the identity — the two off-diagonal control settings are the ones the AND must reject.

Step 4. Take both controls set, $c_1=c_2=1$ . Now $C_{1,3}V$ applies $V$ . The first CNOT flips qubit 2 to $0$ , switching off $C_{2,3}V^\dagger$ ; the second CNOT flips qubit 2 back to $1$ , switching on the final $C_{2,3}V$ . The target sees $V\cdot V=V^2=U$ . Why: the all-ones branch is the only place two $V$ 's meet with no intervening $V^\dagger$ , so it is the only branch that accumulates $U$ — and $V^2=U$ is the sole constraint on $V$ . *Verified: the four settings give $I,I,I,U$ ; equivalent to multiplying the four $8\times8$ (or $2\times2$ block) factors, and matches Nielsen & Chuang §4.3, Fig. 4.8 and Barenco et al. (1995), Lemma 6.1.*

Go deeper · Derivation B · 2 minMulti-controlled NOT with a clean ancilla ladder

Derivation BMulti-controlled NOT with a clean ancilla ladder

The goal is to build $C^nX$ from $2(n-1)$ Toffoli gates using $n-1$ clean ancillas, and to prove that every ancilla returns to $|0\rangle$ so that the controls and target are left in exactly the state a native $C^nX$ would produce. The construction is a compute–fire–uncompute sandwich: it stores the running conjunction of the controls in the ancillas, uses the final ancilla as a single ordinary control on the target, and then reverses the storage step so no scratch information survives. This linear-in- $n$ circuit is the workhorse whenever qubits are plentiful, and it is why the Toffoli is the atom of multi-control.

Step 1. Compute the conjunction. Apply a Toffoli with controls $c_1,c_2$ and target $a_1$ , giving $a_1=c_1\wedge c_2$ ; then a Toffoli with controls $a_1,c_3$ and target $a_2$ , giving $a_2=c_1\wedge c_2\wedge c_3$ ; continue up to $a_{n-1}=\bigwedge_{i=1}^n c_i$ . This is $n-1$ Toffolis. Why: each Toffoli ANDs one more control into the running product, so after $n-1$ of them the last ancilla holds the full conjunction — the single bit that decides whether the target fires.

Step 2. Fire the target. Apply one CNOT with control $a_{n-1}$ and target $t$ , flipping $t$ exactly when $a_{n-1}=1$ , i.e. when all controls are set. Why: the whole point of computing the AND into a scratch qubit was to reduce an $n$ -fold control to a single control, which one CNOT can act on.

Step 3. Uncompute. Apply the same $n-1$ Toffolis of Step 1 in reverse order. Because each Toffoli is its own inverse, this drives $a_{n-1},\dots,a_1$ back to $|0\rangle$ , leaving no entanglement between the ancillas and the data. Why: Bennett's uncomputation principle — reversing the compute step disentangles the scratch so it factors out cleanly and can be reused, which is exactly what "clean ancilla" means.

Step 4. Count and confirm. The tally is $2(n-1)$ Toffolis plus one CNOT, with $n-1$ ancillas, and the ancillas begin and end in $|0\rangle$ for every control input, so they contribute a trivial tensor factor. The net action on controls and target is precisely $C^nX$ . Why: the resource count $2(n-1)$ is linear in $n$ , the best possible scaling, and the ancilla-reset check is what guarantees the circuit is a genuine $C^nX$ and not merely one that agrees on a subspace. *Verified: ancillas return to $|0\rangle$ for all $2^n$ control inputs and the target flips iff the control string is $1^n$ ; count $2(n-1)$ matches Barenco et al. (1995), Lemma 7.2.*

Go deeper · Derivation C · 2 minThe ancilla-free recursion and its quadratic cost

Derivation CThe ancilla-free recursion and its quadratic cost

The goal is to derive the recursion that builds $C^nU$ from smaller multi-controlled gates with no scratch qubits at all, and to show the resulting gate count is $\Theta(n^2)$ — the price of zero ancillas. The idea is to apply the square-root pattern of equation (3) but with the two single controls replaced by an $(n-1)$ -fold control and a single control, so that the recursion peels one control off at a time. Each peel costs a smaller multi-controlled NOT, and summing those linear-per-level costs over $n$ levels produces the quadratic bound that Barenco et al. proved optimal for a general target without work qubits.

Step 1. Split the controls. Choose $V$ with $V^2=U$ and write, in exact analogy with the doubly-controlled identity, $C^nU=(C^1_nV)\,(C^{n-1}_{1\dots n-1}X)\,(C^1_nV^\dagger)\,(C^{n-1}_{1\dots n-1}X)\,(C^{n-1}_{1\dots n-1}V)$ , where qubit $n$ plays the role of the second control and qubits $1\dots n-1$ the first. Why: the same interference argument as the base case shows the target sees $V\cdot V=U$ only when qubit $n$ and all of $1\dots n-1$ are set, so this is a correct $C^nU$ .

Step 2. Identify the pieces. The two single-controlled gates $C^1_nV$ and $C^1_nV^\dagger$ cost a constant number of elementary gates each (via the ABC decomposition of equation (4)); the two $C^{n-1}X$ gates and the one $C^{n-1}V$ are strictly smaller multi-controlled gates that recurse. Why: peeling one control off has reduced an $n$ -control problem to $(n-1)$ -control problems plus constant overhead, which is the signature of a linear recursion depth.

Step 3. Write the recurrence. Let $T(n)$ be the elementary-gate cost of $C^nU$ . Then

T(n) = 2\,T_{C^{n-1}X} + T(n-1) + O(1),\qquad T_{C^{n-1}X}=O(n)

because an ancilla-free $C^{n-1}X$ is itself linear-cost at each level of the outer recursion. Why: the multi-controlled NOTs, unlike the general $C^{n-1}V$ , admit a cheaper ancilla-free treatment, so the dominant per-level cost is the $O(n)$ from the two $C^{n-1}X$ gates.

Step 4. Solve. Summing an $O(n)$ per-level cost over the $n$ levels of the recursion gives $T(n)=\sum_{k=1}^{n}O(k)=\Theta(n^2)$ . Adding even one clean or borrowed ancilla short-circuits this by replacing the nested square roots with the linear AND ladder of the previous derivation. Why: the quadratic is entirely a consequence of having no place to store the running conjunction; storage is what turns $\Theta(n^2)$ into $O(n)$ , which is the whole moral of the ancilla budget. *Verified: the all-ones setting yields $V\cdot V=U$ and every other setting yields $V\cdot V^\dagger=I$ inductively; the $\Theta(n^2)$ ancilla-free and $O(n)$ single-ancilla scalings are Barenco et al. (1995), Lemma 7.5 and Corollary 7.4.*

Limiting cases

The cost of a multi-controlled NOT is not one number but a spectrum set by how much scratch space you are willing to spend.

Case	Result	Meaning
$n=1$	$C^1U$ constant cost	A single controlled- $U$ from the ABC decomposition — the base of the recursion, a fixed handful of CNOTs and rotations.
$n=2$ , $U=X$	Toffoli, $6$ CNOTs $+\ 7\,T$	The reversible AND; exact ancilla-free compilation costs six CNOTs and seven non-Clifford $T$ gates.
$n-1$ clean ancillas	$\mathrm{cost}=2(n-1)$ Toffolis	The linear AND ladder; ancillas returned to $\|0\rangle$ . Lowest gate count, highest qubit count.
$1$ borrowed dirty ancilla	$\mathrm{cost}=O(n)$ elementary	A single unknown-state work qubit, restored at the end, still buys linear cost (Barenco Cor. 7.4).
No ancilla	$\mathrm{cost}=O(n^2)$ elementary	Nested square-root recursion; $\Theta(n^2)$ is the best general scaling for arbitrary $U$ with zero scratch.

Common trapThe square-root trick gives every multi-controlled gate a cheap linear decomposition

It does not. The identity $V^2=U$ solves $C^2U$ for a single-qubit $U$ in a constant number of gates, and it is tempting to assume the recursion inherits that cheapness. But with no ancillas the recursion nests square roots inside square roots, and the honest count is $O(n^2)$ elementary gates, not $O(n)$ — the linear cost only appears once you can store the running conjunction in scratch qubits. Two further traps live here. First, forgetting to uncompute a borrowed ancilla leaves it entangled with the control register, so tracing it out puts the data into a mixed state and silently corrupts interference — the ancilla must be returned to its exact initial state, known or not. Second, a "relative-phase" multi-control (the analogue of the three-CNOT Margolus Toffoli) reproduces the correct permutation but stamps an extra phase on some basis states; it is safe only when that phase is guaranteed to cancel, typically because the qubit it acts on is later uncomputed.

Worked examples

1 · Resource count for a five-control NOT (fully worked)

You need a $C^5X$ (five controls, one target) inside a Grover oracle. Cost it two ways: with clean ancillas, and note what changes with none. Assume the standard exact Toffoli of seven $T$ gates.

Step 1. Count ancillas. A clean AND ladder for $n=5$ controls needs $n-1=\mathbf{4}$ clean ancillas, each prepared in $|0\rangle$ and returned to $|0\rangle$ . These are scratch qubits the surrounding circuit must be able to spare.

Step 2. Count Toffolis. The ladder computes the conjunction with $n-1=4$ Toffolis, fires the target with one CNOT, and uncomputes with $4$ more Toffolis, for $2(n-1)=2\times4=\mathbf{8}$ Toffolis plus one CNOT. The CNOT is Clifford and essentially free in the fault-tolerant cost model.

Step 3. Convert to $T$ -count. Each exact Toffoli spends $7$ non-Clifford $T$ gates, so the $T$ -count is $8\times7=\mathbf{56}$ $T$ gates — 56 distilled magic states for one five-control NOT. This is the number a surface-code resource estimate actually pays.

Step 4. Compare with no ancillas. Strip the scratch and the same $C^5X$ must be built by the nested square-root recursion, whose cost is $O(n^2)$ elementary gates rather than $O(n)$ — a strictly worse scaling that grows quadratically as the control count rises. With 4 clean ancillas: 8 Toffolis ≈ 56 T gates, linear; with none: $O(n^2)$ , quadratic. The ancilla budget, not $X$ , decides the bill.

2 · A doubly-controlled phase gate from the square-root construction (fully worked)

Build the doubly-controlled phase gate $C^2S$ , where $S=\mathrm{diag}(1,i)$ , using the square-root identity. Find the square root $V$ , verify the four control cases, and state the net action on the computational basis.

Step 1. Find the square root. We need $V$ with $V^2=S$ . The $T$ gate is exactly this: $T=\mathrm{diag}(1,e^{i\pi/4})$ , so $T^2=\mathrm{diag}(1,e^{i\pi/2})=\mathrm{diag}(1,i)=S$ . Thus $\mathbf{V=T}$ , a native, cheap single-qubit gate — no compilation of an exotic root is needed.

Step 2. Write the circuit. Substituting $V=T$ into equation (3), $C^2S=(C_{2,3}T)\,(C_{1,2}X)\,(C_{2,3}T^\dagger)\,(C_{1,2}X)\,(C_{1,3}T)$ : two single-controlled $T$ 's, one controlled $T^\dagger$ , and two CNOTs between the controls. Every piece is a controlled phase, so this is a purely diagonal circuit.

Step 3. Verify the four cases. Both controls $0$ : identity. One control set: a $T$ and a $T^\dagger$ meet on the target and cancel, $T\cdot T^\dagger=I$ . Both controls set: the inter-control CNOT switches off the $T^\dagger$ , leaving $T\cdot T=T^2=S$ on the target. So $C^2S$ applies $S$ to the target only on the all-ones control setting. The four cases give $I,I,I,S$ — exactly $C^2S$ .

Step 4. State the net action. Since $S$ multiplies target- $|1\rangle$ by $i$ and fixes target- $|0\rangle$ , the whole gate multiplies the single basis state $|1,1,1\rangle$ by $i$ and leaves the other seven fixed: $C^2S=\mathrm{diag}(1,1,1,1,1,1,1,i)$ . A controlled-controlled phase built from three $T$ -type gates and two CNOTs — the same construction that, with $V=\sqrt X$ , gives the Toffoli.

3 · Turning a zero-control into a one-control

The Grover diffusion operator needs a phase flip on $|0\dots0\rangle$ — a multi-controlled gate that fires when every qubit is $0$ , the opposite of the standard convention. Show how to build it from an all-ones multi-controlled gate.

Step 1. State the target operation. The diffusion reflection $2|0^n\rangle\langle0^n|-I$ (up to Hadamard conjugation) is a $C^{n-1}Z$ that fires on $|0^n\rangle$ rather than $|1^n\rangle$ — every control is conditioned on $|0\rangle$ .

Step 2. Flip each control basis. Apply an $X$ gate to every control wire before the multi-controlled gate and another $X$ after. Since $X|0\rangle=|1\rangle$ , the pre- $X$ 's map the desired all-zeros condition onto the standard all-ones condition the hardware construction expects.

Step 3. Insert the standard gate. Between the two layers of $X$ 's, place the ordinary all-ones $C^{n-1}Z$ (itself a $C^{n-1}X$ conjugated by a Hadamard on the target). The post- $X$ 's undo the basis flip on the controls, restoring them.

Step 4. Count the overhead. The conversion added $2(n-1)$ single-qubit $X$ gates and no two-qubit gates and no ancillas. Conditioning on $|0\rangle$ is free up to single-qubit $X$ 's, so the all-ones construction covers every control polarity — which is why the theory only ever solves the all-ones case.

Physics of the portrait

Multi-controlled gates are where an abstract universality theorem became an engineering discipline, and the person who did most to make that happen is the physicist whose name is on the field's founding decomposition paper.

Origins · 1 minAdriano Barenco and how this was discovered

Adriano Barenco

active from the early 1990s, physicist at Oxford · elementary-gate decompositions and the universality of two-qubit gates

Adriano Barenco did his doctoral work at the University of Oxford in the early-to-mid 1990s, in the group around Artur Ekert and David Deutsch that turned quantum computation from a curiosity into a research program. His single-author 1995 paper "A universal two-bit gate for quantum computation" showed that almost any two-qubit gate is by itself universal — a sharp strengthening of the picture that had required special gate sets — and the family of general two-qubit gates he analysed is still called the Barenco gate. That same year he was the lead author of "Elementary gates for quantum computation" (Physical Review A 52, 3457), written with Bennett, Cleve, DiVincenzo, Margolus, Shor, Sleator, Smolin and Weinfurter, which became the standard reference for compiling arbitrary unitaries into CNOTs and single-qubit rotations. It is that paper that established the multi-control results this article rests on: the controlled- $V$ square-root construction, the ancilla-assisted linear $C^nX$ , the single-borrowed-ancilla linear bound, and the $\Theta(n^2)$ ancilla-free scaling. The work is quietly foundational — every quantum compiler, every fault-tolerant resource estimate that quotes a Toffoli or $T$ count, is downstream of the tradeoffs Barenco and his collaborators made explicit. A set of lemmas about counting gates turned out to be the bridge from "quantum computers are universal in principle" to "here is the circuit, and here is what it costs".

History

1980

— Toffoli proves the controlled-controlled-NOT universal for reversible classical logic

1985

— Deutsch formalizes the quantum Turing machine and quantum logic gates

1995

— Barenco et al. give elementary-gate decompositions with sharp ancilla–gate tradeoffs

1996

— Grover's search makes the multi-controlled phase flip a per-iteration workhorse

2013

— measured-uncomputation and borrowed-ancilla tricks cut multi-control gate counts further

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §4.3 (universal gates, controlled operations, Figs. 4.8–4.10) · Barenco, Bennett, Cleve, DiVincenzo, Margolus, Shor, Sleator, Smolin, Weinfurter, "Elementary gates for quantum computation", Phys. Rev. A 52, 3457 (1995) · Preskill, Lecture Notes for Physics 219, Ch. 5–6 · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, §8 · Watrous, The Theory of Quantum Information, Ch. 2 (unitary channels) · Mermin, Quantum Computer Science, Ch. 2.

Provenance. The definition and the block-diagonal form follow Nielsen & Chuang §4.3; the controlled- $V$ square-root identity, the ABC decomposition of $C^1U$ , the $2(n-1)$ -Toffoli clean-ancilla ladder, the single-borrowed-ancilla linear bound, and the $\Theta(n^2)$ ancilla-free scaling are all from Barenco et al. (Phys. Rev. A 52, 3457, 1995), Lemmas 6.1, 7.2, 7.5 and Corollary 7.4. A verifier should confirm: (1) the four-case evaluation of equation (3) gives $I,I,I,U$ ; (2) $T^2=S$ , so the Example-2 circuit yields $\mathrm{diag}(1,1,1,1,1,1,1,i)$ ; (3) the AND ladder resets all $n-1$ clean ancillas to $|0\rangle$ for every control input and flips the target iff the string is $1^n$ ; (4) the resource arithmetic $2(5-1)=8$ Toffolis $\to 8\times7=56$ $T$ gates. All stated counts (6 CNOTs and 7 $T$ for a Toffoli, $2(n-1)$ , $O(n)$ , $O(n^2)$ ) are standard textbook figures; the $3\times10^{9}$ -Toffoli factoring estimate is Gidney & Ekerå (2021).

Prerequisites. Controlled-U Gates · CNOT Gate · Phase Gates (S and T) · Z-Y Decomposition of Single-Qubit Gates · Circuit Identities and Equivalences. Leads to. Quantum Circuit Model · SWAP Gate · Controlled-Z Gate.

Ask the tutor: Ask me to trace the square-root construction gate by gate for a specific $U$ , or to compare the clean-ancilla, borrowed-ancilla, and ancilla-free circuits for a given control count and target.

Why is the ancilla budget, and not the target unitary U, what sets the gate count?

Because the hard part of a multi-controlled gate is the control logic — computing the AND of many controls — not the single application of $U$ . Applying $U$ once costs a fixed handful of gates via the ABC decomposition; what scales with $n$ is reducing an $n$ -fold control to a single control. If you have scratch qubits you store the running conjunction in them with a linear ladder of Toffolis, so the cost is $O(n)$ . If you have none, you must recreate that conjunction on the fly with nested square roots, and the same information costs $O(n^2)$ to marshal and unmarshal. The target $U$ enters only through the two constant-cost single-controlled $V$ 's, so it never changes the scaling — which is why the whole theory is phrased around the multi-controlled NOT.

What exactly is a "dirty" or borrowed ancilla, and why is it almost as good as a clean one?

A clean ancilla is a scratch qubit you are handed in a known state $|0\rangle$ and may leave in $|0\rangle$ . A dirty or borrowed ancilla is a qubit already in use elsewhere, in an unknown (possibly entangled) state, that you may use only if you return it to exactly that state when you are done. Barenco et al. showed that even a single borrowed qubit collapses the ancilla-free $O(n^2)$ cost of a multi-controlled NOT back to linear $O(n)$ , using a conjugation pattern whose forward and backward halves cancel any effect on the borrowed qubit regardless of its state. This matters enormously in practice: a large circuit almost always has some qubit idle for a moment, and borrowing it is free, whereas dedicating a fresh clean ancilla costs precious width. The one non-negotiable is the restoration — a borrowed qubit left perturbed corrupts whatever computation owns it.

Why must V be a square root of U, and what happens if I pick a different V?

The constraint comes entirely from the all-ones control setting. In the five-gate construction, every control setting except the all-ones one places a $V$ and a $V^\dagger$ on the target, which cancel to the identity by unitarity no matter what $V$ is — those branches are automatically correct. Only when both controls are set does the inter-control CNOT switch off the $V^\dagger$ , leaving two $V$ 's in a row, $V\cdot V=V^2$ , on the target. For that branch to apply the intended $U$ you need $V^2=U$ , and nothing else about $V$ is constrained. Pick a $V$ with $V^2\ne U$ and the three cancelling branches still work, but the all-ones branch applies the wrong operator, so the circuit is not $C^2U$ . The freedom in choosing among the several square roots of $U$ is sometimes exploited to pick a $V$ that is cheap to compile.

Is the Toffoli special, or just the n = 2 case of this whole story?

Both. Formally the Toffoli is exactly $C^2X$ , the smallest nontrivial multi-controlled gate, and the square-root construction with $V=\sqrt{X}$ produces it. But it is special in being the recursion's atom: the linear AND-ladder for $C^nX$ is built entirely from Toffolis, computing the conjunction one control at a time, so the whole linear-cost regime is "count the Toffolis". It is also special because it is non-Clifford — its exact compilation needs seven $T$ gates — which makes the Toffoli count the headline resource metric on a fault-tolerant machine. So the Toffoli is simultaneously a member of the family (the $n=2$ NOT) and the currency in which the rest of the family is priced.

How do multi-controlled gates connect to the Grover diffusion operator?

The Grover diffusion step is the reflection $2|s\rangle\langle s|-I$ about the uniform superposition, and conjugating by Hadamards and $X$ gates turns it into a conditional phase flip on a single basis state — a multi-controlled- $Z$ acting on all the qubits. That $C^{n-1}Z$ is just a $C^{n-1}X$ with a Hadamard sandwiching the target (since $HXH=Z$ ), so compiling the diffusion operator is compiling a multi-controlled NOT. Every Grover iteration pays for one such gate, so the ancilla budget you choose for it — clean ladder, borrowed qubit, or ancilla-free — directly sets the per-iteration depth and width of the search. It is a clean example of the whole subject in miniature: an abstract reflection becomes a concrete high-fanin conditional, and the cost is an ancilla-budget decision.

What is a relative-phase multi-controlled gate, and when is it safe to use?

A relative-phase multi-control reproduces the correct permutation of basis states — it fires the target on exactly the right control string — but attaches an extra phase to one or more basis states, so as a unitary it is not equal to the true multi-controlled gate. The prototype is the three-CNOT Margolus Toffoli, cheaper than the six-CNOT exact one but carrying a stray $-1$ on a single state. Such gates are safe precisely when that phase is guaranteed to cancel, which happens in the ubiquitous compute-then-uncompute pattern: you use the cheap gate to write a value into an ancilla, do some work, and later apply its inverse to erase the ancilla — the stray phase appears twice and squares to $+1$ . If instead you keep the output as a lasting part of the register, the extra phase changes the overall unitary and silently corrupts the computation. The saving is real, but it is bought against a promise you must actually keep.