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

Начнем с описания поставленной задачи: факторизации числа N на простые множители (например, число 51688 может быть разложено как 2 X 7 X 13 X 71). Удобный способ оценить, как быстро конкретный

лгоритм может решить задачу, состоит в том, чтобы выяснить, как число шагов, требуемых для выполнения алгоритма, растет с увеличением размера входных данных.

Для задачи факторизации входными данными является само чис-

о которое мы хотим факторизовать; следовательно, длина входа

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

На обычных компьютерах самые лучшие известные алгоритмы факторизации выполняются за О (ехр [(64/9)/(ln7V)i/3(inln7V)/]) шагов [3]. Таким образом, этот алгоритм растет экспоненциально с размером входных данных logTV. Например, в 1994 году 129-значное чис-

о (известное как RSA129 [3]) было успешно факторизовано с использованием этого алгоритма на приблизительно 1600 рабочих станциях, распределенных по всему миру; полная факторизация заняла восемь месяцев. Используя этот результат для оценки множителя перед приведенной выше экспонентой, получим, что потребуется приблизительно 8 • 10 лет для факторизации теми же компьютерами 250-значного числа; аналогично, для 1000-значного числа потребуется 10 лет (значительно больше, чем возраст вселенной). Трудность факторизации

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

Недавно был разработан алгоритм для факторизации чисел на квантовом компьютере, который реализуется за О ((logTV)) шагов, где е - некоторое малое число [1]. Он приблизительно квадратично зависит от размера входных данных, поэтому факторизация 1000-значного числа с помощью такого алгоритма потребует только несколько

миллионов шагов. Это означает, что криптосистемы с открытым ключом, основанные на факторизации, могут быть взломаны.

Чтобы дать представление о том, за счет чего происходит такое

кспоненциальное улучшение, рассмотрим элементарный квантовоме-ханический эксперимент, который показывает, где могут быть зало-

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

ей. Эти частицы претерпевают унитарную эволюцию, и в конце процесса измерения мы видим интерференционную картину, когда обе ще-

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

1. Вычисления на атомных расстояниях

Квантовые компьютеры будут проводить вычисления на атомных расстояниях [5, 6]. На рис. 1 приведены результаты полученных Кейе-сом в 1988 году [7] оценок изменения с годами числа примесей в основаниях биполярных транзисторов, требуемых для логических операций. Можно считать, что этот график показывает число электронов, необходимых для хранения одного бита информации. Экстраполяция графика значает, что в течение следующих двух десятилетий мы могли бы проводить вычисления на атомных расстояниях.

2. Обратимое вычисление

В чем состоят трудности попыток построить классическую вычислительную машину на таких малых расстояниях? Одна из наиболее крупных проблем программы миниатюризации обычных компьютеров связана с выделением теплоты.

Уже в 1961 году Ландауэр исследовал физические ограничения, на-агаемые на вычисления диссипацией [8]. Удивительно, но ему удалось

1950

1970 1990 2010

Годы

Рис. 1. График из работы [7], показывающий изменение с годами числа не-однородностей в биполярных транзисторах, используемых для выполнения логических операций.

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

Работа по классическим обратимым вычислениям заложила основы для развития квантовомеханических компьютеров. На квантовом компьютере программы выполняются посредством унитарной эволюции входных данных, которые задаются состоянием системы. Так как нитарные операторы U обратимы, и = С/", то на квантовом компьютере вычисления всегда можно обратить.

3. Классические универсальные машины и логические гейты

Рассмотрим теперь основные логические элементы, используемые в вычислении, и объясним, как обычные компьютеры могут быть использованы для любого «разумного» вычисления. Разумное вычисление - такое, которое может быть записано в терминах некоторого