Пусть $\mathscr{B}$ конечный базис классических гейтов, содержащий однобитовую тождественную функцию и порождающий все логические цепи и функцию $F: \mathbf{F}_{2}^{m} \rightarrow \mathbf{F}_{2}^{n}$. Опишем, как превратить схему из логических элементов длины $L$, вычисляющую $F$, в другую логическую схему сравнимой длины, состоящую только из обратимых гейтов и вычисляющую модифицированную функцию, которая, однако, содержит всю информацию о графике $F$. Обратимость означает, что каждый шаг есть биекция (в действительности, свертка) и, следовательно, может быть расширен до унитарного оператора, т. е. квантового гейта. Для квантового гейта $f$ определим $\widetilde{f}(|x, y\rangle)=|x, f(x)+y\rangle$ как выше в 2.2 (D).
3.2.1. Предложение. Булевская схема $\mathcal{S}$ длины $L$ в базисе $\mathscr{B}$ может быть преобразована в обратимую булевскую схему $\widetilde{\mathcal{S}}$ длины $O\left((L+m+n)^{2}\right)$, вычисляющую перестановку $H: \mathbf{F}_{2}^{m+n+L} \rightarrow \mathbf{F}_{2}^{m+n+L}$ со следующим свойством:
\[
H(x, y, 0)=(x, F(x)+y, 0)=(\tilde{F}(x, y), 0) .
\]

Здесь $x, y, z$ имеют размеры $m, n, L$ соответственно.
Доказательство.
Здесь мы будем понимать $L$ как сумму размеров выходов всех гейтов, участвующих в описании $\mathcal{S}$. Во-первых, заменим в $\mathcal{S}$ каждый гейт $f$ его обратимым вариантом $\tilde{f}$. Это приведет к вставке новых битов, которые помещаются в новый регистр сплошным сегментом общей длины $L$. Полученная подцепь будет вычислять такую перестановку $K: \mathbf{F}_{2}^{m+L} \rightarrow \mathbf{F}_{2}^{m+L}$, что $K(x, 0)=(F(x), G(x))$ для некоторой функции $G$ (мусор).

Теперь добавим к памяти еще один регистр размера $n$, содержащий переменную $y$. Продолжим $K$ до перестановки $\bar{K}: \mathbf{F}_{2}^{m+L+n} \rightarrow \mathbf{F}_{2}^{m+L+n}$, не изменяющей $y$, т.е. $\bar{K}:(x, 0, y) \mapsto(F(x), G(x), y)$. Очевидно, что $\bar{K}$ вычисляется той же логической схемой, что и $K$, но с расширенным регистром.

Включим в эту схему еще одну подсхему, складывающую содержимое первого и третьего регистров: $(F(x), G(x), y) \mapsto(F(x), G(x)$,
$F(x)+y)$. И наконец, построим последнее расширение, которое вычисляет $\bar{K}^{-1}$ и состоит из обращенных гейтов, вычисляющих $\bar{K}$ в обратном порядке. Оно очищает средний регистр (мусор) и выдает ( $x, 0, F(x)+y)$. Для всей цепи требуется $O(L+m+n)$ гейтов, если мы разрешаем их применение не обязательно к соседним битам. Иначе мы должны вставлять гейты для локальных перестановок, которые заменят эту оценку на $O\left((L+m+n)^{2}\right)$.