Одним из первых результатов в вычислительной математике, который предшествовал последующему развитию большой части теоретической науки о компьютерных вычислениях, было показанное в работах Чёрча [1936], Тьюринга [1936] и Поста [1936] различие между вы-
*SIAM J. Comput., 26:5, 1997, 1484-1509.

числимыми и невычислимыми функциями. Наблюдение, что несколько различных определений того, что значит для функции быть вычислимой, приводит к одному и тому же множеству вычислимых функций, это ведет к основному тезису Чёрча, согласно которому все вычислительные устройства могут быть смоделированы на машине Тьюринга. Этот тезис сильно упрощает изучение вычислительных процедур, так как сводит поле возможных исследований, состоящее из бесконечного числа потенциально возможных вычислительных устройств, к изучению работы машин Тьюринга. Тезис Чёрча не является математической теоремой, для того чтобы сделать его теоремой, нам бы понадобилось знать точное математическое описание таких вычислительных устройств. Такое описание, однако, всегда оставляет возможным создание некоего реального вычислительного устройства, которое не удовлетворяет такому точному математическому описанию, и, таким образом, окончательная математическая теорема должна быть более слабой, чем оригинальный тезис Чёрча.

С появлением реальных компьютеров стало очевидно, что различие между вычислимыми и невычислимыми функциями является слишком грубым; вычислительная наука сейчас интересуется точной эффективностью, с которой определенная функция может быть вычислена. С другой стороны, такая эффективность является слишком точной величиной, определяющей сложность предлагаемых вычислений. Общепринятым является компромисс между грубостью и точностью, различающий эффективные и неэффективные вычисления функций по тому, является ли длительность вычислений полиномиальной или сверхполиномиальной (например, экспоненциальной, прим. перев.) по длине входных данных. Класс вычислительных проблем, которые могут быть решены с помощью алгоритмов, содержащих полиномиальное по величине входных данных число шагов, известен как класс $P$.

Чтобы данная классификация имела смысл, она не должна зависеть от машины. Другими словами, нам необходимо знать, зависит ли вычислимость определенной функции за полиномиальное время от того, какое было использовано вычислительное устройство. С этим связана следующая количественная версия тезиса Чёрча, которую Вергис (Vergis), Штейглиц (Steiglits) и Дикинсон (Dickinson) [1986] назвали «сильным тезисом Чёрча», и которая является частью «тезиса инвариантности» [van Emde Boas, 1990].

Тезис 1.1. (Количественный тезис Чёрча). Любое физическое вычислительное устройство может быть смоделировано машиной Тьюринга, причем этот процесс полиномиален по числу ресурсов, которые были бы затрачены этим вычислительным устройством.

Читатель, не знакомый с машиной Тьюринга, может себе представить обыкновенный компьютер, память которого растет линейно с длиной вычислений, поскольку эти два класса вычислительных машин могут эффективно моделировать друг друга. В утверждениях этого тезиса к машине Тьюринга иногда присовокупляют генератор случайных чисел, поскольку до сих пор неясно, существуют ли генераторы псевдослучайных чисел, могущие эффективно моделировать истинный генератор случайных чисел, необходимый для разнообразных целей.

В предложенном выше тезисе имеют место два тонких момента. Первый – это слово «физический». Исследователи уже создали модели вычислительного устройства, которое нарушает приведенный выше количественный тезис Чёрча, но большинство из этих моделей отвергаются по причине того, что они не являются «физическими», другими словами, не могут быть реально построены и использованы в работе. Другим тонким моментом является слово «ресурсы», значение которого определено выше не полностью. Имеется два типа ресурсов, которые ограничивают возможности цифровых компьютеров по решению сложных задач: временные (шаги вычислений) и пространственные (требуемая память). Также имеются и другие ресурсы, имеющие отношение к аналоговым вычислениям; предлагались некие аналоговые машины, которые, возможно, способны решить NP-проблему за полиномиальное время, но при этом требуется экспоненциальное увеличение точности деталей, или экспоненциальный рост затраченной энергии (См. Vergis и др. [1986] и Steiglitz [1988]; этот результат также содержится в работе Canny и Reif [1987] и Choi и др. [1995] о трехмерных кратчайших путях.)

