Lecture 3. Reversible computations

Landauer's principle states that during irreversible computations, the computer necessarily generates heat. In connection with this principle, it is interesting to study reversible computations, which can be performed without generating heat. We have formulated what reversible computations are and shown that Boolean circuits can be reduced to reversible ones. Moreover, thanks to the garbage-cleaning lemma, we are able to do this reduction without significantly increasing memory. We discussed examples of reversible gates and wrote a concrete algorithm of how an arbitrary reversible operation can be realised using Toffoli gates, and gave upper and lower bounds.