Two-Qubit Gates and the CNOT

A controlled gate takes a single-qubit unitary $U$ and promotes it to a two-qubit (or multi-qubit) operation: apply $U$ to a target qubit only if a control qubit is in state $|1\rangle$, and do nothing if the control is $|0\rangle$. Formally, on computational basis states of the control,

The CNOT (controlled-NOT, also written $\text{CX}$) is the special case $U = X$, the Pauli bit-flip. Since $X|0\rangle = |1\rangle$ and $X|1\rangle = |0\rangle$, CNOT is the quantum lift of the classical operation "flip $t$ if $c = 1$," which is exactly bitwise XOR: the truth table maps $(c,t) \mapsto (c,\, t \oplus c)$. The crucial subtlety, and the reason this gate deserves an entire article, is that quantum control is defined by linearity, not by "looking at" the control qubit and branching classically. When the control qubit is in a superposition $\alpha|0\rangle + \beta|1\rangle$, CNOT does not measure it and pick a branch; it applies the linear extension of the two basis rules above to the full two-qubit state. This linear extension of a classical-looking rule is exactly what produces entanglement, a phenomenon with no classical analogue. A gate that only ever acted on product states one qubit at a time — no matter how cleverly chosen — could never create the correlations that make $\text{CNOT}(H\otimes I)|00\rangle$ a Bell state instead of a product state.

Convention. We write two-qubit basis states as $|c\rangle|t\rangle = |ct\rangle$ with the control qubit listed first, matching the usual circuit diagrams and Nielsen–Chuang ordering. Some tools use the opposite convention, so always check which wire is the control before reading a matrix off a textbook.

Truth table (basis states):

Matrix. Ordering basis vectors as $|00\rangle, |01\rangle, |10\rangle, |11\rangle$, CNOT is

The top-left $2\times2$ identity block acts on the $c=0$ subspace (do nothing); the bottom-right anti-diagonal block is exactly the Pauli $X$ matrix acting on the target when $c=1$. This block structure is the matrix expression of "apply $I$ or $X$ to the target, conditioned on the control," and it generalizes immediately: replace the $X$ block with any $2\times 2$ unitary $U$ to get the matrix for controlled-$U$,

Circuit symbol. CNOT is drawn as a solid dot on the control wire connected by a vertical line to a $\oplus$ (circled plus) symbol on the target wire. Controlled-$U$ replaces the $\oplus$ with a boxed $U$.

Algorithm view. Treat CNOT as a subroutine that acts on a 4-dimensional amplitude vector, exactly the way any gate is simulated on a classical computer for testing and small-scale verification. ```

# Simulating CNOT on a 2-qubit state vector

# state is a length-4 complex array indexed by integer c*2 + t

# (c = control bit, t = target bit), i.e. amplitude order |00>,|01>,|10>,|11> function APPLY_CNOT(state, control_index, target_index): new_state = copy(state) for index in 0 .. 3: c = bit(index, control_index) # extract control bit of this basis label t = bit(index, target_index) # extract target bit of this basis label if c == 1: flipped_index = index XOR (1 << target_index) # flip only the target bit new_state[flipped_index] = state[index] else: new_state[index] = state[index] return new_state

# Generalization: controlled-U on a target qubit, U given as a 2x2 unitary matrix function APPLY_CONTROLLED_U(state, control_index, target_index, U): new_state = copy(state) for index in 0 .. 3: c = bit(index, control_index) if c == 0: new_state[index] += state[index] # untouched branch else: t = bit(index, target_index) i0 = index with target bit set to 0 i1 = index with target bit set to 1

# only accumulate once per (i0,i1) pair; shown here for the t=0 half if t == 0: new_state[i0] = U[0][0]state[i0] + U[0][1]state[i1] new_state[i1] = U[1][0]state[i0] + U[1][1]state[i1] return new_state ``` The first routine is just a permutation of amplitudes — no arithmetic beyond bookkeeping — which is why CNOT is cheap to simulate and, on hardware, implementable as a native two-qubit interaction. The second routine shows the general pattern: leave the $c=0$ block alone, and apply the $2\times2$ unitary $U$ to the amplitude pair indexed by the target qubit whenever $c=1$.

