CNOT: The Workhorse

Single-qubit gates alone cannot do quantum computing.

The reason is simple: every single-qubit gate acts on one qubit at a time, independently of all the others. Apply an H to qubit 0, then an X to qubit 1, then a T to qubit 0 again — whatever you do, the two qubits stay independent. If they started in a product state |\alpha\rangle \otimes |\beta\rangle, they end in a product state U|\alpha\rangle \otimes V|\beta\rangle. You can rotate each qubit on its own little Bloch sphere as much as you like; they never become correlated in the way entanglement requires.

For quantum computing to deliver what it promises — for Shor's factoring algorithm to factor, for Grover's search to search, for teleportation to teleport — you need gates that couple the qubits, that let one qubit's state depend on another's. The canonical such gate, the first two-qubit gate every QC student meets, is CNOT: the controlled-NOT.

CNOT is the minimum-viable coupler. It does just enough to let one qubit influence another, and it does so in a way simple enough to analyse by hand but powerful enough to — together with single-qubit gates — do literally everything a quantum computer can do. By the end of this chapter you will know its truth table, its matrix, its circuit symbol, how it creates Bell states from product inputs, and why it earns its "workhorse" title.

What CNOT does — the classical story first

Start in classical computer-science land. A NOT gate flips a bit: 0 \to 1, 1 \to 0. A controlled-NOT has two inputs: a control bit and a target bit. The rule is:

• If the control is 0, leave the target alone.
• If the control is 1, flip the target.

That is the entire classical gate. In a truth table:

Notice what the control does: it is not changed by the gate. The target output is the XOR of the two inputs: target_out = control XOR target. So another name for CNOT is the reversible XOR gate — it computes the XOR of its two inputs and stores the answer in the target, while preserving the control so that the operation is reversible. (Classical XOR on its own erases one bit of information and is therefore irreversible; CNOT fixes that by keeping the control.)

Why reversibility matters here: quantum gates are always unitary, and unitary always means reversible. A classical XOR gate with one output destroys a bit. To lift it into a reversible gate — which CNOT is — you have to keep both inputs around. CNOT is the minimal reversible gate that computes XOR.

The quantum CNOT — same truth table, but on kets

The quantum CNOT has the same truth table as its classical cousin, but now the inputs and outputs are computational-basis kets of a two-qubit system.

Using the big-endian convention (leftmost character = qubit 0 = control, rightmost = qubit 1 = target):

Read the four: if the control qubit (left) is 0, the target qubit (right) is untouched. If the control is 1, the target flips. The two states |10\rangle and |11\rangle are the pair that actually moves; |00\rangle and |01\rangle are fixed.

Once you know the action on the four basis states, linearity handles every other state. For any superposition

you apply CNOT to each term and sum:

The amplitudes on |10\rangle and |11\rangle have swapped. That is CNOT on any two-qubit state, computed once and for all.

Why just "swap the amplitudes on |10\rangle and |11\rangle": CNOT is a permutation of the four basis states — it sends |10\rangle to |11\rangle and vice versa, leaving |00\rangle and |01\rangle fixed. Permuting basis states moves the amplitudes around. Since |00\rangle and |01\rangle do not move, their amplitudes stay put; since |10\rangle and |11\rangle swap, their amplitudes swap too.

The circuit symbol

In a quantum circuit, CNOT is drawn with two wires. The control wire has a filled dot. The target wire has an open circle with a plus sign — the \oplus symbol, the same one used for XOR. A vertical line connects them.

The asymmetry of the symbol matters. The filled dot is the control and the \oplus is the target — these roles are not interchangeable. CNOT from qubit 0 to qubit 1 (control on 0, target on 1) is a different gate from CNOT from qubit 1 to qubit 0 (control on 1, target on 0), and the two have different matrices. When you read a circuit, always check which wire has the filled dot and which has the \oplus.

The matrix — block form tells you the whole story

Now the linear-algebra picture. CNOT is a 4-by-4 unitary acting on the \{|00\rangle, |01\rangle, |10\rangle, |11\rangle\} basis. The columns of the matrix are the outputs of CNOT applied to each basis state, written as column vectors.

From the truth table:

