Uncomputation: Difference between revisions

Revision as of 15:26, 15 October 2022

Latest revision as of 16:09, 15 July 2025

(10 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 ignoringdiscarding 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. Then, if we do not apply any further operations to those registers, then according to the principle of implicit measurement, the entangled state can be taken tohas bebeen 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.

==References==