Controlled-U Gates

Almost everything a quantum computer does that a classical one cannot comes from making an operation conditional on quantum information — and the controlled- $U$ gate is the primitive that does exactly this. Take any single-qubit unitary $U\in\mathrm{U}(2)$ , hand it a second qubit called the control, and $\mathrm{C}U$ runs $U$ on the target in the branch where the control reads $\lvert 1\rangle$ and leaves it alone in the $\lvert 0\rangle$ branch. Because the control can itself be in superposition, the two branches coexist and the result is generically entangled. This one construction contains CNOT ( $U=X$ ), controlled- $Z$ ( $U=Z$ ), the controlled phase rotations that build the quantum Fourier transform, and — stacked into multi-control form — the Toffoli gate and quantum oracles. The structure is deceptively simple: $\mathrm{C}U$ is block-diagonal in the control basis, an identity block above a copy of $U$ , and from that one fact everything follows. Feed the target an eigenstate of $U$ and the eigenvalue detaches from the target and reappears as a relative phase on the control — phase kickback, the engine of phase estimation, Shor's algorithm, and HHL. Ask how to build $\mathrm{C}U$ from hardware-native CNOTs and single-qubit rotations and the Z–Y decomposition answers with an exact two-CNOT circuit, while exposing a trap: the global phase of $U$ , invisible for a lone gate, becomes physically real the moment $U$ is controlled.

Key takeaways

A controlled- $U$ gate applies a single-qubit unitary $U$ to a target qubit only when the control is $\lvert 1\rangle$ , and does nothing when the control is $\lvert 0\rangle$ .
Its operator is block-diagonal, $\mathrm{C}U=\lvert 0\rangle\langle 0\rvert\otimes I+\lvert 1\rangle\langle 1\rvert\otimes U$ , which specializes to CNOT ( $U=X$ ), controlled- $Z$ ( $U=Z$ ) and controlled phase ( $U=R_z$ ).
On an eigenstate $U\lvert u\rangle=e^{i\theta}\lvert u\rangle$ the target is untouched and the eigenphase kicks back onto the control — the mechanism behind phase estimation.
Any $\mathrm{C}U$ compiles into exactly two CNOTs via the ABC identity $U=e^{i\alpha}AXBXC$ with $ABC=I$ , plus a phase gate $\mathrm{diag}(1,e^{i\alpha})$ on the control — and dropping that control-phase gate is the classic compilation bug.
Multi-controlled gates $\mathrm{C}^{n}U$ (Toffoli, oracles) are built recursively from two-qubit controlled gates using $V=\sqrt{U}$ .
Key idea: controlled- $U$ writes a single-qubit unitary into the $\lvert 1\rangle\langle 1\rvert$ block of a block-diagonal two-qubit operator, $\mathrm{C}U=\lvert 0\rangle\langle 0\rvert\otimes I+\lvert 1\rangle\langle 1\rvert\otimes U$ — phase kickback, the two-CNOT compilation, and multi-controlled gates all follow from this one structure.

The core insight

Controlled- $U$ writes a single-qubit unitary into the $\lvert 1\rangle\langle 1\rvert$ block of a block-diagonal two-qubit operator: $\mathrm{C}U=\lvert 0\rangle\langle 0\rvert\otimes I+\lvert 1\rangle\langle 1\rvert\otimes U$ . Everything else — phase kickback, the ABC compilation, and multi-controlled extensions — follows from this single structure.

Where this lives today

Controlled- $U$ is not a textbook idealization — it is what quantum hardware spends most of its time doing. Superconducting processors from IBM and Google expose a two-qubit entangler (a controlled- $Z$ , an echoed cross-resonance CNOT, or a tunable controlled-phase) plus single-qubit rotations, and every higher-level operation is transpiled into those primitives using exactly the two-CNOT ABC construction; IBM's native $\sqrt X$ gate is the $V$ of Worked Example 2, while trapped-ion and neutral-atom machines use Mølmer–Sørensen and Rydberg-blockade interactions. At the algorithm layer, controlled powers $\mathrm{C}U^{2^j}$ drive quantum phase estimation — the heart of Shor's factoring, HHL, and quantum-chemistry energy estimation — and the controlled rotations $\mathrm{C}R_k$ are the rungs of every quantum Fourier transform. Fault-tolerant architectures spend heavily synthesizing controlled non-Clifford gates by distilling magic states, and open problems stay sharp: optimal CNOT- and $T$ -count synthesis of a given $\mathrm{C}U$ , and efficient block-encoding of controlled unitaries for qubitization — refinements of the primitive introduced here.