• CNOT|00\rangle = |00\rangle → column 1 is (1, 0, 0, 0)^T.
• CNOT|01\rangle = |01\rangle → column 2 is (0, 1, 0, 0)^T.
• CNOT|10\rangle = |11\rangle → column 3 is (0, 0, 0, 1)^T.
• CNOT|11\rangle = |10\rangle → column 4 is (0, 0, 1, 0)^T.

Stack them as columns of a 4x4 matrix:

Reading the matrix. The top-left 2x2 block is the 2 \times 2 identity I — the "control = 0" part of the gate, where the target is untouched. The bottom-right 2x2 block is the Pauli-X matrix \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} — the "control = 1" part, where the target flips. The two off-diagonal 2x2 blocks are both zero.

This is the cleanest way to remember CNOT: it is block diagonal, with I in the top-left and X in the bottom-right.

You can also derive this block form abstractly using the projector decomposition of any controlled-U gate:

Why this formula works: the operator |0\rangle\langle 0| is the projector onto the subspace where qubit 0 is in state |0\rangle. On that subspace the gate acts as I on the target — i.e., does nothing. The operator |1\rangle\langle 1| is the projector onto qubit 0 = |1\rangle; on that subspace the gate acts as X on the target. The two projectors sum to the identity (|0\rangle\langle 0| + |1\rangle\langle 1| = I), so no state is double-counted or missed. Together, they split the two-qubit space into the "control-0 half" and the "control-1 half," and apply the right single-qubit gate to each half.

Expanded in the basis, |0\rangle\langle 0| \otimes I is a 4x4 matrix with I in the top-left and zeros elsewhere, and |1\rangle\langle 1| \otimes X is a 4x4 matrix with X in the bottom-right and zeros elsewhere. Adding them gives exactly the block-diagonal matrix above.

CNOT is its own inverse

Apply CNOT twice and you get the identity:

You can see this from the matrix — squaring a block-diagonal matrix with I and X on the diagonal gives I and X^2 = I on the diagonal, so the square is the full 4x4 identity. You can also see it from the truth table: swapping |10\rangle \leftrightarrow |11\rangle and doing it again brings every state back where it started. Equivalently, the classical XOR is its own inverse: (a \oplus b) \oplus b = a.

Why this matters in practice: if you accidentally insert an extra CNOT in a circuit, or if two consecutive CNOTs with the same control and target show up next to each other after some algebraic rearrangement, they cancel. Compilers look for exactly this pattern.

So \text{CNOT}^\dagger = \text{CNOT} — CNOT is self-adjoint (Hermitian) and unitary simultaneously. Its eigenvalues are therefore \pm 1, which makes it also a "reflection" in the space of two-qubit states.

The crucial example — CNOT creates entanglement

Here is what makes CNOT matter. On the computational basis, CNOT is essentially a classical gate (controlled-XOR). But quantum states are allowed to be superpositions, and when CNOT acts on a superposition, something remarkable happens: it can turn a product state into an entangled state.

Consider the input |+\rangle \otimes |0\rangle — qubit 0 in |+\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle), qubit 1 in |0\rangle. Write this out in the computational basis:

Now apply CNOT (control qubit 0, target qubit 1). Act term by term:

• \text{CNOT}|00\rangle = |00\rangle — the control is 0, target untouched.
• \text{CNOT}|10\rangle = |11\rangle — the control is 1, target flips.

So

This is one of the four Bell states — specifically the "phi-plus" state, the simplest maximally-entangled two-qubit state. It cannot be written as a product |\alpha\rangle \otimes |\beta\rangle: apply the cross-product test from the two-qubit basis states article — amplitudes are (1/\sqrt{2}, 0, 0, 1/\sqrt{2}), and \alpha_{00}\alpha_{11} = 1/2 while \alpha_{01}\alpha_{10} = 0. They differ, so no factorisation exists.

What just happened? A Hadamard put qubit 0 into a superposition — amplitudes split between |0\rangle and |1\rangle, with qubit 1 still definite at |0\rangle. The state at that point was a product: |+\rangle \otimes |0\rangle, no correlation between the two qubits. Then CNOT copied the control's value to the target in a very particular way — for the |0\rangle branch of the control, nothing happened; for the |1\rangle branch, the target flipped. The two branches ended up correlated: "control is 0 and target is 0" or "control is 1 and target is 1" — never a mix.

