CNOT Gate

The controlled-NOT gate is the smallest machine in quantum computing that does something a single qubit cannot: it makes two qubits know about each other. Written CNOT or CX, it is the simplest nontrivial two-qubit gate — one qubit is named the control, the other the target, and the rule is a single line of classical logic. If the control reads 1, flip the target with a Pauli X; if it reads 0, do nothing. On the four computational basis states this is nothing but the reversible XOR, $|c,t\rangle\mapsto|c,\,t\oplus c\rangle$ , a permutation that swaps two labels and leaves the rest alone. A classical engineer would recognize it instantly and see nothing new. The novelty is hidden in one word: coherently. Because a quantum gate is a linear operator, the "if" may itself be in superposition. Feed CNOT a control spread across $|0\rangle$ and $|1\rangle$ and it does not choose a branch — it writes both, tying the target's fate to the control's amplitude pattern. A product input $(\alpha|0\rangle+\beta|1\rangle)|0\rangle$ walks in and the entangled $\alpha|00\rangle+\beta|11\rangle$ walks out, a thing that can no longer be described as two independent qubits. That single fact — a two-qubit gate that manufactures entanglement from a product state — is why CNOT sits at the center of the circuit model. Combined with arbitrary single-qubit rotations it is universal: any quantum computation is a network of CNOTs and one-qubit turns. It is also the workhorse of error correction, the partner of controlled- $Z$ under a Hadamard, and, tripled, a SWAP — and in real hardware it is usually the noisiest, slowest thing on the chip, which is why counting CNOTs is how you price a quantum algorithm.

Key takeaways

The CNOT gate applies a Pauli- $X$ (bit-flip) to a target qubit if and only if the control qubit is $|1\rangle$ , and does nothing when the control is $|0\rangle$ .
On basis states it is the reversible XOR $|c,t\rangle\mapsto|c,\,t\oplus c\rangle$ — a permutation unitary that only ever exchanges $|10\rangle\leftrightarrow|11\rangle$ , so it is Hermitian, unitary, and its own inverse.
By linearity it entangles: $(\alpha|0\rangle+\beta|1\rangle)|0\rangle\mapsto\alpha|00\rangle+\beta|11\rangle$ , and $\mathrm{CNOT}\,(H\otimes I)|00\rangle=\tfrac{1}{\sqrt2}(|00\rangle+|11\rangle)$ is the textbook Bell-pair recipe.
Together with all single-qubit gates it is a universal set for quantum computation; it is locally equivalent to controlled- $Z$ via Hadamards, and three CNOTs make a SWAP.
As a Clifford gate it propagates Pauli errors deterministically ( $X_c\mapsto X_cX_t$ , $Z_t\mapsto Z_cZ_t$ ), which is the backbone of stabilizer syndrome extraction.
Key idea: CNOT embeds the classical XOR $|c,t\rangle\mapsto|c,t\oplus c\rangle$ as a permutation unitary; by linearity it entangles a superposed control with its target, and together with single-qubit rotations it suffices to build any quantum computation.

Where this lives today

The CNOT count is the single most-quoted cost figure in quantum computing, because on every leading platform the two-qubit gate is the expensive, error-prone bottleneck. On superconducting processors the CNOT is not native at all — IBM's machines synthesize it from a cross-resonance interaction plus single-qubit corrections, while Google's use a controlled- $Z$ or iSWAP-family gate as the primitive and compile CNOT on top via the Hadamard identity of equation (5). Trapped-ion systems realize the equivalent entangler through a Mølmer–Sørensen gate mediated by the ions' shared motion, and neutral-atom arrays use Rydberg blockade. Whatever the substrate, two-qubit-gate infidelity — a few parts in a thousand on the best 2020s devices, versus parts in ten thousand for single-qubit gates — dominates the error budget and caps circuit depth, which is why compilers work so hard to route qubits and cancel CNOTs, and why every connectivity SWAP costs three of them. Fault tolerance leans on CNOT even harder: the surface code that Google demonstrated below threshold in 2023–2024 stitches data and measurement qubits together with scheduled CNOTs (or CZ equivalents) that extract $X$ - and $Z$ -type parity syndromes each cycle, and it is the deterministic Pauli-propagation rules of Derivation C that let a decoder turn those syndromes into corrections in real time. The open frontier — lower error rates, faster decoding, and gates that entangle distant modules through photonic links — is, at bottom, the engineering of a better CNOT.

