Lecture 3. Reversible computation

On this Lecture we discussed why reversible computation is possible and how it works. Coming from thoughts about Landauer's principle and the digital physics programme, these ideas have influenced the development of quantum computing. A Boolean circuit is called reversible if it consists of: some input, a set of reversible operations on the input bits and additional working bits (ancilliae), and reading a part of these bits as the output. Any Boolean circuit can be reduced to a reversible circuit, and the size and depth of the reversible circuit will rise by a constant factor. We can additionally clear the garbage during this rewriting, so that no more than $\mathcal{O}(1)$ of additional memory is required. It is convenient to consider the universal dictionary $\{\mathrm{NOT},C\mathrm{NOT},C\mathrm{TOFFOLI}\}$. Any permutation of the space of $n$-bit strings $\{0,1\}^n$ can be implemented by this dictionary using no more than one ancilla.