Лекция 3. Обратимые вычисления

На этой Лекции мы обсудили, почему обратимые вычисления возможны и как их можно проводить. Возникнув в связи с размышлениями о принципе Ландауэра и программой цифровой физики, эти идеи значительно повлияли на развитие квантовых вычислений. Булева схема называется обратимой, если она состоит из: некоторого входа, набора обратимых операций над входными битами и дополнительными рабочими битами (анциллами), и прочтения части этих бит в качестве выхода. Любую булеву схему можно переписать как обратимую схему, при этом размер и глубина обратимой схемы возрастёт не более чем в константу раз. При таком переписывании можно проводить очистку мусора, благодаря чему потребуется не более $\mathcal{O}(1)$ дополнительной памяти. В качестве универслаьного набора операций, удобно рассматривать словарь $\{\mathrm{NOT},C\mathrm{NOT},\mathrm{TOFFOLI}\}$, тогда любая перестановка пространства $n$-битных строк $\{0,1\}^n$ может быть реализована при помощи этого словаря, используя не более одной анциллы.