Uncomputation: Difference between revisions

Revision as of 15:28, 15 October 2022

Latest revision as of 16:09, 15 July 2025

(9 intermediate revisions by 7 users not shown)

Line 1:

{{Short description|Quantum computing technique}}

[[File:Using Toffoli Gates and Ancilla Bits to make a Not Gate with many controls.png|thumb|400px|Creating a logical conjunction of the five controls out of [[Toffoli gate]]s and ancilla bits. Uncomputation is used to restore the ancilla bits to their original states before finishing.]]

'''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>{{cite book |last1=Nielsen, |first1=Michael; A. |last2=Chuang, |first2=Isaac L. "|title=Quantum Computationcomputation and Quantumquantum Information"information |date=2010 |publisher=Cambridge University Press |___location=Cambridge |isbn=978-1107002173 |edition=10th Anniversary}}</ref>,{{page needed|date=January 2025}} 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>

\frac{1}{\sqrt 2}(|0\rangle|g_0\rangle + |1\rangle|g_1\rangle)

</math> where <math>g_0</math> and <math>g_1</math> are garbage registers. Then, if we do not apply any further operations to those registers, according to the principle of implicit measurement, the entangled state has been measured, resulting in a collapse to either <math>|0\rangle|g_0\rangle</math> or <math>|1\rangle|g_1\rangle</math> with probability <math>\frac{1}{2}</math>. What makes this undesirable is that wave-function collapse occurs before the program terminates, and thus may not yield the expected result.