Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Модель вычислений, в которой все процессы обратимы во времени.
Model of computation in which all processes are time reversible
Реверсивные вычисления – это любая модель вычислений, в которой вычислительный процесс в определенной степени обратим во времени. В модели вычислений, использующей детерминированные переходы от одного состояния абстрактной машины к другому, необходимым условием обратимости является то, что отношение отображения состояний в их последующие состояния должно быть взаимно однозначным. Реверсивные вычисления являются формой нетрадиционных вычислений. Благодаря унитарности квантовой механики, квантовые схемы обратимы, пока они не приводят к "коллапсу" квантовых состояний, над которыми они оперируют.
Reversible computing is any model of computation where the computational process, to some extent, is time reversible. In a model of computation that uses deterministic transitions from one state of the abstract machine to another, a necessary condition for reversibility is that the relation of the mapping from states to their successors must be one to one. Reversible computing is a form of unconventional computing. Due to the unitarity of quantum mechanics, quantum circuits are reversible, as long as they do not "collapse" the quantum states on which they operate.
Возвратность
Существует два основных, тесно связанных между собой типа обратимости, представляющих особый интерес для этой цели: физическая обратимость и логическая обратимость. Процесс считается физически обратимым, если он не приводит к увеличению физической энтропии; он изэнтропический. Существует стиль проектирования схем, идеально демонстрирующий это свойство, который называется логикой восстановления заряда, адиабатическими схемами или адиабатическими вычислениями (см. Адиабатический процесс). Хотя на практике ни один нестационарный физический процесс не может быть точно физически обратимым или изэнтропическим, нет известных ограничений для степени приближения к идеальной обратимости в системах, достаточно хорошо изолированных от взаимодействий с неизвестными внешними средами, при условии, что законы физики, описывающие эволюцию системы, точно известны. Мотивацией для изучения технологий, направленных на реализацию обратимых вычислений, является то, что они предлагают, как предполагается, единственный потенциальный способ повышения вычислительной энергоэффективности (то есть количества полезных операций, выполняемых на единицу рассеянной энергии) компьютеров за пределы фундаментального предела фон Неймана — Ландауэра, равного kT (энергии), рассеиваемой на одну необратимую битовую операцию. Хотя предел Ландауэра был в миллионы раз ниже энергопотребления компьютеров в 2000-х годах и в тысячи раз ниже в 2010-х годах, сторонники обратимых вычислений утверждают, что это во многом связано с архитектурными накладными расходами, которые эффективно усиливают влияние предела Ландауэра в практических схемах, что может затруднить прогресс практических технологий за пределы текущих уровней энергоэффективности без использования принципов обратимых вычислений.
There are two major, closely related types of reversibility that are of particular interest for this purpose: physical reversibility and logical reversibility. A process is said to be physically reversible if it results in no increase in physical entropy; it is isentropic. There is a style of circuit design ideally exhibiting this property that is referred to as charge recovery logic, adiabatic circuits, or adiabatic computing (see Adiabatic process). Although in practice no nonstationary physical process can be exactly physically reversible or isentropic, there is no known limit to the closeness with which we can approach perfect reversibility, in systems that are sufficiently well isolated from interactions with unknown external environments, when the laws of physics describing the system's evolution are precisely known. A motivation for the study of technologies aimed at implementing reversible computing is that they offer what is predicted to be the only potential way to improve the computational energy efficiency (i. e., useful operations performed per unit energy dissipated) of computers beyond the fundamental von Neumann–Landauer limit of [[kT (energy) energy dissipated per irreversible bit operation. Although the Landauer limit was millions of times below the energy consumption of computers in the 2000s and thousands of times less in the 2010s, proponents of reversible computing argue that this can be attributed largely to architectural overheads which effectively magnify the impact of Landauer's limit in practical circuit designs, so that it may prove difficult for practical technology to progress very far beyond current levels of energy efficiency if reversible computing principles are not used.
Связь с термодинамикой
Как впервые утверждал Рольф Ландауэр, работая в IBM, для того чтобы вычислительный процесс был физически обратимым, он также должен быть логически обратимым. Принцип Ландауэра заключается в том, что безвозвратное стирание n бит известной информации всегда влечет за собой затраты в размере nkT ln(2) в термодинамической энтропии. Дискретный, детерминированный вычислительный процесс считается логически обратимым, если функция перехода, отображающая старые вычислительные состояния в новые, является биекцией, то есть выходные логические состояния однозначно определяют входные логические состояния вычислительной операции. Для вычислительных процессов, которые являются недетерминированными (в смысле вероятностными или случайными), связь между старыми и новыми состояниями не является однозначной функцией, и требование, необходимое для достижения физической обратимости, становится несколько более слабым: размер данного ансамбля возможных начальных вычислительных состояний, в среднем, не должен уменьшаться в ходе вычислений.
As was first argued by Rolf Landauer while working at IBM, in order for a computational process to be physically reversible, it must also be logically reversible. Landauer's principle is the observation that the oblivious erasure of n bits of known information must always incur a cost of nkT ln(2) in thermodynamic entropy. A discrete, deterministic computational process is said to be logically reversible if the transition function that maps old computational states to new ones is a one to one function; i. e. the output logical states uniquely determine the input logical states of the computational operation. For computational processes that are nondeterministic (in the sense of being probabilistic or random), the relation between old and new states is not a single valued function, and the requirement needed to obtain physical reversibility becomes a slightly weaker condition, namely that the size of a given ensemble of possible initial computational states does not decrease, on average, as the computation proceeds forwards.
Физическая обратимость
Принцип Ландауэра (и, действительно, второй закон термодинамики) также можно понимать как прямое логическое следствие фундаментальной обратимости физических процессов, что отражено в общей гамильтоновой формулировке механики и, в частности, в унитарном операторе временной эволюции квантовой механики. Реализация обратимых вычислений, таким образом, заключается в том, чтобы научиться характеризовать и контролировать физическую динамику механизмов для выполнения желаемых вычислительных операций настолько точно, чтобы эксперимент накапливал пренебрежимо малое количество неопределенности относительно полного физического состояния механизма при каждой выполняемой логической операции. Иными словами, необходимо точно отслеживать состояние активной энергии, вовлеченной в выполнение вычислительных операций внутри машины, и проектировать машину таким образом, чтобы большая часть этой энергии восстанавливалась в организованной форме, пригодной для повторного использования в последующих операциях, а не рассеивалась в виде тепла. Хотя достижение этой цели представляет собой серьезную задачу для проектирования, производства и характеризации ультраточных новых физических механизмов для вычислений, в настоящее время нет фундаментальных причин полагать, что эта цель не может быть в конечном итоге достигнута, что позволит когда-нибудь создавать компьютеры, генерирующие значительно меньше 1 бита физической энтропии (и рассеивающие значительно меньше, чем kT ln 2 энергии в виде тепла) на каждую полезную логическую операцию, выполняемую внутри. Сегодня в этой области существует обширная научная литература. Широкий спектр концепций обратимых устройств, логических элементов, электронных схем, архитектур процессоров, языков программирования и прикладных алгоритмов был разработан и проанализирован физиками, инженерами-электриками и специалистами по компьютерным наукам. Эта область исследований ожидает детальной разработки высококачественной, экономически эффективной и почти обратимой технологии логических устройств, включающей высокоэффективные механизмы синхронизации или обходящей необходимость в них посредством асинхронного проектирования. Такой инженерный прогресс необходим, прежде чем обширные теоретические исследования в области обратимых вычислений смогут найти практическое применение для преодоления краткосрочных барьеров энергоэффективности реальных компьютерных технологий, включая предел фон Неймана — Ландауэра. Преодолеть этот предел возможно только с помощью логически обратимых вычислений, что обусловлено вторым законом термодинамики.
Landauer's principle (and indeed, the second law of thermodynamics) can also be understood to be a direct logical consequence of the underlying reversibility of physics, as is reflected in the general Hamiltonian formulation of mechanics, and in the unitary time evolution operator of quantum mechanics more specifically. The implementation of reversible computing thus amounts to learning how to characterize and control the physical dynamics of mechanisms to carry out desired computational operations so precisely that the experiment accumulates a negligible total amount of uncertainty regarding the complete physical state of the mechanism, per each logic operation that is performed. In other words, precisely track the state of the active energy that is involved in carrying out computational operations within the machine, and design the machine so that the majority of this energy is recovered in an organized form that can be reused for subsequent operations, rather than being permitted to dissipate into the form of heat. Although achieving this goal presents a significant challenge for the design, manufacturing, and characterization of ultra precise new physical mechanisms for computing, there is at present no fundamental reason to think that this goal cannot eventually be accomplished, allowing someday to build computers that generate much less than 1 bit's worth of physical entropy (and dissipate much less than kT ln 2 energy to heat) for each useful logical operation that they carry out internally. Today, the field has a substantial body of academic literature. A wide variety of reversible device concepts, logic gates, electronic circuits, processor architectures, programming languages, and application algorithms have been designed and analyzed by physicists, electrical engineers, and computer scientists. This field of research awaits the detailed development of a high quality, cost effective, nearly reversible logic device technology, one that includes highly energy efficient clocking and synchronization mechanisms, or avoids the need for these through asynchronous design. This sort of solid engineering progress will be needed before the large body of theoretical research on reversible computing can find practical application in enabling real computer technology to circumvent the various near term barriers to its energy efficiency, including the von Neumann–Landauer bound. This may only be circumvented by the use of logically reversible computing, due to the second law of thermodynamics.
Логическая обратимость
Для того чтобы вычислительная операция была логически обратимой, это означает, что выход (или конечное состояние) операции может быть вычислен на основе входа (или начального состояния), и наоборот. Обратимые функции являются биективными. Это означает, что обратимые вентили (и схемы, то есть композиции из нескольких вентилей) обычно имеют такое же количество входных битов, как и выходных (при условии, что все входные биты потребляются операцией и что все входные/выходные состояния возможны). Вентиль инвертора (NOT) логически обратим, поскольку его можно отменить. Однако, в зависимости от реализации, вентиль NOT может быть физически необратим. Вентиль исключающего ИЛИ (XOR) необратим, поскольку его два входа нельзя однозначно восстановить по его единственному выходу, или, альтернативно, поскольку стирание информации не является обратимым. Однако обратимый вариант вентиля XOR — управляемый вентиль NOT (CNOT) — может быть определен путем сохранения одного из входов в качестве второго выхода. Трехвходный вариант CNOT называется вентилем Тоффоли. Он сохраняет два своих входа a, b и заменяет третий вход c на . С этим получается функция AND, а с — функция NOT. Поскольку AND и NOT вместе образуют функционально полную систему, вентиль Тоффоли является универсальным и может реализовать любую булеву функцию (при наличии достаточного количества инициализированных вспомогательных битов). Аналогично, в модели вычислений машины Тьюринга обратимой машиной Тьюринга является та, у которой функция перехода обратима, так что каждое состояние машины имеет не более одного предшественника. Ив Лесерф предложил обратимую машину Тьюринга в статье 1963 года, но, по-видимому, не зная о принципе Ландауэра, не продолжил работу в этом направлении, посвятив большую часть оставшейся карьеры этнолингвистике. В 1973 году Чарльз Беннетт из IBM Research показал, что универсальную машину Тьюринга можно сделать как логически, так и термодинамически обратимой и, следовательно, в принципе способной выполнять произвольно большое количество вычислительных шагов на единицу рассеянной физической энергии, если она работает достаточно медленно. Термодинамически обратимые компьютеры могут выполнять полезные вычисления с полезной скоростью, рассеивая значительно меньше, чем kT энергии на логический шаг. В 1982 году Эдвард Фредкин и Томмазо Тоффоли предложили компьютер на бильярдных шарах — механизм, использующий классические твердые сферы для выполнения обратимых вычислений с конечной скоростью и нулевым рассеянием, но требующий идеального начального выравнивания траекторий шаров, а обзор Беннетта сравнил эти «броуновские» и «баллистические» парадигмы для обратимых вычислений. Помимо мотивации энергоэффективных вычислений, обратимые логические вентили предлагали практические улучшения преобразований манипулирования битами в криптографии и компьютерной графике. С 1980-х годов обратимые схемы привлекают интерес как компоненты квантовых алгоритмов, а в последнее время — в фотонных и нановычислительных технологиях, где некоторые коммутационные устройства не обеспечивают усиления сигнала. Доступны обзоры обратимых схем, их конструкции и оптимизации, а также недавние исследовательские задачи.
For a computational operation to be logically reversible means that the output (or final state) of the operation can be computed from the input (or initial state), and vice versa. Reversible functions are bijective. This means that reversible gates (and circuits, i. e. compositions of multiple gates) generally have the same number of input bits as output bits (assuming that all input bits are consumed by the operation, and that all input/output states are possible). An inverter (NOT) gate is logically reversible because it can be undone. The NOT gate may however not be physically reversible, depending on its implementation. The exclusive or (XOR) gate is irreversible because its two inputs cannot be unambiguously reconstructed from its single output, or alternatively, because information erasure is not reversible. However, a reversible version of the XOR gate—the controlled NOT gate (CNOT)—can be defined by preserving one of the inputs as a 2nd output. The three input variant of the CNOT gate is called the Toffoli gate. It preserves two of its inputs a,b and replaces the third c by With , this gives the AND function, and with this gives the NOT function. Because AND and NOT together is a functionally complete set, the Toffoli gate is universal and can implement any Boolean function (if given enough initialized ancilla bits). Similarly, in the Turing machine model of computation, a reversible Turing machine is one whose transition function is invertible, so that each machine state has at most one predecessor. Yves Lecerf proposed a reversible Turing machine in a 1963 paper, but apparently unaware of Landauer's principle, did not pursue the subject further, devoting most of the rest of his career to ethnolinguistics. In 1973 Charles H. Bennett, at IBM Research, showed that a universal Turing machine could be made both logically and thermodynamically reversible, and therefore able in principle to perform an arbitrarily large number of computation steps per unit of physical energy dissipated, if operated sufficiently slowly. Thermodynamically reversible computers could perform useful computations at useful speed, while dissipating considerably less than kT of energy per logical step. In 1982 Edward Fredkin and Tommaso Toffoli proposed the Billiard ball computer, a mechanism using classical hard spheres to do reversible computations at finite speed with zero dissipation, but requiring perfect initial alignment of the balls' trajectories, and Bennett's review compared these "Brownian" and "ballistic" paradigms for reversible computation. Aside from the motivation of energy efficient computation, reversible logic gates offered practical improvements of bit manipulation transforms in cryptography and computer graphics. Since the 1980s, reversible circuits have attracted interest as components of quantum algorithms, and more recently in photonic and nano computing technologies where some switching devices offer no signal gain. Surveys of reversible circuits, their construction and optimization, as well as recent research challenges, are available.