The physical picture

Read CNOT first as a piece of classical circuitry and it is disappointingly simple. Two wires run across the page; a dot on the control wire and a $\oplus$ on the target wire, joined by a vertical line, say "toggle the target when the control is on." On the four labelled inputs it does exactly what a reversible XOR gate would: it leaves $|00\rangle$ and $|01\rangle$ untouched and swaps $|10\rangle$ with $|11\rangle$ . Nothing is scaled, nothing is created; the amplitudes are merely shuffled between two slots. That is why the gate is a permutation matrix — manifestly unitary, and its own inverse, since swapping the same pair twice returns everything home. The first figure is this permutation drawn honestly, the two moved labels flagged in red.

Figure

CNOT as a coherent if-then and a basis-state permutation: the control dot and target ⊕ send c,t to c, t⊕c, leaving 00 and 01 fixed while exchanging only 10 ↔ 11 — a permutation of the four labels, so CNOT is unitary and squares to the identity

Now turn the same gate loose on a superposition and the classical reading breaks down. If the control is $\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)$ , CNOT does not read it and pick a branch — linearity forces it to act on both halves at once, and the "if" gets written into a correlation rather than resolved into an answer. Starting from $|00\rangle$ , a Hadamard on the control spreads it across the poles, and the CNOT ties the target to that spread, producing the Bell state $\tfrac{1}{\sqrt2}(|00\rangle+|11\rangle)$ : the two qubits are now perfectly correlated and individually undefined. This is the gate's real job — it is the minimal entangler, the smallest circuit that turns separable inputs into the maximally entangled pairs behind teleportation, dense coding, and Bell tests. The second figure is that recipe with the amplitudes made numerical.

Figure

The Bell-state generator with real amplitudes: H on the control turns 00 into an equal mix of 00 and 10, then CNOT ties the target to the control to give the Bell state Φ⁺ = (00 + 11)/√2 — amplitude 1/√2 ≈ 0.7071 on 00 and 11 and exactly 0 on 01 and 10

Two more facts round out the picture. First, the control/target labels are a matter of basis, not physics: conjugating both qubits by Hadamard turns a CNOT with control on qubit 1 into a CNOT with control on qubit 2 — the very same operator, seen in the rotated $X$ basis, with "who controls whom" reversed. Second, entanglement is not automatic. Feed CNOT a control already in a definite basis state, or feed it $|+\rangle|+\rangle$ (an eigenstate it leaves alone), and the output is a boring product state. The gate only earns its keep when the control carries a genuine computational-basis superposition and the target sits ready at a pole.

The core equations

The most concrete definition is the matrix in the ordered basis $\{|00\rangle,|01\rangle,|10\rangle,|11\rangle\}$ , where the first index is the control and the second the target. Reading it as columns, each column is the image of one input ket.

\mathrm{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} \qquad (1)

where: first index — control qubit value $c$ ; second index — target qubit value $t$ ; the top-left $2\times2$ block is the identity ( $c=0$ ), the bottom-right block is the Pauli $X$ ( $c=1$ ). The reading: it is a permutation matrix — every entry is $0$ or $1$ , one per row and column — so it merely relabels basis states and is automatically unitary. The same content compresses to a single arithmetic rule on the labels, the reversible XOR that names the gate. Everything else is a consequence of this line plus linearity.

\mathrm{CNOT}\,|c\rangle|t\rangle = |c\rangle\,|t\oplus c\rangle \qquad (2)

where: $c$ — control bit, $c\in\{0,1\}$ ; $t$ — target bit, $t\in\{0,1\}$ ; $\oplus$ — addition modulo 2 (XOR). The reading: the control passes through unchanged in this basis, and the target is XORed with it, so $c=1$ flips the target and $c=0$ leaves it alone. Lifting the rule off the basis states gives the operator form that generalizes to any controlled gate: a sum of two branches selected by projectors on the control. This is the definition that makes CNOT a member of the controlled- $U$ family with $U=X$ .

\mathrm{CNOT} = |0\rangle\langle 0|\otimes I + |1\rangle\langle 1|\otimes X \qquad (3)

