С.Л.Браунштейн
(Samuel L. Braunstein) ${ }^{1}$

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

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

Схематически описывается модель квантового компьютера, а также некоторые тонкости в его программировании. Алгоритм Шора $[1,2]$ эффективной факторизации чисел на квантовом компьютере представлен в двух частях: квантовая процедура внутри алгоритма и классический алгоритм, который требует квантовую процедуру. Обсуждается
${ }^{1}$ Encyclopedia of Applied Physics, Update, WILEY-VCH, 1999.
Перевод В. В. Белокурова.
математическая структура в факторизации, которая делает алгоритм Шора возможным. В заключении дается общий взгляд на осуществимость и перспективы квантовых вычислений в ближайшие годы.

Начнем с описания поставленной задачи: факторизации числа $N$ на простые множители (например, число 51688 может быть разложено как $2^{3} \times 7 \times 13 \times 71$ ). Удобный способ оценить, как быстро конкретный алгоритм может решить задачу, состоит в том, чтобы выяснить, как число шагов, требуемых для выполнения алгоритма, растет с увеличением размера входных данных.

Для задачи факторизации входными данными является само число $N$, которое мы хотим факторизовать; следовательно, длина входа есть $\log N$. (Основание логарифма определяется нашей системой счисления. Так, основание 2 задает длину в двоичной системе; а основание 10 в десятичной). «Приемлемыми» алгоритмами являются те, в которых число шагов растет как некоторый полином небольшой степени от размера входных данных (со степенью, возможно, 2 или 3 ).

На обычных компьютерах самые лучшие известные алгоритмы факторизации выполняются за $O\left(\exp \left[(64 / 9)^{1 / 3}(\ln N)^{1 / 3}(\ln \ln N)^{2 / 3}\right]\right)$ шагов [3]. Таким образом, этот алгоритм растет экспоненциально с размером входных данных $\log N$. Например, в 1994 году 129-значное число (известное как $R S A 129\left[3^{\prime}\right]$ ) было успешно факторизовано с использованием этого алгоритма на приблизительно 1600 рабочих станциях, распределенных по всему миру; полная факторизация заняла восемь месяцев. Используя этот результат для оценки множителя перед приведенной выше экспонентой, получим, что потребуется приблизительно $8 \cdot 10^{5}$ лет для факторизации теми же компьютерами 250 -значного числа; аналогично, для 1000 -значного числа потребуется $10^{25}$ лет (значительно больше, чем возраст вселенной). Трудность факторизации больших чисел является определяющим фактором для криптосистем с открытым ключом, таких, какие используются в банках. Там такие коды считаются надежными в силу сложности факторизации чисел с приблизительно 250 знаками.

Недавно был разработан алгоритм для факторизации чисел на квантовом компьютере, который реализуется за $O\left((\log N)^{2+\varepsilon}\right)$ шагов, где $\varepsilon$ – некоторое малое число [1]. Он приблизительно квадратично зависит от размера входных данных, поэтому факторизация 1000 -значного числа с помощью такого алгоритма потребует только несколько
миллионов шагов. Это означает, что криптосистемы с открытым ключом, основанные на факторизации, могут быть взломаны.

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