Uncomputation: Difference between revisions

Revision as of 15:12, 15 October 2022

Revision as of 15:26, 15 October 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 garbage registers can have unintentional consequences during computation, such as wave-function collapse. 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 depending on <math>|0\rangle</math> and <math>|1\rangle</math> respectively. Then, if we ignore,do ornot "drop"apply theany <math>g_i</math>further registersoperations fromto computationthose registers, then according to the principle of implicit measurement, wethe wouldentangled havestate essentiallycan measuredbe ittaken andto ourbe measured, resulting entangled statein woulda collapse to either <math>|0\rangle|g_0\rangle</math> or <math>|1\rangle|g_1\rangle</math> with 50%probability probability<math>\frac{1}{2}</math>. Note that whatWhat makes this undesirable is that measurementwave-function happenscollapse occurs before computationthe finishesprogram terminates, and thus the program may not yield the expected result.

==References==