Uncomputation

Uncomputation is a technique, used in reversible circuits, for cleaning up temporary effects on ancilla bits so they can be re-used.^[1]

Creating a NOT gate with five controls out of Toffoli gates and ancilla bits. Uncomputation is used to restore the ancilla bits to the OFF state before finishing.

Uncomputation is important to quantum computing. Whether or not intermediate effects have been uncomputed affects how states interfere with each other when measuring results.^[2]

References

1. Aaronson, Scott; Grier, Daniel; Schaeffer, Luke (2015). "The Classification of Reversible Bit Operations". arXiv:1504.05155 [quant-ph].
2. Aaronson, Scott (2002). "Quantum Lower Bound for Recursive Fourier Sampling". Quantum Information and Computation ():, 00. 3 (2): 165–174. arXiv:quant-ph/0209060. Bibcode:2002quant.ph..9060A.