Книга: Программируя Вселенную. Квантовый компьютер и будущее науки
Разложение на множители
Разложение на множители
Квантовый параллелизм делает квантовые компьютеры потенциально очень мощными. Квантовый компьютер может одновременно исследовать все возможные решения той или иной проблемы, даже самой сложной. Пример такой проблемы – разложение на множители. Число раскладывается на множители, если его можно представить как произведение двух или более целых чисел, б?льших единицы. Например, число 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[28] показал, что даже относительно небольшой квантовый компьютер, обладающий всего несколькими тысячами кубитов, может без труда разложить на множители число из 400 цифр. В сущности, он показал, как организовать это вычисление таким образом, чтобы верные множители можно было выявить из «фонового шума» потенциальных множителей. Чтобы понять, как можно определить верные множители, комбинируя их волны в квантовом вычислении, давайте снова вспомним метафору симфонии: если Бетховен аранжирует мелодию для скрипки, виолончели, флейты и тромбона, то мы услышим эту мелодию независимо от того, что и как играют остальные инструменты оркестра.
Предположим, что, пока квантовый компьютер исследует все возможные множители, мы грубо вмешиваемся в его работу и измеряем его кубиты, чтобы узнать, что делает компьютер. Он ответит: «О, я только что посмотрел на [какую-то пару чисел из 200 цифр каждое], чтобы выяснить, даст ли их перемножение правильный ответ». Почти всегда эти числа не будут решением задачи. Опрашивать квантовый компьютер, когда он исследует все возможные решения проблемы разложения на множители, в общем-то, все равно что выбрать одно из возможных решений случайным образом. Чтобы извлечь из такого вычисления максимальную пользу, вы не должны вмешиваться в работу компьютера, пока он вычисляет. Нужно позволить каждому из параллельных вычислений идти своим чередом, интерферируя с остальными; только при этом условии симфоническая природа квантового вычисления поможет нам найти верные сомножители.
Оглавление книги
