Обратимые вычисления — это любая модель вычислений , где вычислительный процесс , в некоторой степени, обратим во времени . В модели вычислений, которая использует детерминированные переходы из одного состояния абстрактной машины в другое, необходимым условием обратимости является то, что отношение отображения из состояний в их последовательные состояния должно быть один к одному . Обратимые вычисления — это форма нетрадиционных вычислений .
Благодаря унитарности квантовой механики квантовые цепи обратимы, пока они не « разрушают » квантовые состояния, в которых они работают. [1]
Существуют два основных, тесно связанных типа обратимости, которые представляют особый интерес для этой цели: физическая обратимость и логическая обратимость . [2]
Процесс называется физически обратимым, если он не приводит к увеличению физической энтропии ; он является изоэнтропическим . Существует стиль проектирования схем, идеально демонстрирующий это свойство, который называется логикой восстановления заряда , адиабатическими цепями или адиабатическими вычислениями (см. Адиабатический процесс ). Хотя на практике ни один нестационарный физический процесс не может быть в точности физически обратимым или изоэнтропическим, не существует известного предела близости, с которой мы можем приблизиться к идеальной обратимости в системах, которые достаточно хорошо изолированы от взаимодействия с неизвестной внешней средой, когда законы физики, описывающие эволюцию системы, точно известны.
Мотивацией для изучения технологий, направленных на реализацию обратимых вычислений, является то, что они предлагают то, что, как прогнозируется, является единственным потенциальным способом повышения эффективности вычислительной энергии (т. е. полезных операций, выполняемых на единицу рассеиваемой энергии) компьютеров за пределами фундаментального предела фон Неймана-Ландауэра [3] [4] kT ln(2) энергии , рассеиваемой на необратимую битовую операцию . Хотя предел Ландауэра был в миллионы раз ниже энергопотребления компьютеров в 2000-х годах и в тысячи раз меньше в 2010-х годах, [5] сторонники обратимых вычислений утверждают, что это можно в значительной степени отнести к архитектурным накладным расходам, которые эффективно увеличивают влияние предела Ландауэра в практических схемах, так что для практической технологии может оказаться сложным продвинуться намного дальше текущих уровней энергоэффективности, если не будут использоваться принципы обратимых вычислений. [6]
Как впервые утверждал Рольф Ландауэр во время работы в IBM , [7] для того, чтобы вычислительный процесс был физически обратимым, он также должен быть логически обратимым . Принцип Ландауэра заключается в наблюдении, что забывчивое стирание n бит известной информации всегда должно влечь за собой стоимость nkT ln(2) в термодинамической энтропии . Дискретный, детерминированный вычислительный процесс называется логически обратимым, если функция перехода, которая отображает старые вычислительные состояния в новые, является функцией один к одному ; т. е. выходные логические состояния однозначно определяют входные логические состояния вычислительной операции.
Для вычислительных процессов, которые являются недетерминированными (в смысле вероятностных или случайных), связь между старыми и новыми состояниями не является однозначной функцией , и требование, необходимое для получения физической обратимости, становится немного более слабым условием, а именно, что размер заданного ансамбля возможных начальных вычислительных состояний в среднем не уменьшается по мере продвижения вычислений.
Принцип Ландауэра (и, конечно, второй закон термодинамики ) можно также понимать как прямое логическое следствие основополагающей обратимости физики , как это отражено в общей гамильтоновой формулировке механики и, в частности , в унитарном операторе эволюции во времени квантовой механики . [8]
Реализация обратимых вычислений, таким образом, сводится к изучению того, как характеризовать и контролировать физическую динамику механизмов для выполнения желаемых вычислительных операций настолько точно, чтобы эксперимент накапливал пренебрежимо малое общее количество неопределенности относительно полного физического состояния механизма на каждую выполняемую логическую операцию. Другими словами, точно отслеживать состояние активной энергии, которая участвует в выполнении вычислительных операций в машине, и проектировать машину таким образом, чтобы большая часть этой энергии восстанавливалась в организованной форме, которую можно было бы повторно использовать для последующих операций, а не рассеиваться в форме тепла.
Хотя достижение этой цели представляет собой значительную проблему для проектирования, производства и характеристики новых сверхточных физических механизмов для вычислений , в настоящее время нет никаких фундаментальных оснований полагать, что эта цель в конечном итоге не может быть достигнута, что позволит когда-нибудь построить компьютеры, которые генерируют гораздо меньше 1 бита физической энтропии (и рассеивают гораздо меньше kT ln 2 энергии на тепло) для каждой полезной логической операции, которую они выполняют внутри.
Сегодня эта область имеет значительный объем академической литературы. Широкий спектр концепций обратимых устройств, логических вентилей , электронных схем , архитектур процессоров, языков программирования и прикладных алгоритмов был разработан и проанализирован физиками , инженерами-электриками и специалистами по информатике .
Эта область исследований ожидает детальной разработки высококачественной, экономически эффективной, почти обратимой технологии логических устройств, которая включает в себя высокоэнергоэффективные механизмы синхронизации и тактирования или избегает необходимости в них посредством асинхронного проектирования. Такого рода солидный инженерный прогресс будет необходим, прежде чем большой объем теоретических исследований по обратимым вычислениям сможет найти практическое применение, позволяя реальной компьютерной технологии обходить различные краткосрочные барьеры для ее энергоэффективности, включая границу фон Неймана-Ландауэра. Это можно обойти только с помощью логически обратимых вычислений из-за второго закона термодинамики . [9]
Для вычислительной операции быть логически обратимой означает, что выход (или конечное состояние) операции может быть вычислен из входа (или начального состояния), и наоборот. Обратимые функции являются биективными . Это означает, что обратимые вентили (и схемы , т. е. композиции нескольких вентилей) обычно имеют одинаковое количество входных битов и выходных битов (предполагая, что все входные биты потребляются операцией, и что все состояния входа/выхода возможны).
Инверторный вентиль (НЕ) логически обратим, поскольку его можно отменить . Однако вентиль НЕ может быть физически необратимым, в зависимости от его реализации.
Вентиль «исключающее ИЛИ » (XOR) необратим, поскольку его два входа не могут быть однозначно восстановлены из его одного выхода, или, в качестве альтернативы, поскольку стирание информации необратимо. Однако обратимая версия вентиля «исключающее ИЛИ» — управляемый вентиль НЕ (CNOT) — может быть определена путем сохранения одного из входов в качестве второго выхода. Трехвходовой вариант вентиля CNOT называется вентилем Тоффоли . Он сохраняет два своих входа a, b и заменяет третий c на . С , это дает функцию И, а с этим дает функцию НЕ. Поскольку И и НЕ вместе являются функционально полным набором, вентиль Тоффоли универсален и может реализовать любую булеву функцию (если задано достаточно инициализированных вспомогательных битов ).
Аналогично, в модели вычислений на основе машины Тьюринга обратимой является машина Тьюринга, функция перехода которой обратима, так что каждое состояние машины имеет не более одного предшественника.
Ив Лесерф предложил обратимую машину Тьюринга в статье 1963 года [10] , но, по-видимому, не зная о принципе Ландауэра, не стал заниматься этим вопросом дальше, посвятив большую часть своей оставшейся карьеры этнолингвистике. В 1973 году Чарльз Х. Беннетт из IBM Research показал, что универсальная машина Тьюринга может быть сделана как логически, так и термодинамически обратимой [11] и, следовательно, способной в принципе выполнять произвольно большое количество шагов вычисления на единицу рассеиваемой физической энергии, если работать достаточно медленно. Термодинамически обратимые компьютеры могли бы выполнять полезные вычисления с полезной скоростью, рассеивая при этом значительно меньше kT энергии на логический шаг. В 1982 году Эдвард Фредкин и Томмазо Тоффоли предложили компьютер Billiard ball , механизм, использующий классические твердые сферы для выполнения обратимых вычислений на конечной скорости с нулевой диссипацией, но требующий идеального начального выравнивания траекторий шаров, а обзор Беннетта [12] сравнил эти «броуновские» и «баллистические» парадигмы для обратимых вычислений. Помимо мотивации энергоэффективных вычислений, обратимые логические вентили предложили практические улучшения преобразований битовой манипуляции в криптографии и компьютерной графике. С 1980-х годов обратимые схемы привлекали интерес как компоненты квантовых алгоритмов , а в последнее время и в фотонных и нанокомпьютерных технологиях, где некоторые коммутационные устройства не обеспечивают усиления сигнала .
Доступны обзоры обратимых цепей, их построения и оптимизации, а также недавних исследовательских задач. [13] [14] [15] [16] [17]
Энтропия замкнутой системы, например, компьютера с собственными батареями, не может уменьшаться; следовательно, эта энтропия должна проявляться в другом месте как тепловой эффект, поставляя 0,6931 кТл на восстановленный бит в окружающую среду.