where: $|0\rangle\langle0|,\,|1\rangle\langle1|$ — orthogonal projectors onto the control states; $I$ — the $2\times2$ identity on the target; $X$ — the Pauli- $X$ (NOT) on the target. The reading: the $|0\rangle$ branch applies $I$ , the $|1\rangle$ branch applies $X$ , and because the projectors are orthogonal the two branches never interfere — replacing $X$ by any single-qubit $U$ gives controlled- $U$ . Because the gate is a real symmetric permutation, it is at once Hermitian and unitary, which forces it to be its own inverse — a fact worth stating on its own because it means CNOT undoes itself.

\mathrm{CNOT}^{\dagger} = \mathrm{CNOT}, \qquad \mathrm{CNOT}^{2} = I \qquad (4)

where: $\dagger$ — conjugate transpose; $I$ — the $4\times4$ identity. The reading: self-adjointness ( $\mathrm{CNOT}=\mathrm{CNOT}^\dagger$ ) plus unitarity ( $\mathrm{CNOT}^\dagger\mathrm{CNOT}=I$ ) collapse to $\mathrm{CNOT}^2=I$ , the operator statement that flipping twice on the same condition changes nothing. CNOT is not a special gate standing apart from controlled- $Z$ ; the two are the same object viewed in target bases related by a Hadamard, since $H$ conjugates $Z$ into $X$ . This is the single most-used circuit identity for moving between the two conventions.

\mathrm{CNOT} = (I\otimes H)\,\mathrm{CZ}\,(I\otimes H) \qquad (5)

where: $H$ — the Hadamard gate on the target; $\mathrm{CZ}=|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes Z$ — the controlled- $Z$ gate. The reading: conjugating the target by $H$ leaves the $|0\rangle$ branch as $HIH=I$ and turns the $|1\rangle$ branch into $HZH=X$ — a fact used constantly because CZ, being symmetric in its two qubits, is often the native two-qubit gate on hardware. Three CNOTs in an alternating pattern implement a SWAP, the identity behind routing qubits on a connectivity-limited chip. It is the cheapest way to exchange two qubits without an ancilla.

\mathrm{SWAP} = \mathrm{CNOT}_{12}\,\mathrm{CNOT}_{21}\,\mathrm{CNOT}_{12} \qquad (6)

where: $\mathrm{CNOT}_{12}$ — control on qubit 1, target on qubit 2; $\mathrm{CNOT}_{21}$ — control on qubit 2, target on qubit 1. The reading: three XORs, tracked bit by bit (Derivation B), leave each qubit holding the other's value. Finally, the recipe that makes CNOT famous: a Hadamard on the control followed by CNOT sends the trivial input $|00\rangle$ to a maximally entangled Bell pair.

\mathrm{CNOT}\,(H\otimes I)\,|0\rangle|0\rangle = \tfrac{1}{\sqrt2}\big(|00\rangle+|11\rangle\big) = |\Phi^+\rangle \qquad (7)

where: $H$ — the Hadamard on the control; $|\Phi^+\rangle$ — one of the four Bell states. The reading: the Hadamard makes the control a superposition, the CNOT copies its value onto the target, and the result cannot be factored — this is the gate turning separability into entanglement in two moves.

Derivation AMaking a Bell pair from a superposed control

The goal is to follow, amplitude by amplitude, how the two-gate circuit $H$ -then-CNOT converts the plain product state $|00\rangle$ into the maximally entangled Bell state $|\Phi^+\rangle$ , and to prove at the end that the output genuinely cannot be written as a product of two single-qubit states. This is the concrete demonstration that CNOT is an entangling gate: linearity, applied to a control that has been spread across both poles, forces the target to become correlated with it rather than independent.

Step 1. Apply the Hadamard to the control while the identity leaves the target alone: $(H\otimes I)|00\rangle=\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)\otimes|0\rangle=\tfrac{1}{\sqrt2}(|00\rangle+|10\rangle)$ . The state is still a product — the control is in $|+\rangle$ , the target is a clean $|0\rangle$ , and nothing links them yet. Why: the Hadamard is what puts the "if" of the CNOT into superposition; without it the control is a definite bit and the gate can only do classical logic.