The physical picture

Picture the control qubit as a quantum switch wired to the target: "off" applies the identity $I$ , "on" applies $U$ . What makes it quantum is that the switch itself can be placed in superposition. When the control is $\tfrac{1}{\sqrt2}(\lvert 0\rangle+\lvert 1\rangle)$ , both settings fire at once into orthogonal branches and the gate produces $\tfrac{1}{\sqrt2}(\lvert 0\rangle\lvert\psi\rangle+\lvert 1\rangle U\lvert\psi\rangle)$ — a coherent superposition of "did nothing" and "applied $U$ ." That output is entangled unless $U\lvert\psi\rangle\propto\lvert\psi\rangle$ , which is why the controlled gate is the workhorse for making entanglement. The first figure fixes this switch picture together with the block-diagonal operator it produces.

Figure

Controlled-U as a quantum switch: the control-0 branch runs the identity I, the control-1 branch runs U, so the operator is block-diagonal with I above U — and a control in superposition entangles the two branches into the output shown, where CU equals P₀ ⊗ I + P₁ ⊗ U with P₀, P₁ the control projectors

Now suppose the target starts in an eigenstate of $U$ , say $U\lvert u\rangle=e^{i\theta}\lvert u\rangle$ . The gate cannot change $\lvert u\rangle$ — it may only multiply it by $e^{i\theta}$ — but that scalar sits in front of the $\lvert 1\rangle$ branch only, giving $(\alpha\lvert 0\rangle+e^{i\theta}\beta\lvert 1\rangle)\lvert u\rangle$ : the target is untouched while the eigenphase migrates onto the control. This "phase kickback" lets a quantum computer read out a property of $U$ by measuring the control, and the second figure carries it through with real numbers, using $U=T$ (whose $\lvert 1\rangle$ eigenvalue is $e^{i\pi/4}$ ) to turn a hidden eigenphase into a concrete pair of measurement probabilities.

Figure

Phase kickback with numbers: control in the plus state, target in the T-eigenstate; controlled-T stamps e^(iπ/4) onto the control, then a Hadamard converts that relative phase into measurement probabilities cos²(π/8) = 0.854 and sin²(π/8) = 0.146, reading off the eigenphase φ = 1/8

The core equations

The definition is a single operator, written with the control qubit first. Two orthogonal projectors on the control select which single-qubit operation the target sees: the identity in one branch, $U$ in the other — and every property of the gate is a corollary of this one line.

\mathrm{C}U=\lvert 0\rangle\langle 0\rvert\otimes I+\lvert 1\rangle\langle 1\rvert\otimes U \qquad (1)

where: $\lvert 0\rangle\langle 0\rvert,\ \lvert 1\rangle\langle 1\rvert$ are the projectors onto the control basis states; $I$ is the $2\times2$ identity on the target; $U$ is any single-qubit unitary with $U^\dagger U=I$ . Reading it: the control chooses the block, the target lives inside the chosen block. Ordering the two-qubit basis as $\{\lvert 00\rangle,\lvert 01\rangle,\lvert 10\rangle,\lvert 11\rangle\}$ with the control most significant, equation (1) becomes a $4\times4$ block-diagonal matrix — a $2\times2$ identity in the top-left, the matrix of $U$ in the bottom-right, zeros off the blocks.

\mathrm{C}U=\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & u_{00} & u_{01}\\ 0 & 0 & u_{10} & u_{11}\end{pmatrix} \qquad (2)

where: $u_{ij}$ are the matrix elements of $U=\sum_{ij}u_{ij}\lvert i\rangle\langle j\rvert$ . The upper block never touches the lower block, so unitarity of $\mathrm{C}U$ is exactly unitarity of $U$ . Acting on a control in superposition, linearity distributes the gate over the two branches — the equation that makes controlled gates entangling rather than merely conditional.