Для квантового вычисления в дополнение к пространственным и временным ресурсам существует также третий потенциально важный ресурс – точность. Для того чтобы квантовый компьютер работал, по крайней мере в любой предполагаемой реализации, необходимо, чтобы имелась возможность менять квантовое состояние составляющих его объектов (например, атомов, фотонов или ядерных спинов). Эти изменения, конечно, не могут быть совершенно точными, они необходимо должны содержать небольшую неустранимую неточность. Если эта неточность постоянна (то есть, не зависит от величины входных данных), тогда неизвестно, как на квантовом компьютере вычислить за полиномиальное время функцию, которая не может быть вычислена за полиномиальное время на класеическом компьютере с генератором случайных чисел. Однако, если мы положим, что точность полиномиально растет с увеличением величины входных данных (то есть, если число битов точности будет логарифмически расти по отношению к величине входных данных), то получим более мощный тип компьютера. В случае классического компьютера полиномиальный рост точности не приводит к повышению вычислительной мощности, хотя этого результата можно добиться при экспоненциальном росте точности [Hartmanis and Simon, 1974, Vergis et al., 1986].

Как мы знаем, возможная точность в операциях с квантовыми вычислениями, определяется не фундаментальными физическими законами, а свойствами материалов, из которых построен квантовый компьютер, и его архитектурой. В настоящее время неясно, какие типы архитектуры, если они вообще существуют, дадут высокую точность. Если точность квантового компьютера будет достаточно велика, чтобы сделать его более мощным, чем классический компьютер, то для понимания его потенциальных возможностей следует считать саму эту точность ресурсом переменной величины. Считать точность большой постоянной величиной (хотя для любой данной машины это почти наверняка так) – это примерно то же самое, что трактовать классический компьютер как конечный автомат: поскольку память любого компьютера ограничена, эта точка зрения технически правильна, но не очень полезна.

Из-за замечательной эффективности наших математических моделей процесса вычислений специалисты по вычислениям стали забывать, что этот процесс определяется законами физики. Например, в формулировке количественного тезиса Чёрча у van Emde Boas [1990] слово «физический» заменяется на слово «разумный». Трудно представить себе в этом контексте такое определение «разумности», которое не означало бы «физическую реализуемость», то есть возможность построить и привести в действие такую вычислительную машину!

Неудачи всех предлагавшихся контрпримеров убедили специалистов по вычислениям в истинности количественного тезиса Чёрча. Однако большинство этих контрпримером было основано на законах классической механики, тогда как мир в действительности описывается законами квантовой механики. Квантовые объекты часто ведут себя вопреки предсказаниям нашей интуиции, основанной на законах классической механики. Поэтому кажется правдоподобным, что естественной мерой вычислительной мощности классической механики являются машины Тьюринга ${ }^{1}$, в то время, как вычислительная мощность квантовой механики может быть больше.

Первым, кто занялся взаимодействием между вычислениями и квантовой механикой, по-видимому, является Бенёв $[1980,1982$ a, $1982 \mathrm{~b}]$. Хотя он не задавался вопросом, являются ли квантовомеханические вычисления более мощными, ему удалось показать, что обратимая унитарная эволюция в состоянии реализовать вычислительный потенциал машины Тьюринга, и таким образом показать, что вычислительная мощность квантовой механики не меньше, чем у классического компьютера. Эти работы положили начало дальнейшим исследованиям квантовых компьютеров.

Фейнман $[1982,1986]$, по-видимому, первым предположил, что квантовая механика может привести к более мощным вычислительным средствам, чем машина Тьюринга. Он привел аргументы о том, почему квантовая механика находится за пределами вычислений, моделируемых на классическом компьютере. Также он указал возможность использования компьютера, основанного на принципах квантовой механики, для устранения этой проблемы, и, таким образом, он в неявном виде задался обратным вопросом: может ли компьютер, построенный с использованием квантовомеханических принципов, вычислять более
${ }^{1}$ Мне кажется, что этот вопрос решен не окончательно и заслуживает дальнейшего исследования. См. Vergis et al. [1986], Steiglitz [1988] и Rubel [1989]. В частности, хорошим кандидатом на роль контрпримера к количественному тезису Чёрча может быть турбулентность, поскольку нетривиальную динамику на многих масштабах длины трудно смоделировать на классическом компьютере. эффективно, чем классический? Дойч $[1985,1989]$ был первый, кто задался этим вопросом явно. Для решения этого вопроса он определил квантовые машины Тьюринга и квантовые схемы, а также изучил их свойства.