This correlation — this inability to write the joint state as a product — is what the word "entanglement" names. Single-qubit gates could not have produced it, because they act on each qubit independently. CNOT could, because its action on the target depends on the control. A gate whose action on one qubit depends on another qubit is an entangling gate. CNOT is the canonical example.

Why single-qubit gates alone cannot produce this: if U = U_0 \otimes U_1 is a product of single-qubit gates, then U|\alpha\rangle|\beta\rangle = (U_0|\alpha\rangle) \otimes (U_1|\beta\rangle) — still a product. Any sequence of single-qubit gates, even infinitely many, preserves the product structure of the state. Creating entanglement requires a gate that is not a simple tensor product.

Universality — CNOT plus single-qubit gates is all you need

Here is the theorem that earns CNOT the title "workhorse":

Theorem (universality). Any unitary operation on any number of qubits can be approximated, to arbitrary accuracy, by a finite sequence of CNOT gates and single-qubit gates.

This is the quantum analogue of the classical fact that any Boolean function can be built out of NAND gates alone. The set \{\text{CNOT}\} \cup \{\text{all single-qubit unitaries}\} is universal for quantum computation — nothing more is needed.

The theorem is proved in stages, each of which is addressed in its own chapter of the curriculum:

1. Any unitary on n qubits decomposes into two-qubit gates. An n-qubit unitary is a 2^n \times 2^n complex matrix — a lot of entries, but you can always reduce it to a product of "two-level" unitaries that affect only two basis states at a time. This step is pure linear algebra.
2. Any two-qubit unitary decomposes into CNOTs and single-qubit gates. At most three CNOTs plus a handful of single-qubit gates are needed to build any two-qubit unitary you can write down. This is the Khaneja-Brockett decomposition (1999).
3. Any single-qubit unitary decomposes into a finite set of gates (e.g., Clifford + T). This is the Solovay-Kitaev theorem — any single-qubit rotation can be approximated by a short sequence of H and T gates, with error decaying polylogarithmically in the sequence length.

Chain these three steps and you have a finite, efficient recipe for any quantum algorithm using only CNOTs and a small set of single-qubit gates. The fault-tolerant regime refines the single-qubit set to \{H, S, T\} — the Clifford+T set — for which high-quality error-corrected implementations exist.

Why universality matters: without it, you could imagine quantum computing being limited to a specific narrow class of operations. The universality theorem says there is no such limit — anything a quantum computer is allowed to do (any unitary evolution in principle), you can build out of the same handful of primitives. This is the analogue of the Church-Turing thesis for quantum circuits.

Contrast this with what happens if you remove CNOT and keep only single-qubit gates: you lose entanglement entirely, and along with it all the algorithmic speedups. Quantum computing without a coupling gate is just a tensor product of n independent single-qubit computations — no more powerful than n separate classical bits with complex amplitudes. CNOT is the piece that makes the whole enterprise work.

Control and target are not symmetric — the common mistake

A CNOT with control on qubit 0 and target on qubit 1 is a different gate from a CNOT with control on qubit 1 and target on qubit 0. The matrices are different, the circuits are different, and the outputs on a given input are generally different.

A compact way to see this: take two different input superpositions and watch.

Input A: |+\rangle \otimes |0\rangle with CNOT from qubit 0 to qubit 1 (we computed this above).

Input B: |0\rangle \otimes |+\rangle with CNOT from qubit 0 to qubit 1. Now qubit 0 is the control and it is definitely |0\rangle. The control is always off, so the target is always untouched — the gate does nothing:

Input A had the |+\rangle on the control wire and the CNOT turned it into an entangled Bell state. Input B had the |+\rangle on the target wire and the CNOT did nothing at all. Same gate, opposite behaviours — because the |+\rangle is on a different wire.

Now flip the CNOT's direction. Apply \text{CNOT}_{1 \to 0} (control on qubit 1, target on qubit 0) to Input B:

and \text{CNOT}_{1 \to 0} flips qubit 0 when qubit 1 is 1:

