Разложение на множители

Квантовый параллелизм делает квантовые компьютеры потенциально очень мощными. Квантовый компьютер может одновременно исследовать все возможные решения той или иной проблемы, даже самой сложной. Пример такой проблемы – разложение на множители. Число раскладывается на множители, если его можно представить как произведение двух или более целых чисел, бóльших единицы. Например, число 15 можно разложить на множители, потому что его можно записать как произведение 3 и 5. А число 7 нельзя разложить на множители, потому что единственный способ записать его как произведение двух положительных целых чисел – это 7 раз по 1. Числа, которые нельзя разложить на множители, называют простыми. Вот несколько первых простых чисел – 2, 3, 5, 7, 11, 13… Нетрудно показать, что существует бесконечное число простых чисел.

Возьмем два больших простых числа, состоящих из 200 цифр каждое, и перемножим их. Мы получим число из 400 цифр. Перемножать два числа из 200 цифр – утомительная, но вполне посильная задача для цифрового компьютера, классического или квантового. Возьмем получившееся произведение из 400 цифр, покажем его кому-нибудь, кто не знает, какими были два первоначальных простых числа, и попросим разложить его на множители. Наше число из 400 цифр, очевидно, можно разложить на множители, и если нам известны оба первоначальных числа из 200 цифр, то очень легко проверить, что их произведение действительно дает наше число из 400 цифр. Но поиск этих двух множителей, если мы не знаем их заранее, оказывается сложным. По существу, единственный известный способ найти эти множители – перебирать все возможные числа из 200 цифр по очереди до тех пор, пока мы не найдем то одно, на которое делится наше число из 400 цифр. (Разумеется, существуют уловки, позволяющие быстро исключить некоторые числа, но они не слишком помогают.) К сожалению, чисел из 200 цифр очень много. Используя наш любимый пример, чисел из 200 цифр намного больше, чем элементарных частиц во всей Вселенной.

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

Доказанная сложность разложения на множители больших чисел стала основанием для одного эффективного метода защиты информации. Всякий раз, когда мы пользуемся своей банковской кредитной карточкой или покупаем что-то через Интернет, безопасность этой транзакции защищена методом, получившим название «шифрование» с открытым ключом. Допустим, мы используем кредитную карту, чтобы купить несколько экземпляров этой книги на сайте Amazon.com. Amazon отправляет нам «открытый ключ» (public key) – большое число, которое является произведением двух меньших простых чисел. Наш компьютер использует этот открытый ключ, чтобы зашифровать или «закодировать» информацию, которую мы отправляем на Amazon, включая информацию о кредитной карте. Чтобы расшифровать эту информацию, Amazon использует «закрытый ключ» (private key), состоящий из двух простых чисел, которые, если их перемножить, дадут открытый ключ. Таким образом, любой, у кого есть открытый ключ, может зашифровать информацию, но чтобы ее расшифровать, нужен закрытый ключ, состоящий из множителей открытого ключа. Шифрование с открытым ключом, очевидно, является полезным решением, и его эффективность основана как раз на том, что разложение на сомножители – сложная задача. Открытый ключ из 256 цифр очень трудно «взломать» посредством классических вычислений, и сейчас он считается более чем достаточным для защиты большинства видов информации.

Однако в 1994 г. Питер Шор из лаборатории AT&T[38]показал, что даже относительно небольшой квантовый компьютер, обладающий всего несколькими тысячами кубитов, может без труда разложить на множители число из 400 цифр. В сущности, он показал, как организовать это вычисление таким образом, чтобы верные множители можно было выявить из «фонового шума» потенциальных множителей. Чтобы понять, как можно определить верные множители, комбинируя их волны в квантовом вычислении, давайте снова вспомним метафору симфонии: если Бетховен аранжирует мелодию для скрипки, виолончели, флейты и тромбона, то мы услышим эту мелодию независимо от того, что и как играют остальные инструменты оркестра.

Предположим, что, пока квантовый компьютер исследует все возможные множители, мы грубо вмешиваемся в его работу и измеряем его кубиты, чтобы узнать, что делает компьютер. Он ответит: «О, я только что посмотрел на [какую-то пару чисел из 200 цифр каждое], чтобы выяснить, даст ли их перемножение правильный ответ». Почти всегда эти числа не будут решением задачи. Опрашивать квантовый компьютер, когда он исследует все возможные решения проблемы разложения на множители, в общем-то, все равно что выбрать одно из возможных решений случайным образом. Чтобы извлечь из такого вычисления максимальную пользу, вы не должны вмешиваться в работу компьютера, пока он вычисляет. Нужно позволить каждому из параллельных вычислений идти своим чередом, интерферируя с остальными; только при этом условии симфоническая природа квантового вычисления поможет нам найти верные сомножители.

Поиск

Разложение на множители – не единственная сложная проблема, которую в принципе могут эффективно решить квантовые компьютеры. В 1996 г. Лов Гроувер из Bell Laboratories показал, что квантовые компьютеры совершают операции поиска эффективнее, чем классические. Предположим, вы забыли, в какой из своих четырех карманов положили свой бумажник. Сначала вы проверяете один карман, потом другой. В худшем случае вам придется проверить все четыре кармана, а в среднем – два. Но предположим, что вы можете использовать квантовый параллелизм, то есть проверить все карманы сразу. Гроувер показал: чтобы найти бумажник, нужно произвести операцию квантового поиска всего два раза.

Конечно, алгоритм Гроувера работает и при количестве вариантов больше четырех. Если вы ищете нечто, что может находиться в 100 возможных местах, то чтобы найти его, достаточно выполнить квантовый поиск всего 10 раз. При классическом поиске вам придется выполнить в среднем 50 операций. Если вы ищете что-то в миллионе возможных мест, нужно будет выполнить квантовый поиск всего 1000 раз вместо полумиллиона классических поисковых операций. В общем, количество операций квантового поиска, необходимых для того, чтобы найти искомое, составляет квадратный корень из количества мест, в которых оно может находиться.

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

Дата добавления: 2015-11-14