Classical bits, gates, and reversibility

Before we generalize anything, let us be precise about the thing we are generalizing. A classical computer is built from logic gates on bits - AND, OR, NOT - and you already know exactly how they behave. This lesson takes that familiar model and pulls out the one property quantum computing will insist on: every gate must be able to run backward.

A gate is just a rule that maps an input bitstring to an output bitstring. The question that will matter for the rest of the course is simple: given only the output, can you always recover the input? Play with the bench below. Pick a gate, read its truth table, then click any output value to run the gate backward and see how many inputs could have produced it.

The bench sorts every gate into one of two piles. For AND and OR, several inputs land on the same output - AND sends $00$, $01$ and $10$ all to $0$ - so when you try to run it backward the output cannot tell you which input it came from. That lost information is what makes the gate one-way. For NOT, CNOT and Toffoli, every input has its own private output, so running backward is never ambiguous.

Reversible means bijection

We can make "runs backward" exact. A gate on $n$ bits is a function from the $2^n$ possible inputs to outputs on the same $n$ bits. It is reversible exactly when no two distinct inputs share an output. But a function from a finite set to itself that never collides must also hit every output - if the $2^n$ inputs map to $2^n$ distinct outputs, they use up all of them. So reversibility is the same as being a bijection, a perfect one-to-one pairing:

This is why AND can never be a quantum gate: it takes two bits to one, so it cannot even be a map from a set to itself, let alone a bijection. NOT is the simplest reversible gate (it just swaps $0$ and $1$). CNOT takes two bits to two bits and flips the second whenever the first is $1$; on the basis states it copies the first bit onto a blank second bit, and it is its own inverse. Toffoli takes three bits to three, flipping the last only when the first two are both $1$.

def is_reversible(gate, n_in):
    outputs = [gate(x) for x in range(2 ** n_in)]
    # reversible exactly when no two inputs share an output
    return len(set(outputs)) == len(outputs)

AND = lambda x: (x >> 1) & (x & 1)          # 2 bits in, 1 bit out
NOT = lambda x: x ^ 1                        # 1 bit, flips it
CNOT = lambda x: (x & 0b10) | (((x >> 1) ^ x) & 1)  # flip low bit if high bit set

print(is_reversible(AND, 2))   # False  -> 00, 01, 10 all map to 0
print(is_reversible(NOT, 1))   # True
print(is_reversible(CNOT, 2))  # True   -> a bijection on two bits

Check yourself