13. Classical Logic: Reversible Computing

Classical Logic: Reversible Computing

This is the final conceptual hurdle before we enter the quantum realm proper. You need to unlearn how you think about memory.

In classical coding, you are used to variables being overwritten.

x = 5
x = x + 1  // The old '5' is gone

In Quantum Computing, you cannot overwrite data. This isn't just a rule; it's a law of physics. Because quantum operators are unitary (probability conserving), they must be reversible. If you erase information, you break the unitarity, and the quantum state collapses or decoheres.

1. Landauer's Principle: Information is Physical

Why does this matter? Rolf Landauer proved that erasing information (irreversible computing) necessarily dissipates heat.

$$E \ge k_B T \ln 2$$

Every bit you "delete" costs energy.

Quantum computers must operate with effectively zero energy dissipation during the calculation to maintain the delicate quantum state. Therefore, every step must be logically reversible.

2. The Consequence: "Garbage" Accumulation

Because you can't throw away intermediate data, quantum algorithms generate a massive amount of "Garbage Qubits" (ancilla bits holding intermediate results).

If you compute $f(x)$ using temporary registers, you end up with:

$$|x\rangle \to |x\rangle |g(x)\rangle |f(x)\rangle$$

where $|g(x)\rangle$ is the garbage left over from the calculation.

The Trap: If you leave this garbage entangled with your result, it acts like a "measurement" by the environment. It will kill the interference pattern you are trying to create. You must clean it up.

3. The Solution: Uncomputation

How do you delete data without "deleting" it? You run the circuit in reverse.

The standard pattern for a clean quantum calculation is:

1. Compute: Calculate the result into a blank target register.
   $(|x\rangle, |0\rangle, |0\rangle) \xrightarrow{U} (|x\rangle, |g\rangle, |f(x)\rangle)$
2. Copy: Copy the answer to a safe "readout" register (usually via CNOTs).
   $(|x\rangle, |g\rangle, |f(x)\rangle, |0\rangle) \to (|x\rangle, |g\rangle, |f(x)\rangle, |f(x)\rangle)$
3. Uncompute: Apply the inverse of the compute operation ($U^\dagger$). This reverses the calculation of the garbage and the original result, returning the working registers to zero.
   $(|x\rangle, |g\rangle, |f(x)\rangle, |f(x)\rangle) \xrightarrow{U^\dagger} (|x\rangle, |0\rangle, |0\rangle, |f(x)\rangle)$

Now you have the clean result $|f(x)\rangle$ and empty working space, without having thermally erased anything.

Reversible compute–copy–uncompute pattern.

Your Task: The Uncomputation Workflow

You have a circuit $U$ that takes input $x$ and a workspace $0$, and produces $(x, x \oplus 1)$.

$$U(x, 0) \to (x, x \oplus 1)$$

You want to isolate the result $x \oplus 1$ and return the workspace to $0$.

1. Step 1 (Compute): Prepare the input qubit to $|1\rangle$ (apply X on q0). Build U using CNOT(control q0, target q1) then X on q1. What is the state?
2. Step 2 (Copy): Apply a CNOT where the "work" qubit q1 is the control and a new third qubit q2 (initialized to $|0\rangle$) is the target. What is the state of the three qubits?
3. Step 3 (Uncompute): Apply $U^\dagger$ (the inverse of U) to the first two qubits: X on q1 then CNOT(control q0, target q1). What is the final state?

Hint: U is its own inverse.