Uncomputation reverses temporary reversible work after its useful result has been preserved elsewhere. A computation can leave input, auxiliary, auxiliary-output, and final-output registers in |x⟩|aux⟩|f(x)⟩|y⟩; copy f(x) into the final output with CNOT gates, then apply the adjoint of the earlier computation. The auxiliary registers return to |0⟩ while the final register retains |y ⊕ f(x)⟩. section 6.5.1 section 6.7
Table 6.3 The steps of the Bennett’s trick
| Step | Input | Auxiliary qubits | Auxiliary output | Final output |
| Initialize | \(\ket{x}\) | \(\ket{0}\) | \(\ket{0}\) | \(\ket{y}\) |
| \(\ket{x}\) | \(\ket{\text{aux}}\) | \(\ket{f(x)}\) | \(\ket{y}\) | |
| \(\ket{x}\) | \(\ket{\text{aux}}\) | \(\ket{f(x)}\) | \(\ket{y \oplus f(x)}\) | |
| \(\ket{x}\) | \(\ket{0}\) | \(\ket{0}\) | \(\ket{y \oplus f(x)}\) |
Track the four-register sequence: compute temporary values, copy the result, then reverse the temporary computation. section 6.5.1
For a reversible Boolean-expression evaluation:
- Allocate auxiliary qubits for clause results, evaluate each clause into its matching auxiliary qubit, and write the AND of those results directly into the final output qubit. section 6.5.1
- Undo any temporary X gates used to represent negated input literals, then uncompute the auxiliary clause qubits. section 6.5.1
- Reverse dependent computations in reverse evaluation order; only independent checks can be uncomputed in arbitrary order. section 8.2.2
Some reversible classical-function evaluations are their own inverses. For F(x,y) = (x, y ⊕ f(x)), applying F twice restores (x,y), since f(x) ⊕ f(x) cancels. This permits reusing the same constraint-checking code to erase independent temporary results, rather than explicitly taking an adjoint. section 8.2.2
Constraint checks in an N queens oracle
A marking oracle stores column and diagonal constraint results in extra qubits, uses them to obtain the final answer, and then uncomputes the checks. Because the checks are independent, the same evaluation routines can be called again for cleanup. section 8.2.2
Q# expresses the compute–use–uncompute pattern with within–apply conjugation: the within block prepares intermediate results, the apply block uses them, and the adjoint of the within block cleans them up. Qubits allocated within an operation must be returned to |0⟩ before release, making cleanup a programming requirement as well as a circuit pattern. section 6.5.3