\mathrm{C}U\,(\alpha\lvert 0\rangle+\beta\lvert 1\rangle)\otimes\lvert\psi\rangle=\alpha\lvert 0\rangle\lvert\psi\rangle+\beta\lvert 1\rangle\,U\lvert\psi\rangle \qquad (3)

where: $\alpha,\beta$ are the control amplitudes with $\lvert\alpha\rvert^2+\lvert\beta\rvert^2=1$ , and $\lvert\psi\rangle$ is any target state. The output factorizes only when $U\lvert\psi\rangle\propto\lvert\psi\rangle$ ; otherwise the two qubits are entangled. When the target is an eigenstate of $U$ , it survives untouched and the eigenvalue attaches to the $\lvert 1\rangle$ amplitude of the control — phase kickback stated as an identity.

U\lvert u\rangle=e^{i\theta}\lvert u\rangle\ \Rightarrow\ \mathrm{C}U\,(\alpha\lvert 0\rangle+\beta\lvert 1\rangle)\lvert u\rangle=(\alpha\lvert 0\rangle+e^{i\theta}\beta\lvert 1\rangle)\lvert u\rangle \qquad (4)

where: $\lvert u\rangle$ is an eigenstate of $U$ and $e^{i\theta}$ its unit-modulus eigenvalue. A property of the target ( $\theta$ ) has become a relative phase of the control, ready to be read by interference. To build $\mathrm{C}U$ from a hardware gate set, start from the Z–Y decomposition $U=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)$ and repackage it: choose $A,B,C$ whose product is the identity but between which a Pauli- $X$ reconstructs $U$ .

U=e^{i\alpha}\,A\,X\,B\,X\,C,\qquad ABC=I \qquad (5)

where: $A,B,C$ are single-qubit gates assembled from $z$ - and $y$ -rotations, $e^{i\alpha}$ is the global phase of $U$ , and each $X$ is supplied by a CNOT's target action. Control off gives $ABC=I$ (target untouched); control on inserts the two $X$ 's and yields $U$ . Turning equation (5) into a circuit, each $X$ is realized by a CNOT sharing the control, and the leftover $e^{i\alpha}$ is applied as a phase gate on the control — because a global phase becomes a relative phase between branches.

\mathrm{C}U=\big(\Phi(\alpha)\otimes I\big)(I\otimes A)\,\mathrm{C}X\,(I\otimes B)\,\mathrm{C}X\,(I\otimes C) \qquad (6)

where: $\Phi(\alpha)=\mathrm{diag}(1,e^{i\alpha})$ acts on the control and $\mathrm{C}X$ is a CNOT with the same control and the working target. Two CNOTs, three single-qubit gates, and one control-phase gate reproduce any $\mathrm{C}U$ exactly.

Derivation AWhy controlled-U is block-diagonal and unitary

The goal is to derive the matrix form (2) directly from the operator definition (1), so the block structure is a computed consequence rather than an assertion, and then to read off unitarity for free. We fix a basis ordering, evaluate the four control blocks one by one using the orthogonality of the control projectors, and check that the matrix times its adjoint is the identity exactly when $U$ is unitary — showing why controlling a unitary can never break unitarity.

Step 1. Order the computational basis as $\lvert c\rangle\lvert t\rangle$ with the control $c$ most significant, giving $\lvert 00\rangle,\lvert 01\rangle,\lvert 10\rangle,\lvert 11\rangle$ . Why: the block structure only looks block-diagonal in this ordering; putting the target first would interleave the entries and hide it.

