Аннотация:
Мы обсудили простейшие свойства модели обратимых вычислений. В этой модели позволяется использовать только обратимые операции. Обратимая схема состоит из приготовления входных битов и приготовления рабочих битов (анцилл), последовательности обратимых вентилей над битами, и наконец забывания мусора и считывания исхода. Произвольную булевую схему можно эффективно переписать в эквивалентную обратимую схему, при этом размер и глубина схемы увеличится не более, чем в константу раз, и может потребоваться использование константы дополнительной памяти. Вентиль Тоффоли является универсальным в классе обратимых вычислений, при его помощи можно реализовать произвольную перестановку битовых строк, при этом некоторые обратимые функции требуют экспоненциального числа вентилей Тоффоли.
