Факторизация чисел — это одна из тех задач, с которой традиционные компьютеры справляются с огромным трудом. Чем больше число, тем больше времени требуется для того, чтобы определить его множители. И не просто больше: количество шагов, необходимое для факторизации числа известными алгоритмами, экспоненциально растёт с каждым дополнительным разрядом и быстро переходит границы возможного.
На этом свойстве держится криптография с открытым ключом, которую используют для защиты финансовых данных в интернете или в электронной валюте Bitcoin. Чтобы вскрыть, например, шифр RSA, необходимо знать множители, из которых состоит открытый ключ. Поскольку ключом служит достаточно большое число, для того чтобы факторизовать его с помощью обычного компьютера, потребуются годы.
Когда та же задача решается на квантовом компьютере с помощью алгоритма Шора, время вычислений растёт не экспоненциально, а гораздо медленнее. Большие числа по-прежнему факторизуются дольше коротких, но не настолько долго, чтобы и пытаться не стоило.
Квантовый компьютер позволяет факторизовать число, состоящее из N разрядов, за N2 операций. Это означает, что появление достаточно мощных квантовых компьютеров сделает непригодными для использования многие популярные криптоалгоритмы.
Другой интересный пример — алгоритм Гровера, позволяющий найти нужный элемент в неотсортированном списке из N элементов, выполнив лишь N1/2 сравнений. На обычном компьютере для решения той же задачи потребовалось бы N сравнений.
Для наглядности предположим, что в списке миллион элементов. Обычному компьютеру, чтобы отыскать один из них, необходимо выполнить миллион сравнений. Квантовый компьютер, использующий алгоритм Гровера, обойдётся тысячью. Это не экспоненциальное ускорение, как в случае алгоритма Шора, но прибавка всё равно ощутима.
Квантовым алгоритмам требуется заметно меньше шагов для поиска ответа, чем их аналогам, работающим на традиционном компьютере. Кое-кто предполагает, что с помощью квантовых компьютеров удастся эффективно решать даже NP-полные задачи, но такое мнение нельзя назвать популярным. Впрочем, даже без NP-полных задач преимущества квантовых компьютеров очевидны. За чем же дело стало?
Слово «компьютер» обманчиво. Капризные и дорогостоящие квантовые установки, которые строят в лабораториях, не имеют с компьютерами ничего общего. Это не программируемые вычислительные машины. Слово «машина» едва ли подходит для их обозначения — по крайней мере, на этой стадии развития.
Поскольку квантовые эффекты проявляются лишь на микроуровне, экспериментаторам обычно приходится работать с отдельными атомами или элементарными частицами, что, мягко говоря, не так уж просто. Кубитами могут служить, например, ионы, подвешенные в электромагнитном поле.
Ионы не станут факторизовать числа лишь потому, что их назвали кубитами. Им попросту нечем это делать. Для выполнения квантовых операций требуется внешнее воздействие. Влиять на кубиты можно, например, с помощью лазера или микроволн. Легко понять, что с небольшим числом кубит таким методом ещё можно справиться, а вот дальше начнутся проблемы.
Дело осложняется тем, что любое взаимодействие между кубитами и окружающей средой может привести к декогеренции, которая делает продолжение работы невозможным. Чтобы избежать помех, квантовые компьютеры часто помещают в вакуум и охлаждают почти до абсолютного нуля, но это не особенно помогает.
В 2007 году канадский стартап D-Wave объявил о намерении выпустить первый коммерческий квантовый компьютер. Намерение подкрепили демонстрацией машины, которая, по уверениям разработчиков, насчитывала шестнадцать кубит.
На глазах у зрителей она решила головоломку судоку, вычислила идеальную комбинацию гостей на гипотетической свадьбе и обработала SQL-запрос в специальной версии MySQL. С этими задачами прекрасно справился бы и обычный компьютер, но презентация и не должна была потрясать воображение.