Uncomputation

Quantum gates are reversible: every operation has an inverse, and running a circuit backwards undoes it exactly. This property is not just a curiosity — it is the foundation of uncomputation, the technique that makes large quantum algorithms practical.

Why uncomputation matters

Many algorithms compute a value into an ancilla (helper) qubit and then need that ancilla reset to $|0\rangle$ so it can be reused or so it does not entangle with the rest of the state. If the ancilla is left in a non- $|0\rangle$ state — or, worse, entangled with the data register — it becomes garbage that leaks information about the computation and destroys interference.

The fix is always the same: after using the ancilla's value, apply the exact inverse sequence of gates that produced it. Because every gate is unitary, the inverse of a gate $U$ is its conjugate transpose $U^\dagger$ , and the inverse of a sequence $U_1 U_2 \cdots U_k$ is

$U_k^\dagger \cdots U_2^\dagger U_1^\dagger.$

The Toffoli as an AND gate

The Toffoli (CCX) gate sets its target qubit to $\text{target} \oplus (\text{ctrl}_1 \wedge \text{ctrl}_2)$ . Starting with the target in $|0\rangle$ , this computes the classical AND of the two controls:

$\text{CCX}\,|c_1, c_2, 0\rangle = |c_1, c_2, c_1 \wedge c_2\rangle.$

Because CCX is self-inverse ( $\text{CCX}^2 = I$ ), applying it a second time restores the target to $|0\rangle$ , as long as the controls have not changed. This is the canonical uncomputation pattern for reversible AND.

The uncomputation pattern

A typical three-step pattern looks like this in circuit notation:

Compute the ancilla: apply the forward circuit $U$ to write a result into $|0\rangle_{\text{anc}}$ .
Use the ancilla: apply some dependent operation that reads (but does not destroy) the ancilla.
Uncompute the ancilla: apply $U^\dagger$ in reverse to return $|0\rangle_{\text{anc}}$ .

After step 3 the ancilla is disentangled from the data register and is back in $|0\rangle$ , ready to be reused or discarded without affecting the state of the data qubits.

Try it

The starter code initialises $|q_0, q_1, q_2\rangle = |1, 1, 0\rangle$ , computes $q_2 = q_0 \wedge q_1 = 1$ with a Toffoli, and then flips $q_2$ with an $X$ gate to simulate "using" the ancilla (turning $|1\rangle$ into $|0\rangle$ ). Your task is to uncompute $q_2$ so that the final state of all three qubits matches what the reference solution produces.

Run your code to see the quantum state.

After running the reference solution you will see that qubit 2 is back in $|0\rangle$ even though it was both computed into and then modified during the use step. The data qubits $q_0$ and $q_1$ are unchanged — the ancilla was truly freed. Notice that uncomputation had to reverse the entire compute-and-use sequence (first undo the $X$ , then undo the CCX), not just the original compute step.