В последнее время повысился интерес к задаче о физических ограничениях вычислительных процессов. В частности, темой многочисленных дискуссий стали вопросы энергетической цены вычислений или передачи информации и неизбежности диссипации энергии при вычислениях $[1-10]$. Несколько лет назад $[3,7]$ сложилось мнение, что вычис-
${ }^{\star}$ Journal of Statistical Physics, Vol. 29, № 3, 1982. Перевод О.А.Хрусталева, А. Г. Холмской.
ления связаны с диссипацией по той причине, что процессы вычисления необратимы. Однако в 1973 году Беннетт [2] построил обратимую модель процесса вычисления и обсудил термодинамически обратимые модели вычисления. Последние статьи на эту тему $[1,10]$, в которых утверждалось, что энергия при вычислениях обязательно рассеивается, критиковались Дойчем [5]. Ландауэр [11] подчеркнул важность окончательного выяснения вопроса о том, существуют ли модели вычислительных процессов, не связанные с рассеянием энергии. Фредкин и Тоффоли [12] построили классическую механическую бильярдную модель процесса вычисления без потери энергии. В других работах [13-15] построены квантовомеханические гамильтоновы модели машин Тьюринга и обратимых дискретных процессов. В этих моделях вычислительный процесс приводится в движение последовательными рассеяниями. Две из них диссипативны в том смысле, что состояние полной системы эволюционирует так, что со временем возрастают амплитуды нежелательных компонент в (чистом) состоянии. В другой модели [13] диссипация отсутствует. Эти свойства моделей следуют из предположения, что кинетическая энергия (рассеивателя) является линейной функцией импульса.

В представленной работе построены квантовомеханические гамильтоновы модели машин Тьюринга, не использующие механизм последовательного рассеяния. Эта модель содержит решетку, в которой некоторые конфигурации спинов $1 / 2$ вдоль определенной оси соответствуют частям машины Тьюринга. Изменения в такой системе описываются операторами переворота спина, действующими на спины, локализованные в определенных местах решетки. Поскольку никакие системы в модели не перемещаются, в ней отсутствуют такие источники диссипации, как расплывание волновых пакетов и т. п., присутствующие в других моделях $[14,15]$.

В следующем разделе дается краткий обзор теории машины Тьюринга. Затем следует изложение конструкции, представляющей собой машину Тьюринга вместе с системой записи как конфигурацию решетки спинов $\frac{1}{2}$. Соответствуюшая модель состояний конфигурации, проекционные операторы и элементарные операторы, производящие изменение состояний конфигурации, даны в разделе 3. Эти состояния и операторы используются в разделах 4 и 5 для построения, соответственно, зависящих и не зависящих от времени гамильтоновых моделей первых $J$ шагов машины Тьюринга.

В разделах 6 и 7 обсуждаются характеристики построенных моделей, свойства и ограничения измерений различных подсистем моделей. Оказывается, что модели с не зависящими от времени гамильтонианами не рассеивают энергию и эволюция таких моделей не приводит к разрушению состояний модели. Эффективность операций в таких системах такова, что отношение неопределенности энергии к скорости вычисления не превосходит $2 \pi \hbar$. Однако соответствующие гамильтонианы могут показаться слишком сложными. Не зависящие от времени гамильтонианы приводят к глобальной во времени эволюции, так что измерения, которые определяют параметры системы, оказываются крайне сложными. Такие измерения вызывают рассеяние энергии и возмущают состояния системы. (Глобальными во времени мы называем такие модели, которые, эволюционируя от состояния, представляющего $n$-й шаг вычисления, к состоянию, представляющему ( $n+1$ )-й шаг, проходят за промежуточное время через состояния, являющиеся линейными комбинациями состояний, представляющих все шаги вычисления. Модель локальна во времени, если промежуточные состояния являются линейной комбинацией только состояний $n$-го и ( $n+1$ )-го шагов вычисления.)

Зависящие от времени гамильтоновы модели также не приводят к разрушению состояний системы. Гамильтонианы менее сложные, и эволюция моделей локальна во времени. В результате измерения, которые должны установить, закончились ли вычисления, не столь трудны, как в предыдущих моделях, они не возмущают состояния системы и не приводят к диссипации энергии. Однако, в этом случае необходимо предусмотреть внешние устройства, управляющие последовательными шагами вычисления. В разделе 8 сравниваются некоторые аспекты рассмотренных моделей с моделями, предложенными в других работах [13-15].