Uncomputation: Difference between revisions

Revision as of 09:09, 9 September 2024

Revision as of 17:30, 5 January 2025

Line 3:

'''Uncomputation''' is a technique, used in [[Reversible computing|reversible]] circuits, for cleaning up temporary effects on [[Ancilla Bit|ancilla bits]] so that they can be re-used.<ref>{{cite arXiv |eprint=1504.05155|last1=Aaronson|first1=Scott|title=The Classification of Reversible Bit Operations|last2=Grier|first2=Daniel|last3=Schaeffer|first3=Luke|class=quant-ph|year=2015}}</ref>

Uncomputation is a fundamental step in [[quantum computing]] algorithms. Whether or not intermediate effects have been uncomputed affects how states interfere with each other when measuring results.<ref>{{Cite journal|arxiv=quant-ph/0209060|last1=Aaronson|first1=Scott|title=Quantum Lower Bound for Recursive Fourier Sampling|journal=Quantum Information and Computation ():, 00|volume=3|issue=2|pages=165–174|year=2002|doi=10.26421/QIC3.2-7 |bibcode=2002quant.ph..9060A}}</ref>

The process is primarily motivated by the principle of implicit measurement,<ref>Nielsen, Michael; Chuang, Isaac. "Quantum Computation and Quantum Information"</ref> which states that discarding a register during computation is physically equivalent to measuring it. Failure to uncompute garbage registers can have unintentional consequences. For example, if we take the state <math></math> <math>