So \text{CNOT}_{1 \to 0} on |0\rangle|+\rangle gives the same Bell state that \text{CNOT}_{0 \to 1} gave on |+\rangle|0\rangle. The gates are related by swapping roles, but you have to swap the inputs accordingly — you cannot treat CNOT_{0 \to 1} and CNOT_{1 \to 0} as the same thing.

There is a nice identity that makes this formal: CNOT with the control and target interchanged equals a CNOT sandwiched between Hadamards on both wires. Symbolically,

This is one of the cleanest circuit identities in all of QC. You can prove it by checking all four basis states — a calculation that also reveals the role of the Hadamards in swapping the computational basis with the plus-minus basis.

Common confusions

• "CNOT is symmetric — just relabel the wires." No. CNOT with control on qubit 0 and target on qubit 1 is a different gate from the one with the roles swapped. The identity \text{CNOT}_{1 \to 0} = (H \otimes H)\,\text{CNOT}_{0 \to 1}\,(H \otimes H) makes the difference precise: to swap roles, you must conjugate by H on both wires.

• "CNOT entangles everything." No. CNOT creates entanglement when applied to appropriate inputs — typically, when the control is in a non-trivial superposition and the target is not equally in that superposition. CNOT on |00\rangle does nothing (|00\rangle stays |00\rangle). CNOT on |0\rangle|+\rangle does nothing. You need something like |+\rangle|0\rangle or a Hadamard on the control to kick off the entanglement.

• "CNOT copies the control onto the target." Only when the target starts in |0\rangle, and only on computational-basis inputs. For target |0\rangle, CNOT takes |a\rangle|0\rangle to |a\rangle|a\rangle — looks like copying. But for a superposition control like |+\rangle|0\rangle, the output is the Bell state |\Phi^+\rangle, not |+\rangle|+\rangle. The no-cloning theorem rules out a gate that copies an arbitrary quantum state; CNOT is not a cloner, even though it looks like one on the computational basis.

• "CNOT is fast because classical XOR is fast." No. On real quantum hardware, CNOT (or the native two-qubit gate the compiler translates it to) is typically the slowest and noisiest operation on the chip. IBM's superconducting processors have single-qubit gate fidelities near 99.9\% and two-qubit gate fidelities around 99\% — a whole order of magnitude worse. Every CNOT you insert is a substantial error-budget hit.

• "CNOT in the plus-minus basis works the same way." It does not. CNOT in the computational basis flips the target when the control is 1. But in the X-basis (the \{|+\rangle, |-\rangle\} basis), CNOT turns out to flip the control when the target is |-\rangle. This is the phase kickback phenomenon, central to Deutsch's algorithm and many others. The phrase "CNOT in the X basis" is worth learning and is covered in detail in the controlled-U gates article.

Going deeper

The CNOT-CZ identity

One of the most-used circuit identities in QC:

CZ (controlled-Z) is the gate that applies a Pauli Z to the target when the control is |1\rangle. It has matrix \text{diag}(1, 1, 1, -1) — the phase on |11\rangle picks up a minus sign. The identity says: sandwich a CZ between two Hadamards on the target wire and you get a CNOT.

You can derive the identity by expanding both sides on the computational basis and verifying agreement on all four states, or by noticing that H Z H = X — the Hadamard conjugates Z into X. Since CZ applies Z to the target on the control = 1 branch, the two Hadamards on the target turn that Z into an X, which is exactly what CNOT does.

This identity is load-bearing for hardware: CZ is the native two-qubit gate on many platforms (particularly newer transmon chips), and CNOT is then compiled as "H, CZ, H." The Hadamards are single-qubit gates, which are cheap; the CZ is the expensive two-qubit gate. So one CNOT costs one CZ on the hardware, not more.

CNOT in the stabiliser formalism

CNOT is a Clifford gate — a member of the group generated by \{H, S, \text{CNOT}\} that maps the set of Pauli operators to itself under conjugation. Specifically, for CNOT_{0 \to 1}:

Why these four relations matter: they are the complete specification of how CNOT acts on the Pauli group, which is enough (by the Clifford theorem) to compute how CNOT acts on any stabiliser state. Stabiliser states are a large, efficiently-simulable class of quantum states used as the starting point for quantum error correction. The surface code, Steane code, and every other major quantum error-correcting code is a stabiliser code, and CNOT plus measurement is the complete toolkit for syndrome extraction.

