Uncomputation: Difference between revisions

Revision as of 16:03, 12 May 2022

Revision as of 11:35, 18 July 2022

Line 5:

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 ignoring a register during computation is physically equivalent to measuring it. Failure to uncompute the necessary garbage registers can have unintentional consequences on during computation, such as superposition collapse. For example, if we take the state <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 depending on <math>|0\rangle</math> and <math>|1\rangle</math> respectively. Then if we ignore, or "drop" the <math>g_i</math> registers from computation, then according to the principle of implicit measurement, we would have essentially measured it and our resulting entangled state would collapse to either <math>|0\rangle</math> or <math>|1\rangle</math> with 50% probability. Note that what makes this undesirable is that measurement happens before computation finishes, and thus the program may not yield the expected result.