Коллектив Авторов - Цифровой журнал «Компьютерра» № 169

Это делают с помощью квантовых алгоритмов, которые состоят из специальных операций, влияющих на кубиты. Ассоциация с компьютерными программами, которую, возможно, вызовет слово «алгоритм», не особенно точна. Квантовые алгоритмы совсем не похожи на программы. У них куда больше общего с логическими схемами, состоящими из вентилей И, ИЛИ и НЕ, только вместо булевой алгебры они используют квантовую логику.

В 1994 году математик Питер Шор придумал первый квантовый алгоритм, у которого потенциально может быть практическое применение. Алгоритм Шора предназначен для факторизации чисел, то есть разложения их на простые множители. Именно его работоспособность проверял квантовый компьютер, раскладывавший на множители число 15.

Великие изобретения редко случаются без внешнего стимула. Успехам в освоении космоса мы обязаны гонке вооружений и напряжённым отношениям между СССР и США. Компьютеры появились на исходе Второй мировой войны для баллистических расчётов и взлома немецких шифров. Но ничуть не реже стимулом становилась не война, а крупная награда, привлекающая к решению важной задачи лучшие умы человечества.

Факторизация чисел — это одна из тех задач, с которой традиционные компьютеры справляются с огромным трудом. Чем больше число, тем больше времени требуется для того, чтобы определить его множители. И не просто больше: количество шагов, необходимое для факторизации числа известными алгоритмами, экспоненциально растёт с каждым дополнительным разрядом и быстро переходит границы возможного.

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

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

Квантовый компьютер позволяет факторизовать число, состоящее из N разрядов, за N 2операций. Это означает, что появление достаточно мощных квантовых компьютеров сделает непригодными для использования многие популярные криптоалгоритмы.

Другой интересный пример — алгоритм Гровера, позволяющий найти нужный элемент в неотсортированном списке из N элементов, выполнив лишь N 1/2сравнений. На обычном компьютере для решения той же задачи потребовалось бы N сравнений.

Для наглядности предположим, что в списке миллион элементов. Обычному компьютеру, чтобы отыскать один из них, необходимо выполнить миллион сравнений. Квантовый компьютер, использующий алгоритм Гровера, обойдётся тысячью. Это не экспоненциальное ускорение, как в случае алгоритма Шора, но прибавка всё равно ощутима.

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

Слово «компьютер» обманчиво. Капризные и дорогостоящие квантовые установки, которые строят в лабораториях, не имеют с компьютерами ничего общего. Это не программируемые вычислительные машины. Слово «машина» едва ли подходит для их обозначения — по крайней мере, на этой стадии развития.

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

Ионы не станут факторизовать числа лишь потому, что их назвали кубитами. Им попросту нечем это делать. Для выполнения квантовых операций требуется внешнее воздействие. Влиять на кубиты можно, например, с помощью лазера или микроволн. Легко понять, что с небольшим числом кубит таким методом ещё можно справиться, а вот дальше начнутся проблемы.