Обратимые вычисления

Существует два основных типа обратимости вычислений: физически обратимые и логически обратимые.^[1]

Процесс физически обратим, если по его завершению система не увеличила свою физическую энтропию, то есть процесс является изоэнтропийным. Физически обратимые схемы: charge-recovery logic (сохраняющая заряд логика), адиабатические схемы, адиабатические вычисления. На практике нестационарный физический процесс не может быть полностью физически обратимым (изоэнтропийным), однако для хорошо изолированных систем возможно приближение к полной обратимости.

Вероятно, наибольшим стимулом изучения технологий для реализации обратимых вычислений является то, что они представляются единственным способом улучшить энергоэффективность вычислений за фундаментальные пределы, предсказанные принципом Неймана — Ландауэра^[2][3], согласно которому выделяется по крайней мере kT ln(2) теплоты (около 3×10⁻²¹ Дж при T=300K) на каждую необратимую операцию над битом (при стирании бита информации). На начало XXI века компьютеры рассеивали примерно в миллион раз больше тепла, на начало 2010-х разница снизилась до нескольких тысяч^[4].

Как было показано Рольфом Ландауэром из IBM в 1961 году^[3], для того, чтобы процесс вычислений был физически обратимым, требуется, чтобы он также был логически обратимым (logically reversible). В принципе Ландауэра им впервые было сформулировано правило, согласно которому стирание N бит неизвестной информации всегда связано с увеличением термодинамической энтропии на величину по крайней мере равную Nk ln(2). Дискретный детерминированный процесс вычислений называется логически обратимым в случае, если функция переходов, отображающая старое состояние системы в новое является инъективной (каждому новому состоянию однозначно соответствует одно старое состояние), то есть, по информации о конечном логическом состоянии схемы возможно определить входное логическое состояние схемы.

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

Один из первых вариантов^[5] реализации обратимых вычислений был предложен в работах Чарльза Беннетта,^[6][7] (IBM Research, 1973). В настоящее время множеством ученых предложены десятки концепций обратимых вычислений, включая обратимые логические вентили, электронные схемы, архитектуры процессоров, языки программирования, алгоритмы^[8][9].

Для реализаций обратимых вычислительных схем и оценок их сложности и ограничений используется формализация через обратимые вентили — аналоги логических вентилей. Например, вентиль инвертора NOT (НЕ) является обратимым, так как сохраняет информацию. В то же время логический вентиль исключительное ИЛИ (XOR) является необратимым — значения его входов не могут быть восстановлены из единственного выходного значения. Обратимым аналогом XOR может стать вентиль управляемого отрицания (CNOT — controlled NOT).