Программируя Вселенную. Квантовый компьютер и будущее науки - Сет Ллойд

Квантовый параллелизм делает квантовые компьютеры потенциально очень мощными. Квантовый компьютер может одновременно исследовать все возможные решения той или иной проблемы, даже самой сложной. Пример такой проблемы – разложение на множители. Число раскладывается на множители, если его можно представить как произведение двух или более целых чисел, бóльших единицы. Например, число 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 цифр с помощью известных нам сегодня методов, вероятно, еще в течение многих лет останется невозможным.