Step 2. Apply CNOT term by term using the action rule (2). The $|00\rangle$ term has control $0$ , so its target is untouched and it stays $|00\rangle$ ; the $|10\rangle$ term has control $1$ , so its target flips $0\mapsto1$ and it becomes $|11\rangle$ . Linearity adds the images: $\mathrm{CNOT}\,\tfrac{1}{\sqrt2}(|00\rangle+|10\rangle)=\tfrac{1}{\sqrt2}(|00\rangle+|11\rangle)$ . Why: the gate never "chose" a branch — it acted on both simultaneously, which is precisely how the control's superposition gets transcribed into a correlation between the qubits.

Step 3. Prove the output is entangled by contradiction. Suppose $\tfrac{1}{\sqrt2}(|00\rangle+|11\rangle)=(a|0\rangle+b|1\rangle)\otimes(c|0\rangle+d|1\rangle)$ . Expanding, the $|01\rangle$ coefficient is $ad$ and the $|10\rangle$ coefficient is $bc$ , both of which must vanish; but the $|00\rangle$ coefficient $ac$ and the $|11\rangle$ coefficient $bd$ must both equal $\tfrac{1}{\sqrt2}\neq0$ , forcing all of $a,b,c,d$ nonzero — a contradiction. Why: this is the operational meaning of entanglement — no assignment of independent single-qubit states reproduces the joint amplitudes, so the two qubits have no separate identities. *Note: the output amplitudes are $\tfrac{1}{\sqrt2}\approx0.7071$ on $|00\rangle$ and $|11\rangle$ and exactly zero on $|01\rangle$ and $|10\rangle$ ; the reduced state of either qubit alone is the maximally mixed $\tfrac12 I$ .*

Go deeper · Derivation B · 1 minThree controlled-NOTs implement a SWAP

Derivation BThree controlled-NOTs implement a SWAP

The aim is to verify the identity $\mathrm{CNOT}_{12}\,\mathrm{CNOT}_{21}\,\mathrm{CNOT}_{12}=\mathrm{SWAP}$ by tracking an arbitrary basis state $|a,b\rangle$ through the three XORs and showing it emerges as $|b,a\rangle$ , then invoking linearity for all inputs. This is the circuit compilers use to exchange two qubits that are not physically adjacent, and it is the cheapest such construction — no SWAP is native to most hardware, so it is synthesized from three two-qubit gates.

Step 1. Apply $\mathrm{CNOT}_{12}$ (control qubit 1): $|a,b\rangle\mapsto|a,\,b\oplus a\rangle$ . Qubit 2 now carries the XOR of the two bits while qubit 1 is unchanged. Why: XOR is the only nonlinear-looking move available, but modulo-2 arithmetic makes it perfectly reversible, which is what lets three of them compose into a clean swap.

Step 2. Apply $\mathrm{CNOT}_{21}$ (control qubit 2, now holding $b\oplus a$ ): $|a,\,b\oplus a\rangle\mapsto|a\oplus(b\oplus a),\,b\oplus a\rangle=|b,\,b\oplus a\rangle$ , using $a\oplus a=0$ so that $a\oplus(b\oplus a)=b$ . Qubit 1 now holds the original value of qubit 2. Why: the self-inverse property of XOR, $a\oplus a=0$ , is doing all the work — it is why the second CNOT cleanly deposits $b$ onto the first wire.

Step 3. Apply $\mathrm{CNOT}_{12}$ again (control qubit 1, now holding $b$ ): $|b,\,b\oplus a\rangle\mapsto|b,\,(b\oplus a)\oplus b\rangle=|b,a\rangle$ , using $(b\oplus a)\oplus b=a$ . The bits are exchanged, and since the map $|a,b\rangle\mapsto|b,a\rangle$ holds on all four basis states, unitary linearity extends it to every superposition. Why: verifying on a spanning set plus linearity is the standard way to prove a circuit identity — a permutation that swaps the basis labels the right way is the SWAP operator, full stop. *Direct matrix multiplication confirms $\mathrm{CNOT}_{12}\,\mathrm{CNOT}_{21}\,\mathrm{CNOT}_{12}$ is the SWAP, exchanging $|01\rangle\leftrightarrow|10\rangle$ and leaving $|00\rangle$ and $|11\rangle$ fixed.*

Go deeper · Derivation C · 1 minHow CNOT propagates Pauli errors

Derivation CHow CNOT propagates Pauli errors

