К счастью, гейт примитивный ERASE не является абсолютно необходимым в вычислениях. Чтобы понять, почему это так, рассмотрим, что требуется для вычисления произвольных функций, использующего обратимую логику (где примитивный ERASE запрещен). Ландауэр показал, как любая функция $f(a)$ может быть воспроизведена взаимно однозначно с ее аргументом (один к одному) в результате сохранения копии входных данных:
\[
f: a \rightarrow(a, f(a)) .
\]

Круглые скобки означают здесь упорядоченный набор величин, в данном случае двух. Дополнительные «щели» будут добавлены (или удалены), как потребуется в нашем дальнейшем обсуждении.

Как этот трюк может быть использован для выполнения обратимой логики? Одно решение, известное как Тоффоли-гейт, показано на рис. 4 $[8,10,11]$. Выход этого гейта может быть разложен в различные гейты:
\[
B \oplus(\text { A.C })=\left\{\begin{array}{rlll}
A . C, & \text { для } & B=0 & (\mathrm{AND}) \\
A \oplus B, & \text { для } & C=1 & \text { (XOR) } \\
\bar{B}, & \text { для } & A=C=1 & \text { (NOT) } \\
A, & \text { для } & B=0, C=1 & \text { (FANOUT) }
\end{array}\right.
\]

где $A . B$ изображает AND-гейт, $A \oplus B$ изображает XOR-гейт и $\bar{A}$ изображает NOT-гейт. Мы видим, что этот гейт является универсальным, поскольку он выполняет AND, XOR, NOT или FANOUT, в зависимости от того, что имеется на входе.

Комбинация многих таких гейтов может затем использоваться для любого вычисления и будет оставаться обратимой.

Рис. 4. Универсальный обратимый Тоффоли-гейт с тройным входом и тройным выходом. Этот гейт, очевидно, является обратимым, т. к. повторное его применение воспроизводит первоначальные входные данные.

Как было замечено Ландауэром, эта процедура приводит к прямой проблеме из-за отсутствия примитивного ERASE. Чем больше гейтов мы используем, тем больше «мусорных» битов мы накопим: в каждом гейте мы должны хранить входные биты для сохранения обратимости. Другими словами, компьютер, построенный из логически обратимых гейтов вместо обычных, логически необратимых гейтов, вел бы себя как
\[
f: a \rightarrow(a, j(a), f(a)),
\]

с большим числом дополнительных мусорных битов $j(a)$.
Беннетт решил эту проблему, показав, что мусорные биты могут быть обратимым образом стерты на промежуточных шагах с минимальными затратами времени и памяти $[12,13]$. Идею решения Беннетта можно истолковать на языке следующей процедуры:
\[
\begin{array}{c}
f: a \rightarrow(a, j(a), f(a)), \\
\text { FANOUT: }(a, j(a), f(a)) \rightarrow(a, j(a), f(a), f(a)), \\
f^{\dagger}:(a, j(a), f(a), f(a)) \rightarrow(a, f(a)),
\end{array}
\]

где $f^{\dagger}$ обозначает возвращение к невычисленному $f$, как противоположное к вычислению $f^{-1}$. Сначала вычисляется $f$ и при этом получаются мусорные биты и искомый выходной результат. Затем применяется FANOUT-гейт для дублирования выходного результата. В конце мы возвращаемся к невычисленной исходной функции $f$, выполняя в обратную сторону операцию ее вычисления. Эта процедура удаляет мусорные биты и первоначальный выходной результат. Однако дубликат остается!

Это завершает наше обсуждение устройства классических обратимых компьютеров. Мы установили, что требование обратимости не является препятствием для логической конструкции вычислительных машин. Прежде, чем переносить эти идеи на квантовые системы, введем некоторые элементарные квантовомеханические понятия.