Не существует простого способа разложить на множители число из 400 цифр с помощью классического компьютера. Одним из самых сложных классических вычислений в истории было разложение на множители числа из 128 цифр, осуществленное несколько лет назад. Для этого вычисления использовались сотни классических компьютеров, соединенных через Интернет, и в этом процессе были сделаны триллионы логических операций с миллиардами битов. Позже было проведено разложение на множители числа, состоящего из 200 цифр. Но разложение на множители произвольного числа из 400 цифр с помощью известных нам сегодня методов, вероятно, еще в течение многих лет останется невозможным.
Доказанная сложность разложения на множители больших чисел стала основанием для одного эффективного метода защиты информации. Всякий раз, когда мы пользуемся своей банковской кредитной карточкой или покупаем что-то через Интернет, безопасность этой транзакции защищена методом, получившим название «шифрование» с открытым ключом. Допустим, мы используем кредитную карту, чтобы купить несколько экземпляров этой книги на сайте Amazon.com. Amazon отправляет нам «открытый ключ» (public key) – большое число, которое является произведением двух меньших простых чисел. Наш компьютер использует этот открытый ключ, чтобы зашифровать или «закодировать» информацию, которую мы отправляем на Amazon, включая информацию о кредитной карте. Чтобы расшифровать эту информацию, Amazon использует «закрытый ключ» (private key), состоящий из двух простых чисел, которые, если их перемножить, дадут открытый ключ. Таким образом, любой, у кого есть открытый ключ, может зашифровать информацию, но чтобы ее расшифровать, нужен закрытый ключ, состоящий из множителей открытого ключа. Шифрование с открытым ключом, очевидно, является полезным решением, и его эффективность основана как раз на том, что разложение на сомножители – сложная задача. Открытый ключ из 256 цифр очень трудно «взломать» посредством классических вычислений, и сейчас он считается более чем достаточным для защиты большинства видов информации.
Однако в 1994 г. Питер Шор из лаборатории AT&T
[28] показал, что даже относительно небольшой квантовый компьютер, обладающий всего несколькими тысячами кубитов, может без труда разложить на множители число из 400 цифр. В сущности, он показал, как организовать это вычисление таким образом, чтобы верные множители можно было выявить из «фонового шума» потенциальных множителей. Чтобы понять, как можно определить верные множители, комбинируя их волны в квантовом вычислении, давайте снова вспомним метафору симфонии: если Бетховен аранжирует мелодию для скрипки, виолончели, флейты и тромбона, то мы услышим эту мелодию независимо от того, что и как играют остальные инструменты оркестра.
Предположим, что, пока квантовый компьютер исследует все возможные множители, мы грубо вмешиваемся в его работу и измеряем его кубиты, чтобы узнать, что делает компьютер. Он ответит: «О, я только что посмотрел на [какую-то пару чисел из 200 цифр каждое], чтобы выяснить, даст ли их перемножение правильный ответ». Почти всегда эти числа не будут решением задачи. Опрашивать квантовый компьютер, когда он исследует все возможные решения проблемы разложения на множители, в общем-то, все равно что выбрать одно из возможных решений случайным образом. Чтобы извлечь из такого вычисления максимальную пользу, вы не должны вмешиваться в работу компьютера, пока он вычисляет. Нужно позволить каждому из параллельных вычислений идти своим чередом, интерферируя с остальными; только при этом условии симфоническая природа квантового вычисления поможет нам найти верные сомножители.
Поиск
Разложение на множители – не единственная сложная проблема, которую в принципе могут эффективно решить квантовые компьютеры. В 1996 г. Лов Гроувер из Bell Laboratories показал, что квантовые компьютеры совершают операции поиска эффективнее, чем классические. Предположим, вы забыли, в какой из своих четырех карманов положили свой бумажник. Сначала вы проверяете один карман, потом другой. В худшем случае вам придется проверить все четыре кармана, а в среднем – два. Но предположим, что вы можете использовать квантовый параллелизм, то есть проверить все карманы сразу. Гроувер показал: чтобы найти бумажник, нужно произвести операцию квантового поиска всего два раза.
Конечно, алгоритм Гроувера работает и при количестве вариантов больше четырех. Если вы ищете нечто, что может находиться в 100 возможных местах, то чтобы найти его, достаточно выполнить квантовый поиск всего 10 раз. При классическом поиске вам придется выполнить в среднем 50 операций. Если вы ищете что-то в миллионе возможных мест, нужно будет выполнить квантовый поиск всего 1000 раз вместо полумиллиона классических поисковых операций. В общем, количество операций квантового поиска, необходимых для того, чтобы найти искомое, составляет квадратный корень из количества мест, в которых оно может находиться.
Какие еще задачи квантовые компьютеры могут решать более эффективно, чем классические? Чтобы по максимуму использовать симфоническую природу квантового параллелизма, нужно позволить всем элементам квантового вычисления интерферировать друг с другом. Но как непросто написать симфонию, столь же трудно и создать необходимую квантовую интерференцию, тем более что есть всего несколько квантовых алгоритмов, таких как разложение на сомножители и поиск, которые в настоящее время квантовые компьютеры могут выполнять лучше, чем их классические аналоги.
Создание квантового компьютера
Осенью 1994 г. мне позвонил Джефф Кимбл, профессор физики Калифорнийского технологического института. Джефф прочел пару моих статей о квантовых вычислениях и хотел обсудить возможность создания квантовых логических элементов на основе фотонов.
Джефф Кимбл – долговязый техасец, который хорошо умеет обращаться с атомами и светом. Его представили мне как человека, который «так сильно сжал свет, как до него еще никому не удавалось», и если этот свет чувствовал себя так же, как моя рука после рукопожатия Джеффа, я склонен этому верить. Мы начали беседу, и я заметил две вещи. Во-первых, Джефф без всяких колебаний говорит то, что думает. Если он смотрит на ваше уравнение и произносит, со своим мягким техасским акцентом, что «есть проблема в Ривер-сити»
[29], это значит, что вы в беде. Во-вторых, когда он описывает свои эксперименты, я понимаю примерно одно слово из трех.
Той осенью, неделю за неделей, я много общался с Джеффом и его студентами, и постепенно стал понимать, чем они занимаются. Джефф брал отдельные фотоны и заставлял их взаимодействовать с отдельными атомами. По сути, он помещал фотон в емкость с атомом и встряхивал их. Емкость представляла собой оптическую полость, состоящую из двух зеркал на расстоянии нескольких миллиметров друг от друга. Фотон десятки тысяч раз метался туда-сюда между зеркалами, пока, наконец, не вырывался на свободу. Джефф вводил в полость атомы цезия, в то же время освещая ее фотонами лазерного пучка, а потом смотрел, что получилось. Каждый фотон и каждый атом проводили в небольшом пространстве оптической полости существенную долю секунды, и у них было достаточно времени для взаимодействий друг с другом.