The purpose is to derive the four conjugation rules that describe how CNOT moves single-qubit Pauli operators through itself, $P\mapsto\mathrm{CNOT}\,P\,\mathrm{CNOT}$ , and to explain why these rules — not the state evolution — are what make CNOT the backbone of stabilizer error correction. Because CNOT is a Clifford gate, conjugating any Pauli string yields another Pauli string, so an error entering a circuit does not smear into a general operator; it merely relabels, and a syndrome measurement can catch it. Throughout, subscripts $c,t$ label control and target, and we use $\mathrm{CNOT}^2=I$ so conjugation means sandwiching.

Step 1. Take $X$ on the control, $X_c\otimes I$ . Physically, flipping the control before the gate changes which branch fires; the algebra gives $\mathrm{CNOT}\,(X_c\otimes I)\,\mathrm{CNOT}=X_c\otimes X_t$ , so a control bit-flip propagates a copy onto the target. Why: this is the mechanism by which a single physical $X$ error becomes a two-qubit error — tracking it is exactly what a decoder must do.

Step 2. Take $X$ on the target, $I\otimes X_t$ . A target flip commutes through the conditional flip because both are $X$ 's on the same qubit: $\mathrm{CNOT}\,(I\otimes X_t)\,\mathrm{CNOT}=I\otimes X_t$ , unchanged. Why: $X$ errors flow only from control to target, never backward — the asymmetry of the gate is written directly into how errors spread.

Step 3. Take $Z$ on the control, $Z_c\otimes I$ . Since $Z$ is diagonal and the control is unaltered in the computational basis, it commutes straight through: $\mathrm{CNOT}\,(Z_c\otimes I)\,\mathrm{CNOT}=Z_c\otimes I$ . Why: phase information on the control is invisible to a gate that only conditions on control amplitudes, so it passes untouched.

Step 4. Take $Z$ on the target, $I\otimes Z_t$ . Now the flow reverses: $\mathrm{CNOT}\,(I\otimes Z_t)\,\mathrm{CNOT}=Z_c\otimes Z_t$ , so a target phase-flip propagates backward onto the control. Why: $Z$ errors travel target-to-control while $X$ errors travel control-to-target — the mirror image being the same control/target reversal that Hadamard conjugation makes explicit, and together the four rules let a stabilizer code predict every error's fate. *The four conjugation results are: $\mathrm{CNOT}\,X_c\,\mathrm{CNOT}=X_cX_t$ , $\mathrm{CNOT}\,Z_t\,\mathrm{CNOT}=Z_cZ_t$ , $\mathrm{CNOT}\,X_t\,\mathrm{CNOT}=X_t$ , and $\mathrm{CNOT}\,Z_c\,\mathrm{CNOT}=Z_c$ , in agreement with the standard stabilizer Clifford table.*

Limiting cases

The special inputs below make the gate's logic and its entangling power concrete, and are the cases worth carrying in your head.

Case	Result	Meaning
Control in $\vert 0\rangle$	$\mathrm{CNOT}\,\vert 0\rangle\vert t\rangle = \vert 0\rangle\vert t\rangle$	target untouched — the gate is the identity on this subspace
Control in $\vert 1\rangle$	$\mathrm{CNOT}\,\vert 1\rangle\vert t\rangle = \vert 1\rangle\,X\vert t\rangle$	target bit-flipped, $\vert t\rangle\mapsto\vert t\oplus1\rangle$
Superposed control, target $\vert 0\rangle$	$\mathrm{CNOT}\,(\alpha\vert 0\rangle+\beta\vert 1\rangle)\vert 0\rangle = \alpha\vert 00\rangle+\beta\vert 11\rangle$	generically entangled for $\alpha,\beta\neq0$ — the Bell-state generator
Both qubits in $\vert +\rangle$	$\mathrm{CNOT}\,\vert +\rangle\vert +\rangle = \vert +\rangle\vert +\rangle$	a $+1$ eigenstate; in the $X$ basis it is the control that is left fixed
Target in $\vert -\rangle$	$\mathrm{CNOT}\,\vert c\rangle\vert -\rangle = (-1)^{c}\vert c\rangle\vert -\rangle$	phase kickback: the flip becomes a phase on the control, the seed of phase estimation

Common trapThe control qubit is untouched and CNOT just classically reads it