Вопрос, приведет ли использование квантовой механики в компьютерах к увеличению их вычислительной мощности, недавно был поставлен в работах Deutsch, Jozsa [1992] и Berthiaume, Brassard [1992a, 1992b]. В этих работах показано, что существуют задачи, которые быстро и точно решаются на квантовом компьютере, в то время как лишь на классическом компьютере они могут быть быстро решены с высокой вероятностью с помощью генератора случайных чисел. Однако в этих статьях не показано, как решать какую-либо задачу на квантовом компьютере за полиномиальное время, про которую неизвестно, решаема ли она за полиномиальное время с помощью генератора случайных чисел с малой вероятностью ошибки; это характеристика класса сложности BPP, который широко использется как класс эффективно решаемых задач.

Дальнейшая работа над этой проблемой была стимулирована статьей Bernstein и Vazirani [1993]. Одним из результатов, содержащихся в этой работе, является задача с оракулом (то есть проблема введения некой подпрограммы «черный ящик», которую компьютер может использовать, но машинный код ее неизвестен), которая может быть решена за полиномиальное время на квантовой машине Тьюринга, а на классическом компьютере ее решение требует сверхполиномиальное время. Этот результат был улучшен Саймоном [1994]. Он предложил более простую конструкцию задачи с оракулом, которая решается за полиномиальное время на квантовом компьютере, но требует экспоненциального времени на обычном компьютере. Действительно, в то время как задача Бернштейна и Вазирани кажется несколько надуманной, задача Саймона выглядит вполне естественной. Алгоритм Саймона вдохновил автора на работу, предлагаемую в этой статье.

Две проблемы теории чисел, которые были широко исследованы, но для которых так и не найдено полиномиальных по времени алгоритмов – это нахождение дискретных логарифмов и разложение числа на простые множители. [Pomerance, 1987, Gordon, 1993, Lenstra и Lenstra, 1993, Adleman и McCurley, 1995]. То, что эти проблемы крайне трудны для решения настолько общепринято, что на их основе построены некоторые криптографические алгоритмы, включая широко используемую криптосистему RSA публичных ключей, разработанную Ривестом, Шамиром, Адлеманом [Rivest, Shamir, Adleman, 1978]. Мы покажем, что эта проблема может быть решена на квантовом компьютере за полиномиальное время с малой вероятностью ошибки.

Сейчас никто не знает, как построить квантовый компьютер, хотя, как кажется, это вполне возможно исходя из законов квантовой механики. Были предложены несколько проектов таких компьютеров [Teich et al., 1988, Lloyd, 1993, 1994, Cirac и Zoller, 1995, DiVincenzo, 1995, Sleator и Weinfurter, 1995, Barenco et al., 1995b, Chuang и Yamomoto, 1995], но любой из таких проектов сталкивается с одной существенной проблемой [Landauer, 1995a, Landauer, 1996b, Unruh, 1995, Chuang et al., 1995, Palma et al., 1996]. Наиболее непреодолимая преграда заключается в явлении разрушения когерентности квантовой суперпозиции за счет взаимодействия компьютера с окружающей средой, и реализации преобразований квантового состояния с достаточной точностью для получения достоверных результатов после многих шагов вычислений. Оба этих препятствия становятся более трудными, когда размеры компьютера растут; таким образом, может оказаться, что возможно построить маленький квантовой компьютер, однако с увеличением размеров машины до размеров, достаточных, чтобы решать интересные вычислительные задачи, могут возникнуть фундаментальные проблемы.

Даже если никакого пригодного для реальных вычислений квантового компьютера никогда не будет построено, данное исследование может иллюстрировать проблему моделирования квантовой механики на классическом компьютере. Любые методы, позволяющие это сделать для произвольного гамильтониана, окажутся необходимыми при моделировании квантового компьютера. Поэтому всякий метод моделирования квантовой механики как максимум с полиномиальным замедлением может привести к полиномиальному по времени факторизационному алгоритму.

Данная работа организована следующим образом. В §2 мы предлагаем модель квантового компьютера, массива из квантовых гейтов, которую мы используем в оставшейся части статьи. В $\S \S 3$ и 4 мы предложим две подпрограммы, которые используются в наших алгоритмах: обратимое возведение в степень по модулю в § 3 и квантовое преобразование Фурье в $\S 4$. В §5 мы даем наш алгоритм разложения на простые числа, а в $\S 6$ – алгоритм извлечения дискретных логарифмов. В $\S 7$ мы кратко обсудим практическое применение квантовых вычислений и предложим возможные направления для дальнейшей работы.