The Gottesman-Knill theorem tells us that circuits built only from Clifford gates and computational-basis measurements can be simulated efficiently on a classical computer. CNOT is therefore not the source of quantum speedup — the speedup comes from the non-Clifford gates (like T) that you have to add to achieve universality. But CNOT is the entangling glue that makes the Clifford part of error correction possible in the first place.

The hardware reality — CNOTs are slow and noisy

On every major quantum hardware platform, the CNOT gate (or the platform's native two-qubit gate) is the dominant source of errors.

Every "99.5% fidelity" number hides the fact that in a 100-CNOT circuit, the cumulative error is 1 - 0.995^{100} \approx 0.39 — a coin-flip's worth of reliability. This is why every modern QC compiler (Qiskit transpiler, Cirq router, Braket compiler, Azure Quantum) spends most of its optimisation time reducing CNOT count. Each CNOT you save is an exponential in the tail of the reliability curve.

On Indian hardware efforts — TIFR Mumbai's superconducting group, IIT Madras's trapped-ion group, and the broader National Quantum Mission ecosystem — the same trade-offs hold. The calibration and pulse engineering needed to push two-qubit fidelities from 99% to 99.9% is among the most labour-intensive parts of running a quantum device.

CNOT in Shor's factoring algorithm

A small scale-calibrating example. Shor's algorithm for factoring a 2048-bit RSA key requires, in its modular-exponentiation subroutine, on the order of 10^{10} to 10^{11} CNOTs (the exact count depends on the implementation). At 99.9% two-qubit fidelity, the probability of the circuit completing without any gate errors is 0.999^{10^{10}} \approx e^{-10^7} — effectively zero.

This is why fault-tolerant quantum computing with error correction is required for Shor. Each "logical CNOT" is implemented as many physical CNOTs within an error-corrected block (typically hundreds to thousands of physical CNOTs per logical CNOT on the surface code), and the error correction keeps the logical error rate exponentially small even as the physical gate count grows. A 2048-bit RSA factorisation is currently estimated to need roughly 20 million physical qubits assuming surface-code error correction with physical CNOT fidelity around 99.9% — orders of magnitude beyond today's 100-qubit devices.

The takeaway: CNOT is the workhorse at every level — in the algorithm (the glue that creates entanglement), in the compiler (the resource to minimise), and in the hardware roadmap (the primitive whose fidelity and gate time determine the timeline to useful QC). Every other two-qubit gate you will meet in this curriculum — CZ, CH, controlled-U, Toffoli, SWAP — is either a close cousin of CNOT or is built out of CNOTs.

Where this leads next

• Controlled-U gates — generalising CNOT to apply any single-qubit unitary U when the control is |1\rangle.
• Bell states — the four maximally-entangled two-qubit states; CNOT-plus-Hadamard is the standard preparation circuit.
• Entanglement defined — what it means for a state to be non-factorisable and why CNOT is the prototypical entangler.
• SWAP and iSWAP — SWAP is built from three CNOTs; iSWAP is a hardware-native cousin.
• Toffoli gate — the three-qubit controlled-controlled-NOT, built out of CNOTs, and the gate that makes quantum computers universal for classical computation as well.
• Two qubits, four basis states — the computational basis and the product-vs-entangled test that we used to check that |\Phi^+\rangle is entangled.

References

1. Nielsen and Chuang, Quantum Computation and Quantum Information (2010), §4.3 (two-qubit gates and universality) — Cambridge University Press.
2. John Preskill, Lecture Notes on Quantum Computation, Ch. 4 and 6 — theory.caltech.edu/~preskill/ph229.
3. Barenco et al., Elementary gates for quantum computation (1995) — the paper that proved CNOT + single-qubit gates is universal. arXiv:quant-ph/9503016.
4. Qiskit Textbook, Multiple Qubits and Entangled States — CNOT with worked runnable examples.
5. IBM Quantum Learning, Entanglement in Action — CNOT and Bell states on real hardware.
6. Wikipedia, Controlled NOT gate — the matrix form, truth table, and circuit identities.