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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Скептицизм специалистов столкнулся с полным нежеланием D-Wave рассказывать, каким образом были достигнуты такие успехи. Напрашивается вопрос: а был ли мальчик? Действительно ли устройство, которым хвасталась компания, — это квантовый компьютер? Никаких доказательств этому не было. Развеять сомнения могли бы публикации разработчиков D-Wave в академических журналах, но их не было.

К D-Wave приклеился ярлык «шарлатаны», но компания продолжала работать. Чересчур оптимистичный план пришлось скорректировать. Машина, использующая, если верить D-Wave, 128 кубитов, появилась не в 2008, а лишь в 2011 году. Несколько месяцев назад разрядность довели до 512.

В 2009 году D-Wave и Google провели совместную презентацию. Хартмут Невен, видный специалист в области распознавания лиц, работающий в Google, рассказал об испытании самообучающегося алгоритма для выделения автомобилей на снимках Street View. По утверждению Невена, квантовое устройство D-Wave справилось с задачей лучше, чем традиционные компьютеры в дата-центрах Google.

Такое развитие событий немного озадачило скептиков. Результаты, которые обнародовал Невен, не доказывали, что в D-Wave построили настоящий квантовый компьютер, однако отмести их тоже было нельзя. Если D-Wave — это мошенники, то как же им удалось переманить на свою сторону совсем не глупых людей из Google?

В 2011 году корпорация Lockheed Martin, гигант военно-промышленного комплекса США, объявила о приобретении 128-кубитной машины D-Wave за 10 миллионов долларов. Можно было бы предположить, что покупка совершена из любопытства, однако история на этом не закончилась.

В марте 2013 года в Lockheed Martin решили купить следующую модель квантового компьютера D-Wave. Первая покупка не просто удовлетворила интерес компании — она доказала свою полезность. Получается, в обещаниях D-Wave всё же есть доля правды?

В D-Wave в итоге пошли на попятную и опубликовали пару научных работ о своей машине. Попутно стало ясно, что это, во-первых, не квантовый компьютер в самом распространённом понимании этого слова, а во-вторых, кубиты, о которых идёт речь в рекламе компании, строго говоря, не вполне кубиты.

В основе машины D-Wave лежит охлаждённая до -273 градусов по Цельсию микросхема с решёткой, построенной из сверхпроводящих квантовых интерферометров. Именно их в компании называют кубитами. Значение кубитов D-Wave, как и значение кубитов в настоящем квантовом компьютере, может быть неопределённым, однако они не связаны между собой с помощью квантовой запутанности.

Машина D-Wave не годится для алгоритмов, которые используют квантовые вентили. Ни алгоритм Шора, ни алгоритм Гровера на ней не пойдут. Вместо этого она использует для работы совершенно иной принцип — так называемые адиабатические квантовые вычисления. Это значительно ограничивает её возможности, но позволяет не беспокоиться о декогеренции и других проблемах, сопровождающих обычные квантовые вычислители.

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

Эта оптимизационная задача имеет на удивление много реальных применений. В D-Wave использовали своё устройство для фолдинга белков, в Google учили его распознавать образы, а в Lockheed Martin приспособили машину для верификации критически важного программного обеспечения.