Итак, утверждается, что обратимое вычисление не требует затраты времени, поскольку, в отличие от необратимых вычислений, оно не является физическим процессом, происходящим в пространстве и во времени.
Чтобы пояснить это, рассмотрим какую-нибудь конкретную реализацию необратимой логической операции и какую-нибудь конкретную реализацию обратимой логической операции. Вот, например, как реализуется необратимая операция И-НЕ на основе технологии КМОП с использованием четырёх полевых транзисторов:
Когда, например, на вход a и на вход b подаётся логическая единица, то транзисторы 1 и 2 (p-канальные) запираются, а транзисторы 3 и 4 (n-канальные), наоборот, открываются. В результате выход оказывается замкнутым на землю, т. е. на выходе получается логический 0.
"Транзистор открывается" - это означает, что электроны либо дырки (в зависимости от того, какой транзистор - n-канальный или p-канальный), притягиваясь к затвору, скапливаются под ним, образуя проводящий канал. "Транзистор закрывается" - это те же электроны либо дырки, отталкиваясь от затвора, уходят, и проводящий канал пропадает. Так что открывание или закрывание транзистора представляет собой вполне определённый физический процесс: движение носителей заряда к затвору или, наоборот, от затвора. Этот перенос заряда происходит в определённом месте пространства (под затвором) и в течение определённого отрезка времени, определяемого ёмкостью и сопротивлением системы. Конечно, скорость срабатывания логического элемента (в нашем случае - скорость переключения транзисторов) может быть увеличена путём технологических усовершенствований, либо путём перехода к принципиально новым реализациям логических элементов (например, к свехпроводящим переключателям). Но в любом случае выполнение необратимой логической операции - это физический процесс, минимальная длительность которого определяется физическими характеристиками используемого логического элемента.
Другое дело - обратимые вычисления. Мы рассмотрим в качестве примера их реализацию, использующую спин электрона как носитель информации. Для наших целей спин электрона можно изображать в виде стрелочки (вектора фиксированной длины), которая может быть ориентирована в произвольном направлении; направление стрелочки и задаёт спиновое состояние электрона. Пусть состояние "спин вверх" соответствует логической единице, а состояние "спин вниз" - логическому нулю. Теперь, чтобы реализовать обратимую логическую операцию НЕ, можно подействовать на наш электрон импульсом магнитного поля, направление которого перпендикулярно вертикали. Магнитное поле вызывает вращение стрелочки, изображающей спин электрона, вокруг направления магнитного поля, причём угловая скорость вращения определяется интенсивностью поля. Длительность импульса выбирается такой, чтобы спин электрона повернулся на 180 градусов. Такой импульс магнитного поля переводит состояние "спин вверх" в состояние "спин вниз" и наоборот; то есть он переводит 1 в 0 и 0 в 1. Таким образом, он действительно реализует операцию НЕ.
Теперь вопрос: в какой момент времени (или в течение какого отрезка времени) происходит выполнение операции НЕ в расмотренном примере? Первый приходящий в голову ответ таков: операция выполняется в течение отрезка времени [t1,t2], где t1 - момент включения магнитного поля, t2 - момент его выключения. Действительно, пусть, например, начальное спиновое состояние электрона было "спин вверх" (т. е. 1). Тогда в моменты времени t<t1 спин направлен вверх, что соответствует логической единице; в моменты времени t1<t<t2 направление спина будет промежуточным между верхом и низом (т. е. ни 0, ни 1); а при t>t2 спин направлен вниз (что соответствует логическому нулю). Таким образом, при t<t1 выполнение логической операции НЕ ещё не началось, при t1<t<t2 оно началось, но ещё не закончилось, а при t>t2 операция уже завершилась. То есть выполнение операции заняло отрезок времени [t1,t2].
Однако приведённый выше ответ не является единственно возможным. Дело в том, что мы не обязаны принимать в качестве логической единицы всегда состояние "спин вверх", а в качестве логического нуля - состояние "спин вниз": в разные моменты времени можно принимать разные определения логического нуля и единицы. Примем, например, определение, схематически показанное на рисунке. Красными стрелками показано направление спина, соответствующее логическому нулю в данный момент времени, а синими стрелками - направление, соответствующее логической единице. Чёрные стрелки - направление спина электрона в случае, когда начальное направление спина было "вверх".
При такой интерпретации спинового состояния получается, что если начальное состояние - логическая 1, то оно останется единицей вплоть до момента времени tx, после которого оно перейдёт в логический 0. И наоборот, если вначале был логический 0, то в момент времени tx он превратится в логическую единицу. Так что выполнение логической операции происходит мгновенно в момент времени tx.
Конечно, момент времени tx сам по себе ничем не выделен - это мы его выделили специальным выбором состояний, соответствующих логическим 0 и 1 в разные моменты времени. Можно было бы устроить и так, чтобы выполнение операции произошло в любой другой (заданный) момент времени - как во время импульса магнитного поля, так и до него или после него. Можно в принципе и не включать никакое магнитное поле и вообще ничего не делать, а только переопределить, начиная с некоторого момента, состояния нуля и единицы, - то, что было раньше нулём, обозвать единицей, и наоборот. Теперь уже видно, что выполнение логической операции НЕ - это вовсе не физический процесс, а просто "преобразование координат", которое с равным успехом может совершаться активно (т. е. как некоторое "движение" при фиксированной "координатной сетке") или пассивно (т. е. как изменение "координатной сетки"). (Вспомним, кстати, что в аналитической механике (в которой нет трения) всякое движение представляет собой всего лишь каноническое преобразование фазового пространства; обратимые вычисления представляют собой аналог движения без трения.)
Ещё несколько замечаний. Во-первых, мы сейчас говорили о логической операции НЕ; но всё то же самое относится и к любой другой (двух- или трёхбайтовой) элементарной обратимой логической операции, а значит, и к обратимым вычислениям вообще. Во-вторых, мы показали, что выполнение обратимой логической операции происходит "вне времени"; добавим, что оно происходит и "вне пространства". Это ясно уже из того, что, согласно теории относительности, время и пространство неотделимы друг от друга. И, в-третьих, мы использовали в нашем примере спин электрона, т. е. чисто квантовую величину; однако мы не использовали никакой "квантовой специфики" спина электрона, так что наши выводы справедливы и для чисто классических реализаций обратимого вычисления (например, для "бильярдного компьютера", который придумал, кажется, Тоффоли лет двадцать назад).
Теперь о том, как понимать утверждение, что обратимые вычисления, содержащие сколь угодно большое число элементарных операций, в принципе можно выполнять "мгновенно". Словам "мгновенное выполнение вычислений" можно придать как минимум два различных смысла - назовём их "мгновенное выполнение в физическом смысле" и "мгновенное выполнение в математическом смысле".
"Мгновенное выполнение (обратимого вычисления) в физическом смысле" означает вот что. Есть некоторая физическая система с "входом" и "выходом"; ну, например, какая-нибудь микросхема, у которой с одной стороны торчат несколько проводков, играющих роль "входа", и с другой стороны - несколько проводков, играющих роль "выхода". Мгновенное вычисление заключается в том, что мы подаём на "вход" какие-то данные и тут же считываем с "выхода" ответ. Ничего принципиально невозможного тут нет: мы видели на примере операции НЕ, что обратимые вычисления можно свести к преобразованию координат. Таким образом, мы можем записать исходные данные в одной "системе координат" и сразу же прочитать результат вычислений в другой "системе координат".
Но всякое ли обратимое вычисление (т. е. всякое ли взаимно однозначное отображение множества всех возможных начальных данных на множество всех возможных результатов вычисления) можно в принципе реализовать описанным здесь образом, т. е. посредством перехода от одной системы координат к другой? Чтобы понять, какие тут возможны ограничения, попробуем выяснить, что же это за множество, на котором мы вводим разные координатные сетки. В случае, когда имеется (хранится и перерабатывается) только один бит информации, множество состояний системы (фазовое пространтво) представляет собой окружность, как показано на рисунке:
Когда имеется N бит информации, то пространтвом состояний будет декартово произведение N окружностей, т. е. N-мерный тор. Так что преобразованием координат, посредством которого реализуется обратимое вычисление, будет преобразование (непрерывное, взаимно однозначное, сохраняющее объём) N-мерного тора в себя. Такие преобразования, как правило, являются перемешивающими, т. е. две близкие друг к другу точки после преобразования могут оказаться на значительном расстоянии друг от друга, и наоборот, две удалённые друг от друга точки N-мерного тора могут в результате преобразования приблизиться друг к другу. Иначе говоря, вдоль некоторых направлений на торе происходит растяжение, а вдоль некоторых других направлений - сжатие. Так вот, для того, чтобы данное преобразование можно было использовать для "мгновенного вычисления", необходимо, чтобы это преобразование не приводило к очень большим (экспоненциально большим) растяжениям и сжатиям. Иначе вычислительный процесс окажется неустойчивым: даже очень малая ошибка, допущенная при записи исходных данных в систему, приведёт к большой ошибке в считываемом результате вычисления. Таким образом, для реализации какого-нибудь обратимого вычисления как "мгновенного вычисления в физическом смысле" необходимо подобрать преобразование N-мерного тора в себя (где N -количество бит информации, вовлечённой в вычисления), реализующее данное вычисление и не приводящее к экспоненциально большим растяжениям и сжатиям тора. По-видимому, требование существования такого преобразования - это главное требование, нужное для осуществимости "мгновенных вычислений в физическом смысле".
Теперь о "мгновенных вычислениях в математическом смысле". "Математическая длительность вычисления" измеряется числом элементарных логических операций, которые нужно проделать, чтобы получить результат вычисления. Конечно, "мгновенность" не может означать, что число элементарных операций равно нулю; поэтому будем подразумевать под "мгновенными вычислениями в математическом смысле" вычисления, требующие не слишком большого числа элементарных операций. Слова "не слишком большое число операций" можно конкретизировать по-разному: можно, например, под этим подразумевать "не экспоненциально большое (по отношению к N - количеству бит информации) число операций", или "число операций, зависящее от N степенным образом", или "число операций, не превышающее 100N2", или что-нибудь ещё в этом же роде. (Заметим, что наши "мгновенные вычисления" и вычисления класса сложности P - это не одно и то же.)
Всякое ли обратимое вычисление может быть проделано "мгновенно"? Простой подсчёт показывает, что нет. Действительно, пусть N - разрядность (число битов, задействованных в процессе вычислений). Тогда число различных состояний на входе и на выходе равно 2N, а число различных функций, которые могут быть вычислены обратимо, будет равно 2N! (2N факториал). Количество различных элементарных обратимых операций на совокупности N битов - около N3 (так как среди них есть трёхбитовые операции). Пусть A(N) - число элементарных операций, достаточное для того, чтобы реализовать любую обратимую функцию на N битах. Тогда количество таких обратимых функций не превышает N3A(N). То есть 2N!<N3A(N). Отсюда получаем, что A(N)>2N для больших N, т. е. не любое обратимое вычисление можно реализовать с помощью малого (не экспоненциально большого) числа элементарных операций.
Однако далеко не всякая "обратимая" логическая функция (т. е. функция, которую можно реализовать посредством цепочки обратимых элементарных логических операций) может представлять какой-либо интерес. Как правило, интерес представляют такие функции, которые могут быть вычислены с помощью не очень сложного алгоритма (т. е. посредством не очень длинной пограммы). Выполнение такого "не очень сложного алгоритма" представляет собой многократное повторение цепочки из небольшого числа элементарных операций, выполняемых на небольшом числе битов (ячеек памяти). Причём необходимое число повторений цепочки может быть очень большим (экспоненциально большим). Так, например, нахождение наименьшего делителя N-значного (в двоичной системе счисления) числа может быть выполнено путём повторения цепочки, состоящей из около 99N элементарных операций (наверное, можно и меньше) над около 8.5N битами, а число повторений составляет 2N/2+2N. Оказывается, что можно обойтись при этом только обратимыми элементарными операциями: операциями НЕ, КОНТРОЛИРУЕМОЕ НЕ и гейтом Тоффоли (таким образом, вычисление будет обратимым).
Для таких вот обратимых вычислений, которые могут быть реализованы посредством "не слишком сложных алгоритмов", уже можно предположить, что их можно выполнить "мгновенно в математическом смысле". Более строго наше предположение можно сформулировать в виде следующей гипотезы:
Определим сначала функционал L[f], который для любой "обратимой" логической функции f даёт минимальное число обратимых элементарных операций, посредством которого можно реализовать эту функцию. Теперь гипотеза: существует такая неубывающая функция A(x) натурального аргумента, что для любой "обратимой" логической функции f и для любого натурального R будет выполняться неравенство
L[fR]<A(L[f]),
где fR означает R-кратное повторение выполнения функции f. Кроме того, функция A(x) с увеличением x возрастает не быстрее, чем O(xa) с некоторым натуральным a. (Может быть, даже можно усилить нашу гипотезу, потребовав, чтобы A(x) росло не быстрее, чем O(x).)
Если наша гипотеза верна, то, например, нахождение делителя N-значного числа потребует не более, чем O(Na) элементарных операций. Это, впрочем, ещё не означает, что проблема факторизации (т. е. разложения на простые множители) больших чисел переходит из класса сложности NP в класс P: хотя, согласно нашей гипотезе, существует цепочка операций, позволяющая вычислить простые делители данного числа за полиномиальное время, но нахождение этой цепочки может потребовать экспоненциально большое время (под временем, конечно, здесь подразумевается количество элементарных операций).