Both halves are wrong, and both come from importing classical intuition. First, the control is not generally left alone: in the computational basis it happens to pass through, but conjugating both qubits by Hadamard gives $(H\otimes H)\,\mathrm{CNOT}_{12}\,(H\otimes H)=\mathrm{CNOT}_{21}$ , so in the $X$ basis the control and target swap roles entirely — "who controls whom" is a basis convention, not a physical fact. Second, CNOT does not "read" the control the way a classical wire samples a bit. On a superposed control it creates entanglement, and a target in state $|-\rangle$ shows the reverse flow directly: $\mathrm{CNOT}\,|c\rangle|-\rangle=(-1)^c|c\rangle|-\rangle$ , a phase kickback that stamps the target's phase back onto the control. A gate that pushes a phase onto its own control is not passively reading it — it is fully entangling the two, and treating the control as an undisturbed classical bit gives wrong answers in any interference-sensitive circuit.

Worked examples

1 · Partial entanglement from an unbalanced control (fully worked)

A control qubit is prepared in $0.6\,|0\rangle+0.8\,|1\rangle$ (note $0.6^2+0.8^2=1$ ) and the target in $|0\rangle$ . Apply CNOT. Find the output state, the two-qubit measurement statistics, and quantify the entanglement produced.

Step 2. Measurement in the computational basis gives probabilities from the squared amplitudes: $P(00)=0.6^2=\mathbf{0.36}$ and $P(11)=0.8^2=\mathbf{0.64}$ , while $P(01)=P(10)=0$ . The two qubits are perfectly correlated — you never see 01 or 10 — but the marginal on either qubit is biased $0.36/0.64$ , not $50/50$ as for a Bell pair.

Step 3. Quantify the entanglement. The reduced density matrix of either qubit is $\rho=\mathrm{diag}(0.36,\,0.64)$ , whose eigenvalues are the two probabilities. The entanglement entropy is $S=-0.36\log_2 0.36-0.64\log_2 0.64\approx0.531+0.412=\mathbf{0.943}$ ebits, short of the $1$ ebit of a maximally entangled Bell pair. Equivalently the concurrence is $C=2|0.6\cdot0.8|=\mathbf{0.96}$ . CNOT produced genuine but sub-maximal entanglement — $0.943$ ebits — because the control was superposed but unbalanced; a balanced control ( $0.707,0.707$ ) would give the full $1$ ebit.

2 · Fanning out a GHZ state with two CNOTs (fully worked)

Build the three-qubit GHZ state $\tfrac{1}{\sqrt2}(|000\rangle+|111\rangle)$ from $|000\rangle$ using one Hadamard and two CNOTs, and confirm the amplitudes.

Step 1. Hadamard the first qubit: $(H\otimes I\otimes I)|000\rangle=\tfrac{1}{\sqrt2}(|000\rangle+|100\rangle)$ . Qubit 1 is now spread across both poles with amplitude $\tfrac{1}{\sqrt2}\approx0.707$ ; qubits 2 and 3 are still $|0\rangle$ .

Step 2. Apply $\mathrm{CNOT}_{1\to2}$ (control qubit 1, target qubit 2). Only the $|100\rangle$ branch has control $1$ , so its second bit flips: $\tfrac{1}{\sqrt2}(|000\rangle+|110\rangle)$ . Qubit 2 is now chained to qubit 1.

Step 3. Apply $\mathrm{CNOT}_{1\to3}$ (control qubit 1, target qubit 3). Again only the $|110\rangle$ branch fires, flipping the third bit: $|\mathrm{GHZ}\rangle=\tfrac{1}{\sqrt2}(|000\rangle+|111\rangle)$ . The output has amplitude $1/\sqrt2\approx0.707$ on $|000\rangle$ and $|111\rangle$ and zero on the other six basis states. Measuring any one qubit collapses all three to the same value — the defining all-or-nothing correlation of GHZ, built by CNOT acting as a coherent copy of the control's value onto each target in turn.

Physics of the portrait

The controlled-NOT is a piece of engineering that arrived with a physicist's fingerprints on it: it was Richard Feynman, thinking about whether nature could be simulated efficiently, who first drew conditional quantum gates as the primitives of a computing machine.

Origins · 1 minRichard Feynman and how this was discovered

Richard Feynman

1918–1988 · the controlled-NOT as a primitive of quantum computation