Step 2. Evaluate the control- $0$ block: $\langle 0\rvert\langle t'\rvert\,\mathrm{C}U\,\lvert 0\rangle\lvert t\rangle=\langle t'\rvert I\lvert t\rangle=\delta_{t't}$ , because $\lvert 0\rangle\langle 0\rvert$ projects onto the first term of (1) and kills the second. Why: this is the mathematical statement that "control off does nothing" — the upper-left $2\times2$ block is the identity.

Step 3. Evaluate the control- $1$ block: $\langle 1\rvert\langle t'\rvert\,\mathrm{C}U\,\lvert 1\rangle\lvert t\rangle=\langle t'\rvert U\lvert t\rangle=u_{t't}$ , and the two cross blocks vanish since $\langle 0\vert 1\rangle=0$ . Why: the lower-right block is exactly $U$ , and orthogonal control projectors guarantee the off-diagonal blocks are strictly zero.

Step 4. Assemble the results into matrix (2) and form $\mathrm{C}U^\dagger\,\mathrm{C}U$ ; the block-diagonal product is $\mathrm{diag}(I,\ U^\dagger U)=\mathrm{diag}(I,I)$ . Why: unitarity of $\mathrm{C}U$ reduces to unitarity of $U$ — controlling a valid gate always yields a valid gate. *The block-diagonal matrix follows directly from the $\{00,01,10,11\}$ ordering and the orthogonality of the control projectors; $\mathrm{C}U^\dagger\mathrm{C}U=I\Leftrightarrow U^\dagger U=I$ by direct block multiplication.*

Go deeper · Derivation B · 1 minCompiling controlled-U into two CNOTs and a control-phase gate

Derivation BCompiling controlled-U into two CNOTs and a control-phase gate

The goal is to build an explicit circuit for $\mathrm{C}U$ using only CNOTs, single-qubit rotations, and one phase gate — the compilation every real quantum computer must perform, since no hardware executes an arbitrary $\mathrm{C}U$ directly. Starting from the Z–Y decomposition of $U$ , we manufacture three single-qubit gates $A,B,C$ whose product is the identity yet whose $X$ -conjugated combination rebuilds $U$ , then restore the global phase as a control-phase gate — tracking the two branches separately proves the circuit exact and shows why the global phase, harmless for a lone $U$ , must be re-inserted.

Step 1. By the Z–Y decomposition write $U=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)$ and define $A=R_z(\beta)R_y(\gamma/2)$ , $B=R_y(-\gamma/2)R_z(-(\delta+\beta)/2)$ , $C=R_z((\delta-\beta)/2)$ . Why: these splits are engineered so the $y$ - and $z$ -angles cancel in one combination and reinforce in the other — the whole construction hinges on this bookkeeping.

Step 2. Verify the control-off branch: $ABC=R_z(\beta)R_y(\tfrac{\gamma}{2})R_y(-\tfrac{\gamma}{2})R_z(-\tfrac{\delta+\beta}{2})R_z(\tfrac{\delta-\beta}{2})=R_z(\beta)R_z(-\beta)=I$ . Why: the $y$ -rotations cancel and the $z$ -angles sum to $-\beta$ , so with no CNOTs firing the $\lvert 0\rangle$ branch is the identity.

Step 3. Verify the control-on branch using $XR_y(\phi)X=R_y(-\phi)$ and $XR_z(\phi)X=R_z(-\phi)$ : the two $X$ 's flip the signs of $B$ 's angles, and $A(XBX)C=R_z(\beta)R_y(\gamma)R_z(\delta)=e^{-i\alpha}U$ . Why: conjugating $B$ by $X$ converts the cancelling combination into the reinforcing one, rebuilding the $SU(2)$ part of $U$ ; each $X$ comes from a CNOT whose control is on.

Step 4. Restore the global phase: since the reconstruction gives $e^{-i\alpha}U$ , apply $\Phi(\alpha)=\mathrm{diag}(1,e^{i\alpha})$ on the control, contributing $e^{i\alpha}$ only in the $\lvert 1\rangle$ branch. Why: for a lone $U$ the factor $e^{i\alpha}$ is unobservable, but here it multiplies one branch and not the other — omitting this gate is the most common controlled- $U$ compilation error. *For a random $U\in\mathrm{U}(2)$ , $ABC=I$ and $e^{i\alpha}AXBXC=U$ hold to machine precision; two CNOTs is optimal for a generic $U$ .*

Go deeper · Derivation C · 1 minPhase kickback: turning an eigenvalue into a control phase

Derivation CPhase kickback: turning an eigenvalue into a control phase

The goal is to show that controlling a unitary on one of its eigenstates transfers the eigenphase onto the control while leaving the target physically unchanged — the exact mechanism quantum phase estimation, Shor's algorithm, and amplitude estimation all exploit. We prepare the control in an equal superposition and the target in an eigenstate, apply the defining operator branch-by-branch, and watch the eigenvalue factor out onto the control; a final Hadamard turns that phase into a measurable bit, so the target does real work while never actually changing.

Step 1. Prepare the control in $\lvert +\rangle=\tfrac{1}{\sqrt2}(\lvert 0\rangle+\lvert 1\rangle)$ and the target in $\lvert u\rangle$ with $U\lvert u\rangle=e^{2\pi i\varphi}\lvert u\rangle$ , then apply $\mathrm{C}U$ branch by branch: $\mathrm{C}U\lvert +\rangle\lvert u\rangle=\tfrac{1}{\sqrt2}(\lvert 0\rangle\lvert u\rangle+\lvert 1\rangle U\lvert u\rangle)$ . Why: the defining operator acts as identity on the $\lvert 0\rangle$ branch and as $U$ on the $\lvert 1\rangle$ branch, so linearity is all that is used here.

Step 2. Substitute the eigenvalue equation $U\lvert u\rangle=e^{2\pi i\varphi}\lvert u\rangle$ so the $\lvert 1\rangle$ branch becomes $e^{2\pi i\varphi}\lvert 1\rangle\lvert u\rangle$ . Why: because $\lvert u\rangle$ is an eigenstate, $U$ is only permitted to multiply by a scalar — the target amplitude is preserved and only a phase appears.

Step 3. Factor the common target: the state is $\tfrac{1}{\sqrt2}(\lvert 0\rangle+e^{2\pi i\varphi}\lvert 1\rangle)\otimes\lvert u\rangle$ , a product state. Why: the eigenphase has "kicked back" onto the control and the target is disentangled — you could discard the target and keep the phase, which is what phase estimation effectively does.

Step 4. Read out by interference: a Hadamard on the control gives measurement probability $\tfrac12(1+\cos2\pi\varphi)=\cos^2(\pi\varphi)$ for outcome $0$ , encoding $\varphi$ ; a register of controls with powers $\mathrm{C}U^{2^j}$ plus an inverse QFT extracts $\varphi$ bit by bit. Why: interference converts an unobservable relative phase into observable statistics — this is the readout step of the phase-estimation algorithm. *Substituting the eigenvalue equation gives a product state; for $U=T$ ( $\varphi=1/8$ ) the Hadamard gives $P(0)=\cos^2(\pi/8)=0.854$ .*

Limiting cases

Particular choices of the target unitary collapse $\mathrm{C}U$ onto the standard named gates — and one choice exposes the global-phase subtlety directly:

Case	Result	Meaning
$U=I$	$\mathrm{C}I=I\otimes I$	trivial: the control does nothing, the gate is the identity on both qubits
$U=X$	$\mathrm{C}X=\lvert 0\rangle\langle 0\rvert\otimes I+\lvert 1\rangle\langle 1\rvert\otimes X$	the CNOT: flips the target iff the control is $\lvert 1\rangle$
$U=Z$	$\mathrm{C}Z=\mathrm{diag}(1,1,1,-1)$	controlled- $Z$ : diagonal, and symmetric under control $\leftrightarrow$ target exchange
$U=R_z(\phi)$	$\mathrm{C}R_z(\phi)=\mathrm{diag}(1,1,e^{-i\phi/2},e^{i\phi/2})$	controlled phase rotation — the building block of the quantum Fourier transform
$U=e^{i\alpha}I$	$\mathrm{C}(e^{i\alpha}I)=\mathrm{diag}(1,1,e^{i\alpha},e^{i\alpha})$	a pure global phase on $U$ becomes a real phase gate on the control

Worked examples

1 · Single-bit phase estimation with controlled-T (fully worked)

Take $U=T=\mathrm{diag}(1,e^{i\pi/4})$ , the $\pi/8$ gate. Its $\lvert 1\rangle$ eigenvalue is $e^{i\pi/4}$ , so $\lvert 1\rangle$ is an eigenstate with phase $\varphi=1/8$ . Prepare the control in $\lvert +\rangle$ and the target in $\lvert 1\rangle$ , apply controlled- $T$ , then Hadamard the control. Find the measurement statistics and show they encode $\varphi$ .

Step 1. Apply controlled- $T$ branch by branch. Since $T\lvert 1\rangle=e^{i\pi/4}\lvert 1\rangle$ , kickback (equation 4) gives $\mathrm{C}T\lvert +\rangle\lvert 1\rangle=\tfrac{1}{\sqrt2}(\lvert 0\rangle+e^{i\pi/4}\lvert 1\rangle)\otimes\lvert 1\rangle$ . The target is untouched; the phase $e^{i\pi/4}$ has moved onto the control. The state factorizes — the target does no visible work yet carries the answer.

Step 2. Hadamard the control. Using $H\lvert 0\rangle=\tfrac{1}{\sqrt2}(\lvert 0\rangle+\lvert 1\rangle)$ and $H\lvert 1\rangle=\tfrac{1}{\sqrt2}(\lvert 0\rangle-\lvert 1\rangle)$ , the control becomes $\tfrac12\big[(1+e^{i\pi/4})\lvert 0\rangle+(1-e^{i\pi/4})\lvert 1\rangle\big]$ .

Step 3. Compute the outcome- $0$ probability: $P(0)=\tfrac14\lvert 1+e^{i\pi/4}\rvert^2=\tfrac14(2+2\cos\tfrac{\pi}{4})=\tfrac12(1+\cos\tfrac{\pi}{4})=\cos^2(\pi/8)$ . Numerically $\cos^2(\pi/8)=\mathbf{0.854}$ and $P(1)=\sin^2(\pi/8)=\mathbf{0.146}$ .

Step 4. Interpret. The bias of the coin is set entirely by the eigenphase, $P(0)=\tfrac12(1+\cos2\pi\varphi)$ , so the lopsided result signals a small phase $\varphi=1/8$ . Repeating with controlled powers $\mathrm{C}T^{2^j}$ and an inverse QFT extracts the bits of $\varphi$ exactly — this single gate is one round of phase estimation. $P(0)=\cos^2(\pi/8)=0.854$ , $P(1)=0.146$ , reading $\varphi=1/8$ .

2 · Assembling a Toffoli from controlled-√X

The Toffoli gate $\mathrm{C}^2X$ flips the target only when both controls are $\lvert 1\rangle$ . Build it from two-qubit controlled gates using $V=\sqrt{X}$ , the " $\mathrm{SX}$ " gate native to superconducting hardware, where $V=\tfrac12\begin{pmatrix}1+i&1-i\\1-i&1+i\end{pmatrix}$ and $V^2=X$ .

Step 1. Confirm the building block: $V^2=\tfrac14\begin{pmatrix}(1+i)^2+(1-i)^2 & 2\cdot 2\\ 2\cdot 2 & (1+i)^2+(1-i)^2\end{pmatrix}=\begin{pmatrix}0&1\\1&0\end{pmatrix}=X$ , using $(1+i)^2+(1-i)^2=2i-2i=0$ and $(1+i)(1-i)=2$ . So two applications of the controlled- $\sqrt X$ equal one controlled- $X$ .

Step 2. Lay out the Barenco circuit on qubits (control 1, control 2, target 3), read left to right in time: $\mathrm{C}V_{2,3}$ , $\mathrm{C}X_{1,2}$ , $\mathrm{C}V^\dagger_{2,3}$ , $\mathrm{C}X_{1,2}$ , $\mathrm{C}V_{1,3}$ .

Step 3. Track the net target operation over the four control settings. Both $0$ : every gate idle, net $I$ . Controls $(0,1)$ : target sees $V$ then $V^\dagger$ , net $I$ . Controls $(1,0)$ : the CNOTs toggle qubit 2 so the target sees $V^\dagger$ then $V$ , net $I$ . Controls $(1,1)$ : qubit 2 is toggled to $0$ before the middle gate, so the target sees $V$ then $V$ , net $V^2=X$ .

Step 4. The target is flipped by $X$ only when both controls are $\lvert 1\rangle$ — precisely the Toffoli truth table. $\mathrm{C}^2X=\mathrm{C}V_{1,3}\,\mathrm{C}X_{1,2}\,\mathrm{C}V^\dagger_{2,3}\,\mathrm{C}X_{1,2}\,\mathrm{C}V_{2,3}$ with $V=\sqrt X$ (verified to machine precision). The same $V=\sqrt U$ recursion builds $\mathrm{C}^2U$ for any $U$ , and iterating gives $\mathrm{C}^nU$ .

Physics of the portrait

Controlled gates are where the idea of a "quantum program" became concrete: a circuit of conditional unitaries on qubits. The person who framed computation that way, and first exhibited a universal controlled-controlled gate, is David Deutsch.

Origins · 1 minDavid Deutsch and how this was discovered

David Deutsch

b. 1953, Haifa / Oxford · founder of the quantum circuit model and universal controlled gates

David Deutsch turned quantum computation from a slogan into a formalism. In 1985 he defined the universal quantum Turing machine and argued, via the Church–Turing–Deutsch principle, that a device built on quantum evolution could do what no classical machine efficiently could. But it was his 1989 paper "Quantum computational networks" that introduced the language used ever since: computation as a network of quantum gates, unitary boxes wired together in time. There Deutsch exhibited a single three-qubit gate — the Deutsch gate $D(\theta)$ , a controlled-controlled rotation applying $iR_x(\theta)$ only when two controls are both $\lvert 1\rangle$ — and proved it universal: any quantum computation can be approximated by that one gate alone (for $\theta$ an irrational multiple of $\pi$ ). This is the controlled- $U$ idea at full stretch, and it set the programme that Barenco, Bennett, Cleve, DiVincenzo and collaborators completed in 1995 with the two-CNOT compilation of an arbitrary $\mathrm{C}U$ and the recursive $\mathrm{C}^nU$ construction. Deutsch also gave the field its first algorithm — the Deutsch, later Deutsch–Jozsa, problem — whose speed-up runs entirely on phase kickback. The modern circuit model, in which every conditional operation is some $\mathrm{C}U$ , descends directly from his networks.

History

1985

— Deutsch defines the universal quantum Turing machine and the Church–Turing–Deutsch principle

1989

— Deutsch introduces quantum computational networks and the universal controlled-controlled Deutsch gate

1995

— Barenco proves a single two-qubit gate is universal for quantum computation

1995

— Barenco, Bennett, Cleve and collaborators give the two-CNOT controlled-U compilation and the CⁿU recursion

1995

— DiVincenzo shows two-qubit gates suffice for universal quantum computation

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §4.3 (controlled operations) and Fig. 4.6, §5.2 (phase estimation) · Preskill, Lecture Notes for Physics 219, Ch. 5 (classical and quantum circuits) · Barenco, Bennett, Cleve, DiVincenzo, Margolus, Shor, Sleator, Smolin, Weinfurter, "Elementary gates for quantum computation," Phys. Rev. A 52, 3457 (1995) · Watrous, The Theory of Quantum Information, Ch. 2 · Kitaev, Shen, Vyalyi, Classical and Quantum Computation, §8 · Mermin, Quantum Computer Science, Ch. 2. Key checkpoints: the block-diagonal matrix follows from the $\{00,01,10,11\}$ ordering; $ABC=I$ and $e^{i\alpha}AXBXC=U$ via $XR_{y/z}(\theta)X=R_{y/z}(-\theta)$ ; the kickback factorization gives $P(0)=\cos^2(\pi/8)=0.854$ for controlled- $T$ ; and the Toffoli identity rests on $V=\sqrt X$ , $V^2=X$ .

Prerequisites. Quantum Circuit Model · Single-Qubit Rotation Gates · Z–Y Decomposition of Single-Qubit Gates · CNOT Gate. Leads to. Controlled-Z Gate · Universal Gate Sets · Circuit Identities and Equivalences · SWAP Gate.

Ask the tutor: Ask me to walk you through the two-CNOT ABC compilation of any specific gate — a controlled-Hadamard, controlled- $S$ , or a controlled rotation from your own circuit — or to show how phase kickback turns into the bits of a phase-estimation readout.

Is the "control" qubit really more in charge than the target?

Less than the name suggests — the asymmetry lives entirely in $U$ , not in the construction. For controlled- $Z$ the roles are interchangeable: $\mathrm{C}Z=\mathrm{diag}(1,1,1,-1)$ is symmetric under swapping the qubits, because $Z$ is diagonal. Even for CNOT you can move "which qubit is the control" by conjugating with Hadamards, since $(H\otimes H)\,\mathrm{C}X\,(H\otimes H)$ is a CNOT with control and target exchanged. And under phase kickback it is often the target that supplies the information while the control merely records it. Control and target are labels of convenience, not a fixed hierarchy.

What is phase kickback, intuitively?

A controlled gate acting on an eigenstate of $U$ cannot change that eigenstate — it may only multiply it by the eigenvalue $e^{i\theta}$ — but that scalar attaches to the $\lvert 1\rangle$ branch of the control alone. So a property of the target (its eigenphase) is copied onto the control as a relative phase you can read by interference, while the target comes out exactly as it went in. This is why phase estimation feeds $U$ an eigenstate it never disturbs yet extracts the eigenphase to many bits: the answer was always riding on the control.

Why exactly two CNOTs — can I ever do it in one?

For a generic single-qubit $U$ , two CNOTs are necessary and sufficient. The ABC construction achieves two, and Barenco et al. proved you cannot generally do better: a single CNOT with surrounding single-qubit gates realizes only a restricted family, because the $ABC=I$ constraint with one $X$ insertion cannot reproduce an arbitrary $\lvert 1\rangle$ -branch unitary while keeping the $\lvert 0\rangle$ -branch identity. Special cases do better — a gate equivalent to controlled- $Z$ up to single-qubit gates costs one entangler, and $\mathrm{C}I$ costs none — but "two CNOTs for a generic $\mathrm{C}U$ " is the tight bound.

How do I build a controlled gate if my hardware only has CNOT?

You use the two-CNOT ABC circuit (equation 6): decompose $U=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)$ , form $A,B,C$ from those angles, and lay down $C$ , CNOT, $B$ , CNOT, $A$ on the target with a phase gate $\mathrm{diag}(1,e^{i\alpha})$ on the control. Every gate there is a CNOT or a single-qubit rotation, both native to essentially all hardware — this is exactly what a transpiler emits for an abstract $\mathrm{C}U$ . The one thing hand-compilers forget is the control-phase gate $\Phi(\alpha)$ ; omit it and the gate is wrong by a control-dependent phase.

