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