Richard Feynman reshaped twentieth-century physics twice over — the path-integral formulation of quantum mechanics, the Feynman diagrams that organize quantum electrodynamics (for which he shared the 1965 Nobel Prize with Schwinger and Tomonaga), the theory of superfluid helium, the parton model of the proton, and a gift for exposition that made the Feynman Lectures a permanent fixture. Late in his career he turned to the physics of computation. In his 1981 keynote "Simulating Physics with Computers" he argued that a classical computer cannot efficiently simulate a general quantum system, because the state space grows exponentially, and proposed instead a computer built from quantum elements — the seed of the whole field. In the 1985 essay "Quantum Mechanical Computers" he made the idea concrete, sketching a reversible gate model whose primitives were the controlled-NOT and the controlled-controlled-NOT, and worrying already about error and dissipation. Feynman did not prove the universality theorem that anoints CNOT — that came with David Deutsch's quantum-network model in 1989 and the 1995 result of Barenco, Bennett, Cleve, DiVincenzo and collaborators that CNOT plus arbitrary single-qubit gates suffice to build any unitary — but he supplied the gate and the vision. He was also the physicist who, on the Rogers Commission, dunked an O-ring in ice water to explain the Challenger disaster on live television, insisting that for a successful technology reality must take precedence over public relations.

History

1973

— Bennett proves computation can be made logically reversible, removing the thermodynamic case against it

1980

— Toffoli's reversible controlled-controlled-NOT gives a universal classical reversible gate

1985

— Feynman presents the controlled-NOT among the primitive gates of a quantum computer

1989

— Deutsch formulates quantum computation as networks of quantum logic gates

1995

— Barenco, Bennett, Cleve, DiVincenzo and collaborators prove CNOT plus single-qubit gates are universal

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §1.3.2 (CNOT and circuits), §4.3 (controlled operations), §10.5 (stabilizer codes) · Preskill, Lecture Notes for Physics 219, Ch. 5 · Watrous, The Theory of Quantum Information, Ch. 2 · Wilde, Quantum Information Theory, Ch. 3 · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, Ch. 8 · Mermin, Quantum Computer Science, Ch. 2 · Barenco et al., "Elementary gates for quantum computation," Phys. Rev. A 52, 3457 (1995) for the universality theorem. Key relations and numbers collected here for reference: the $4\times4$ permutation matrix follows from the action rule $|c,t\rangle\mapsto|c,t\oplus c\rangle$ ; the projector form is $|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes X$ ; the Bell-state amplitude is $1/\sqrt2\approx0.7071$ ; the three-CNOT SWAP identity is $\mathrm{CNOT}_{12}\,\mathrm{CNOT}_{21}\,\mathrm{CNOT}_{12}=\mathrm{SWAP}$ ; the Hadamard conjugations are $\mathrm{CNOT}=(I\otimes H)\,\mathrm{CZ}\,(I\otimes H)$ and $(H\otimes H)\,\mathrm{CNOT}_{12}\,(H\otimes H)=\mathrm{CNOT}_{21}$ ; the Clifford table reads $X_c\mapsto X_cX_t$ , $X_t\mapsto X_t$ , $Z_c\mapsto Z_c$ , $Z_t\mapsto Z_cZ_t$ ; and the worked numbers are $0.6\,|00\rangle+0.8\,|11\rangle$ with $P=0.36/0.64$ , entropy $0.943$ ebits, concurrence $0.96$ , and GHZ amplitudes $1/\sqrt2$ . All matrix entries are $0$ or $1$ in the computational basis; normalizations $1/\sqrt2$ are standard.

Prerequisites. Pauli Gates (X, Y, Z) · Quantum Circuit Model · Hadamard Gate. Leads to. Controlled-U Gates · Controlled-Z Gate · SWAP Gate · Universal Gate Sets.

Ask the tutor: ask me to run any two-qubit state through CNOT, build a Bell or GHZ state step by step, or propagate a Pauli error through a stabilizer circuit.

Is CNOT just a quantum copy machine — doesn't it copy the control onto the target?

