Reversible Computation

Every quantum gate is unitary. That means it pairs each input with exactly one output, and it can always be run backwards. So a circuit can never merge two different inputs into the same output. Normal logic, such as AND, throws information away. Before a quantum circuit can do AND, it must be rebuilt in a reversible form. Usually a Toffoli gate writes the answer onto an extra qubit, and the inputs survive.

Why must quantum logic be reversible?

Why care? This rule shapes every quantum program you will ever write. It is why quantum circuits need extra qubits, and why they clean up after themselves.

Every gate in a quantum circuit is a unitary operation. That is a change that keeps the total chance at 100% and always has an exact inverse, a step that reverses it. Run the gate, then run its inverse, and you are back exactly where you started. No exceptions.

One result follows right away. A unitary gate is a one-to-one mapping. (Mathematicians call it a bijection.) Two different starting states can never end up as the same final state. If they did, the inverse would have no way to tell them apart.

Normal logic breaks this rule all the time. Take AND. It outputs 1 only when both inputs are 1. Let's count the cases in its truth table:

(0,0) gives 0.
(0,1) gives 0.
(1,0) gives 0.
(1,1) gives 1.

Four different inputs squeeze into two outputs. Suppose someone hands you the output 0. You can't say which of three inputs made it. The information is destroyed.

Think of blending fruit into a smoothie. Lots of fruit mixes can give the same pink drink, and you can't un-blend it. A quantum gate is more like shuffling a deck of cards in a set way. Every card lands in exactly one new spot, so you can always shuffle back.

No unitary matrix can do that merge directly. (A matrix is just the table of numbers that writes down what a gate does to each amplitude.) So AND, OR and every other operation that loses information must be rebuilt in a reversible form. Only then can it live inside a quantum circuit.