Notice in the diagram that the control qubit starts in the classical state $|1\rangle$, but the target starts in superposition $|+\rangle = (|0\rangle+|1\rangle)/\sqrt2$ produced by a Hadamard gate. Applying CNOT to $|1\rangle|+\rangle$ produces $(|11\rangle + |10\rangle)/\sqrt2$, which after relabeling is exactly an entangled Bell-type state — a preview of The Bell States.

Unitarity and reversibility. CNOT's matrix is a real permutation matrix: every row and column has exactly one $1$ and the rest $0$s. Permutation matrices are always orthogonal, hence unitary ($\text{CNOT}^\dagger \text{CNOT} = I$), and CNOT is its own inverse since applying the same flip rule twice restores the target bit: $t \oplus c \oplus c = t$. This matches the general requirement that every quantum gate be unitary, guaranteeing reversibility and no loss of quantum information — a strictly stronger constraint than the reversibility of classical logic gates like XOR, because unitarity must hold for every superposition, not just classical bit inputs.

Why controlled-$U$ is always unitary. Write $\text{controlled-}U = |0\rangle\langle0|\otimes I + |1\rangle\langle1|\otimes U$. Since $|0\rangle\langle0|$ and $|1\rangle\langle1|$ are orthogonal projectors summing to identity, and $I$, $U$ are each unitary,

The cross terms vanish because $\langle0|1\rangle = 0$. So controlled-$U$ is unitary for any unitary $U$, not just $X$ — this is why the construction generalizes so cleanly.

Why CNOT entangles. Take the control in superposition $\alpha|0\rangle + \beta|1\rangle$ and the target in $|0\rangle$. Linearity gives

Claim: this state cannot be written as a tensor product $|\phi\rangle\otimes|\chi\rangle$ whenever $\alpha,\beta \neq 0$. Suppose it could: $(\phi_0|0\rangle+\phi_1|1\rangle)\otimes(\chi_0|0\rangle+\chi_1|1\rangle) = \phi_0\chi_0|00\rangle+\phi_0\chi_1|01\rangle+\phi_1\chi_0|10\rangle+\phi_1\chi_1|11\rangle$. Matching coefficients against $\alpha|00\rangle+0\cdot|01\rangle+0\cdot|10\rangle+\beta|11\rangle$ forces $\phi_0\chi_1=0$ and $\phi_1\chi_0=0$, while $\phi_0\chi_0=\alpha\neq0$ and $\phi_1\chi_1=\beta\neq0$ (both nonzero, both factors of a product state). The first two equations force either $\phi_0=0$ or $\chi_1=0$, and either $\phi_1=0$ or $\chi_0=0$ — but any such choice contradicts $\phi_0\chi_0\neq0$ and $\phi_1\chi_1\neq0$ simultaneously. No consistent assignment exists, so the state is not separable: CNOT applied to a superposed control genuinely entangles the two qubits. This is a full proof, not a hand-wave, and it is the precise sense in which "controlled gates create entanglement."

Time and space complexity. Simulating CNOT on a classical computer costs $O(1)$ arithmetic operations per basis-state amplitude touched, since it is a fixed permutation of a 4-entry table; on $n$ qubits embedded in a $2^n$-dimensional state vector, applying CNOT to two of the $n$ wires costs $O(2^n)$ time (touch every amplitude once) and $O(1)$ extra space if done in place, because it only swaps amplitude pairs that differ in the target bit whenever the control bit is 1. This is the same asymptotic cost as any other single fixed two-qubit gate; the exponential blow-up is inherent to full state-vector simulation, not to CNOT specifically. On real hardware, CNOT (or an equivalent native two-qubit entangling gate such as the cross-resonance gate or the Mølmer–Sørensen gate) executes in constant time — one hardware pulse or pulse sequence — independent of $n$, which is the entire point of building a quantum device rather than simulating one.

