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

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

Проблема заключается в том, что при считывании информации неопределённость исчезает. Вместо бесчисленного множества решений, которые только что содержал квантовый компьютер, остаётся только одно, причём не самое верное, а первое попавшееся. Чтобы от квантового компьютера была какая-то польза, ненужные варианты нужно заранее отсеять.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В 2007 году канадский стартап D-Wave объявил о намерении выпустить первый коммерческий квантовый компьютер. Намерение подкрепили демонстрацией машины, которая, по уверениям разработчиков, насчитывала шестнадцать кубит.

На глазах у зрителей она решила головоломку судоку, вычислила идеальную комбинацию гостей на гипотетической свадьбе и обработала SQL-запрос в специальной версии MySQL. С этими задачами прекрасно справился бы и обычный компьютер, но презентация и не должна была потрясать воображение.

Воображение потрясало другое: наполеоновские планы D-Wave. К концу года компания намеревалась довести число кубит до 32, а к середине 2008 года впустить квантовый компьютер с 1024 кубитами.

Обещания D-Wave отличались от суровой реальности, хорошо знакомой всем, кто занимался исследованиями в области квантовых вычислений, как небо и земля. Скачок таких масштабов был бы чудом, а чудес, как известно, не бывает.