Only for classical inputs, and reading it that way is the fastest route to the no-cloning theorem. On a basis state $|c\rangle|0\rangle$ the output $|c\rangle|c\rangle$ does look like a copy, and that is exactly how CNOT builds parity and fan-out. But apply it to a superposed control $(\alpha|0\rangle+\beta|1\rangle)|0\rangle$ and you get $\alpha|00\rangle+\beta|11\rangle$ , which is not two copies of $\alpha|0\rangle+\beta|1\rangle$ — that would be $\alpha^2|00\rangle+\alpha\beta|01\rangle+\alpha\beta|10\rangle+\beta^2|11\rangle$ . Instead of duplicating the state, CNOT entangled it. This failure to clone an unknown superposition is not a defect of CNOT; it is the general no-cloning theorem showing through, and it is why CNOT copies bits but not qubits.

Which qubit is really the control, and can I swap the roles?

In the computational basis the control is the qubit whose value decides whether the target flips, and it passes through unchanged. But that asymmetry is a basis convention. Conjugating both qubits by Hadamard gives $(H\otimes H)\,\mathrm{CNOT}_{12}\,(H\otimes H)=\mathrm{CNOT}_{21}$ : in the $X$ basis (the $|+\rangle,|-\rangle$ frame) the roles are exactly reversed, and the former target now controls. Physically the clue is phase kickback — with the target in $|-\rangle$ , the "flip" turns into a phase on the control, $\mathrm{CNOT}\,|c\rangle|-\rangle=(-1)^c|c\rangle|-\rangle$ . So there is no absolute controller; CNOT is a symmetric entangling interaction that only looks one-sided in one particular basis.

Why does adding CNOT to single-qubit gates give a universal computer?

Single-qubit gates alone can only rotate each qubit independently — they never create correlations, so any circuit made of them keeps a product state a product state and cannot reach most of the $2^n$ -dimensional space. You need at least one entangling two-qubit gate to leave the product manifold, and CNOT is the canonical choice. The universality theorem (Barenco et al., 1995) shows that CNOT together with arbitrary single-qubit gates can build any $n$ -qubit unitary exactly, and combined with a discrete set like $\{H, T\}$ can approximate any unitary to arbitrary precision (Solovay–Kitaev). CNOT supplies the entanglement; the single-qubit gates supply the local orientation. Neither is universal without the other.

How is CNOT related to the controlled-Z gate, and why does hardware care?

They are the same gate dressed in different target bases: $\mathrm{CNOT}=(I\otimes H)\,\mathrm{CZ}\,(I\otimes H)$ , because the Hadamard conjugates $Z$ into $X$ . This matters because many platforms find CZ (or a close relative like iSWAP) easier to realize natively than CNOT — CZ is symmetric between its two qubits and often maps directly onto the physical interaction, such as a tunable coupler bringing two superconducting qubits into resonance. A compiler then wraps the hardware CZ in two Hadamards to present a CNOT to the algorithm. The two gates have identical entangling power, so the choice is purely about which one the physics hands you for free.

Does CNOT always create entanglement?

No — it only entangles suitable inputs. If the control is already in a definite computational-basis state, the output is a product state: $\mathrm{CNOT}\,|0\rangle|t\rangle=|0\rangle|t\rangle$ and $\mathrm{CNOT}\,|1\rangle|t\rangle=|1\rangle\,X|t\rangle$ . It also leaves the $X$ -basis eigenstate $|+\rangle|+\rangle$ completely alone. Entanglement requires the control to carry a genuine superposition of $|0\rangle$ and $|1\rangle$ while the target sits in a state like $|0\rangle$ that the two control branches send to distinguishable places. And even then the amount varies: a balanced control gives a full Bell pair (1 ebit), while the unbalanced $0.6/0.8$ control of the worked example gives only $0.943$ ebits. CNOT is an entangling gate, not an entangling guarantee.

Why do people say CNOT is the noisiest gate, and why does its count matter so much?

Because on essentially every quantum platform, entangling two qubits requires a stronger, slower, more delicate interaction than rotating one qubit in place. Single-qubit gates on the best 2020s hardware reach error rates around $10^{-4}$ ; two-qubit gates like CNOT typically sit near $10^{-3}$ or worse, and they take longer, giving decoherence more time to act. So the two-qubit-gate count sets both the dominant error accumulation and, through circuit depth, the exposure to noise. Compilers therefore treat CNOTs as the scarce resource — minimizing them, cancelling adjacent pairs, and paying three of them for every SWAP forced by limited connectivity. Pricing a quantum algorithm almost always means counting its CNOTs.