The tradeoff to be honest about. Two-qubit gates are the accuracy bottleneck of near-term hardware: single-qubit gate fidelities on leading platforms often exceed 99.9%, while two-qubit gate fidelities typically trail at 99–99.9%, because entangling interactions require precise coupling between physical qubits and are more sensitive to crosstalk and calibration drift. Circuit depth in two-qubit gates, not single-qubit gate count, is usually the dominant source of error in a real quantum computation, which is why compilers aggressively minimize CNOT count when mapping abstract circuits to hardware topology.

Setup. Prepare qubit 1 (control) in $|0\rangle$ and apply $H$; prepare qubit 2 (target) in $|0\rangle$ and leave it. Then apply CNOT with qubit 1 as control, qubit 2 as target. This is the standard Bell-state recipe. Step-by-step amplitude trace, using basis order $|00\rangle,|01\rangle,|10\rangle,|11\rangle$:

Reading off the matrix action directly: CNOT leaves the $|00\rangle$ amplitude alone (control bit 0), and sends the $|10\rangle$ amplitude to the $|11\rangle$ slot (control bit 1, target flips $0\to1$). The result, $\frac{1}{\sqrt2}(|00\rangle+|11\rangle)$, is the Bell state $|\Phi^+\rangle$ — the canonical maximally entangled two-qubit state, foreshadowing The Bell States directly.

A second, less symmetric trace to show the general controlled-$U$ mechanics rather than just this famous special case. Let the control qubit be in $|1\rangle$ and the target qubit start in $|1\rangle$, but apply controlled-$H$ (control $=$ qubit 1, target $=$ qubit 2, $U = H$) instead of CNOT.

Check separability here: this state factors as $|1\rangle \otimes \frac{1}{\sqrt2}(|0\rangle-|1\rangle)$, a product state, because the control started in a definite basis state $|1\rangle$ rather than a superposition. This confirms the correctness argument above precisely: entanglement requires the control to be in superposition before the controlled gate acts. A controlled-$U$ gate applied to a classical control value never entangles; it merely selects a branch, exactly like classical conditional execution.

The controlled-NOT gate is not attributed to a single discoverer in the way a named theorem might be; it emerged from the reversible-computing and quantum-information communities converging on the same construction from different directions, once quantum circuit models crystallized in the 1980s and 1990s.

CNOT and controlled-$U$ gates are the entangling primitive inside essentially every non-trivial quantum protocol. Quantum teleportation and superdense coding both use a CNOT-plus-Hadamard pair to prepare and later disentangle a Bell pair, exactly the construction shown in the worked example above. Quantum error-correcting codes such as the surface code, used in Google's and IBM's roadmaps toward fault tolerance, rely on layers of CNOTs to spread a single logical qubit's information redundantly across many physical qubits and to extract error syndromes without collapsing the encoded state. Shor's algorithm and Grover's algorithm both compile down, in their circuit-level descriptions, to sequences dominated by controlled operations acting on superposed registers — this is literally where their quantum advantage comes from. On real hardware, the CNOT is rarely implemented directly as drawn; it is compiled from whichever two-qubit interaction is physically native to the device. Superconducting qubits (IBM, Google, Rigetti) typically implement a cross-resonance or CZ-type interaction and synthesize CNOT from it using single-qubit rotations; trapped-ion systems (IonQ, Quantinuum) use the Mølmer–Sørensen gate, which entangles pairs (or larger groups) of ions via shared motional modes; photonic and neutral-atom platforms use their own native entangling mechanisms. In every case, quantum compilers translate the abstract CNOT gates that appear in a written circuit into the native gate set of the target device, and minimizing this translated two-qubit gate count is one of the central optimization problems in real-world quantum compiler engineering. Understanding CNOT precisely — its matrix, its entangling behavior, its cost — is therefore not just a theoretical exercise but the direct prerequisite for reading any quantum hardware benchmark or circuit diagram.

Ask the tutor: How does chaining multiple CNOT and controlled-U gates let you build arbitrary multi-qubit entangled states from a simple starting register?