Uncomputation: Difference between revisions

Revision as of 11:35, 18 July 2022

Latest revision as of 16:09, 15 July 2025

(12 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 |date=2010 |publisher=Cambridge University Press |___location=Cambridge |isbn=978-1107002173 |edition=10th Information"Anniversary}}</ref>,{{page needed|date=January 2025}} which states that ignoringdiscarding a register during computation is physically equivalent to measuring it. Failure to uncompute the necessary garbage registers can have unintentional consequences during computation, such as superposition 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 computation,those thenregisters, according to the principle of implicit measurement, wethe wouldentangled havestate essentiallyhas measuredbeen it and ourmeasured, resulting entangledin state 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==