Unitaries Are Reversible

You have spent this course mastering classical reversible gates — bijections on bit-strings, drawn as two-column truth tables where every output row is hit exactly once. Somewhere else you learned that a quantum gate is a unitary matrix. This lesson is where the two subjects turn out to be the same subject. The dictionary is one line long:

\text{classical reversible gate} \;=\; \text{permutation matrix} \;\subset\; \text{unitary matrix} \;=\; \text{quantum gate.}

Every classical reversible circuit you have built is already a quantum circuit — it can run, unchanged, on quantum hardware. And the containment runs one way only: quantum mechanics offers a whole continuum of gates beyond the permutations, but it cannot offer even a single irreversible one. Reversibility is not a design taste in the quantum world; it is a law of physics.

A reversible gate is a permutation matrix

A classical reversible gate on n bits is a bijection on the 2^n bit-strings — a permutation of the set \{0,1\}^n. To turn that combinatorial object into a matrix, encode each bit-string as a basis vector of a 2^n-dimensional space (the computational basis, exactly as in the formal postulates of quantum mechanics). The gate becomes a 2^n \times 2^n permutation matrix: a 0/1 matrix with exactly one 1 in every row and every column. Column j says where basis state j goes.

The smallest example is NOT, whose matrix is the Pauli X:

\mathrm{NOT} = X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad X|0\rangle = |1\rangle,\; X|1\rangle = |0\rangle.

One size up, CNOT permutes the four two-bit states — it swaps |10\rangle and |11\rangle and fixes the other two:

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

in the ordered basis |00\rangle, |01\rangle, |10\rangle, |11\rangle. The top-left 2\times 2 block is the identity (control 0: do nothing); the bottom-right block is X (control 1: flip the target). One 1 per row, one per column — a permutation matrix, as a reversible truth table demands.

Permutation matrices are unitary

Recall what unitarity means: U^\dagger U = I, equivalently the columns of U form an orthonormal set, equivalently U is invertible with

U^{-1} = U^\dagger.

Now look at a permutation matrix through that lens. Its columns are distinct standard basis vectors — each has a single 1, and no two columns put their 1 in the same row (that would mean two inputs mapping to the same output, which a bijection forbids). Distinct standard basis vectors are automatically orthonormal: each has length 1, and any two are orthogonal. So every permutation matrix is unitary, and every classical reversible gate is a legal quantum gate. No translation, no approximation — the very same matrix.

Verify it for CNOT. CNOT is real and symmetric, so \mathrm{CNOT}^\dagger = \mathrm{CNOT}, and the unitarity check U^\dagger U = I becomes a single matrix multiplication:

\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} = I_4.

Check one entry by hand to feel the mechanism: the (3,3) entry of the product is row 3 of the left factor dotted with column 3 of the right factor, (0,0,0,1)\cdot(0,0,0,1) = 1 — the third column, sent to the fourth slot and back again. Algebraically this is the statement you already knew from the truth table: CNOT is its own inverse, \mathrm{CNOT}^2 = I, so applying it twice rewinds it.

Worked example: the Toffoli, as an 8×8 permutation

The Toffoli gate flips its third bit when both controls are 1 — it swaps |110\rangle \leftrightarrow |111\rangle and fixes the other six basis states. In the ordered basis |000\rangle,\dots,|111\rangle its matrix is

\mathrm{TOFF} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}.

The structure is a 6\times 6 identity block (both controls are not 1: leave everything alone) with a lone X block in the bottom-right corner — the swapped pair of rows that is the controlled-controlled-NOT. Eight columns, eight distinct standard basis vectors, orthonormal: unitary. The gate that makes classical reversible logic universal is, without modification, a quantum gate — a fact the next lesson leans on hard.

The containment picture

So \{\text{permutation matrices}\} \subset \{\text{unitary matrices}\}, and both inclusions of that sentence carry a message.

Everything classical-reversible is inside. Any circuit of NOT, CNOT, SWAP, Toffoli and Fredkin gates is a product of permutation matrices, hence a permutation matrix, hence unitary. Your entire reversible-synthesis toolbox ships to quantum hardware as-is.
The extra room is a continuum. Permutation matrices are a finite set ((2^n)! of them); unitaries form a continuous group. The simplest non-permutation unitary is the Hadamard, H = \tfrac{1}{\sqrt2}\begin{psmallmatrix} 1 & 1 \\ 1 & -1 \end{psmallmatrix}: its columns are orthonormal, so it is unitary, but its entries are not 0s and 1s — it sends the basis state |0\rangle to the superposition \tfrac{1}{\sqrt2}(|0\rangle + |1\rangle). That extra room is exactly what buys superposition and, with signed amplitudes, interference — the two resources classical reversible circuits lack.
Nothing irreversible gets in at all. A unitary is invertible by definition (U^{-1} = U^\dagger), so quantum mechanics simply has no way to write an irreversible gate. There is no unitary AND: AND sends the distinct basis states |00\rangle, |01\rangle, |10\rangle to states with the same output bit, so any matrix implementing it would repeat a column — and repeated columns can never be orthonormal. The "merge" in AND's truth-table funnel is the algebraic failure of unitarity.

a classical reversible gate on n bits is a permutation of the 2^n basis states — a 2^n \times 2^n permutation matrix (one 1 per row and column);
every permutation matrix is unitary: its columns are distinct standard basis vectors, hence orthonormal, so U^\dagger U = I and U^{-1} = U^\dagger;
therefore every classical reversible circuit is already a quantum circuit — unchanged;
the containment is strict: unitaries such as H are not permutations (they create superpositions), and no unitary is irreversible — there is no unitary AND.

Unitarity is not an axiom chosen for elegance — it is forced by probability. A closed quantum system evolves by |\psi\rangle \mapsto U|\psi\rangle, and the total probability of all outcomes, \langle\psi|\psi\rangle, must stay equal to 1 forever. The linear maps that preserve \langle\psi|\psi\rangle for every state are exactly the unitaries. In continuous time the same statement reads U = e^{-iHt} for a Hermitian Hamiltonian H — Schrödinger's equation, exponentiated. So the slogan of this whole course — physics does not forget — is, in the quantum formalism, literally the statement that time evolution has an inverse: run U^\dagger and history rewinds. The thermodynamic arguments of the foundations module and the linear algebra of this page are two languages for one fact.

The dictionary tempts a false converse: "quantum gates are reversible, classical reversible gates are reversible, so they're the same thing." No. Classical reversible gates are the permutations — a finite, rigid skeleton inside a continuum. The Hadamard has no classical counterpart at all: ask for its truth table and the question is malformed, because H|0\rangle is not a bit-string but the superposition \tfrac{1}{\sqrt2}(|0\rangle+|1\rangle). A classical reversible computer is a quantum computer that never leaves the computational basis; a quantum computer is a reversible computer with the whole unit sphere to move through. Everything classical reversible circuits can do, quantum circuits can do — and the reverse fails the moment a single H appears.