How Do Toffoli and Fredkin Gates Stay Reversible?

Reversible logic gates such as the Toffoli and Fredkin gates preserve a one-to-one mapping between input states and output states by ensuring that no information is erased during computation. Unlike standard classical gates that combine multiple inputs into a single output, reversible gates maintain an equal number of input and output wires and permute the possible bit strings. This structure allows any output state to be uniquely traced back to its exact input state.

Why Standard Logic Gates Lose Information

In conventional classical computing, gates like AND, OR, and NAND are logically irreversible. An AND gate takes two input bits and produces one output bit. Because there are four possible input combinations (\(00\), \(01\), \(10\), and \(11\)) and only two possible output values (\(0\) and \(1\)), multiple inputs must map to the same output. For example, an output of \(0\) could have come from \(00\), \(01\), or \(10\). Once the gate executes, the original input state cannot be uniquely reconstructed from the output alone.

To achieve reversibility, a logic gate must implement a bijective function—a one-to-one and onto mapping—between the set of \(n\)-bit input states and the set of \(n\)-bit output states. Every distinct input must produce a distinct output, which requires the number of output bits to equal the number of input bits.

How the Toffoli Gate Preserves a One-to-One Mapping

The Toffoli gate, also known as the Controlled-Controlled-NOT (CCNOT) gate, is a universal three-bit reversible gate. It takes three input bits, \((A, B, C)\), and produces three output bits, \((A', B', C')\), defined by the following transformation:

\[A' = A\] \[B' = B\] \[C' = C \oplus (A \land B)\]

Here, \(\oplus\) denotes the bitwise XOR operation and \(\land\) denotes the logical AND operation. The first two bits, \(A\) and \(B\), act as control bits and pass through the gate unchanged. The third bit, \(C\), is the target bit, which is flipped if and only if both \(A\) and \(B\) are equal to \(1\).

Because the control bits \(A\) and \(B\) are preserved in the output, you can always determine whether the target bit \(C\) was flipped. In fact, applying the Toffoli gate a second time to its own output restores the original input:

\[(C \oplus (A \land B)) \oplus (A \land B) = C\]

Since the gate is its own inverse, every one of the \(2^3 = 8\) possible three-bit input states maps to a unique three-bit output state, guaranteeing a strict one-to-one correspondence.

How the Fredkin Gate Preserves a One-to-One Mapping

The Fredkin gate, also known as the Controlled-SWAP (CSWAP) gate, is another universal three-bit reversible gate. It takes three input bits, \((A, B, C)\), and produces three output bits, \((A', B', C')\). The bit \(A\) acts as the control bit, while \(B\) and \(C\) are target bits:

  • If \(A = 0\), the output is \((A, B, C)\) (no change).
  • If \(A = 1\), the output is \((A, C, B)\) (the bits \(B\) and \(C\) are swapped).

Mathematically, this can be written as:

\[A' = A\] \[B' = (\neg A \land B) \lor (A \land C)\] \[C' = (\neg A \land C) \lor (A \land B)\]

Just like the Toffoli gate, the Fredkin gate preserves its control bit \(A\) in the output. Knowing \(A'\) immediately tells you whether a swap occurred. Applying the Fredkin gate a second time swaps \(B'\) and \(C'\) back if \(A = 1\), or leaves them untouched if \(A = 0\). Therefore, the Fredkin gate is also its own inverse and forms a bijection over all \(8\) three-bit states. Additionally, the Fredkin gate is conservative, meaning it preserves the number of \(1\)s (the Hamming weight) between the input and the output.

The Role of Ancilla Bits in Reversible Circuits

By keeping control bits intact and using invertible operations like XOR and conditional swapping, Toffoli and Fredkin gates ensure that no two distinct inputs ever collide on the same output. When building larger classical circuits from these gates, extra constant-initialized wires called ancilla bits are often added to hold intermediate values or copy outputs, ensuring that the entire circuit maintains a one-to-one mapping from start to finish.