How does controlled-U scale to many control qubits?

A multiply-controlled gate $\mathrm{C}^nU$ fires only when all $n$ controls are $\lvert 1\rangle$ . You build it recursively from two-qubit controlled gates using $V=\sqrt U$ : Worked Example 2 shows $\mathrm{C}^2U$ from three controlled- $V$ / $V^\dagger$ gates and two CNOTs, and the same idea nests upward. With a handful of ancilla qubits $\mathrm{C}^nX$ (the multi-controlled Toffoli) can be done with $O(n)$ two-qubit gates. These constructions underlie quantum oracles, Grover's diffusion operator, and reversible arithmetic — anywhere a large logical AND of qubits must gate an operation.

Does measuring the control after kickback disturb the target?

No, provided the target was an eigenstate of $U$ . After kickback the joint state is a product, $(\alpha\lvert 0\rangle+e^{i\theta}\beta\lvert 1\rangle)\otimes\lvert u\rangle$ , so measuring the control leaves $\lvert u\rangle$ untouched — the same eigenstate can be fed through many controlled powers of $U$ without being consumed, which is exactly what phase estimation relies on. The story changes if the target is not an eigenstate: the output (equation 3) is then entangled, and measuring the control back-acts on the target, projecting it into $\lvert\psi\rangle$ or $U\lvert\psi\rangle$ .

Controlled-U Gates

Where this lives today

The physical picture

The core equations

Limiting cases

Worked examples

1 · Single-bit phase estimation with controlled-T (fully worked)

2 · Assembling a Toffoli from controlled-√X

Physics of the portrait

Going further

Before this

Where this leads