Золотой билет

Записанные на телевизор бейсбольные игры – это, конечно, не кубиты, однако с кубитами у них имеется много общего. Пока игра идет, она находится в неопределенном, промежуточном состоянии, и это продолжается вплоть до финального свистка. Затем Том наблюдает окончание игры, и тут уже всякая неопределенность исчезает, поскольку становится ясно, кто выиграл, а кто проиграл. С кубитом дело обстоит аналогичным образом: как только за ним начинают наблюдать, он покидает свое промежуточное состояние и принимает одно из двух пограничных значений, превращаясь в самый обыкновенный бит.

Квантовые биты могут быть определенным образом связаны, или запутаны, – например, так, что при каждом измерении они будут приходить в одно и то же состояние. Нечто подобное происходит и при просмотре записанных на телевизор бейсбольных игр.

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

Состояние бейсбольного матча «ходит» вдоль одной оси: это просто вероятность того или иного исхода.

Рис. 9.1. Бостонская команда

Звездочкой обозначена тридцатипроцентная вероятность победы Бостона. Пока Том смотрит матч, звездочка перемещается; в зависимости от исхода игры она попадет либо в самую левую точку, либо в самую правую.

Состояния кубита образуют окружность с центром в точке пересечения осей «Истина» и «Ложь».

Рис. 9.2. Кубиты

В данном случае звездочка перемещается по двумерной траектории. На рис. 9.2 ее текущие координаты – 0,55 по «Истине» и 0,84 по «Лжи». Координаты вполне могут быть и отрицательными: к примеру, смайлик находится в точке (-0,71; -0,71). Квантовые компьютеры вращают и переворачивают эти окружности и таким образом управляют состояниями кубитов.

Одному кубиту соответствует окружность на плоскости. Двум кубитам требуется четырехмерная окружность; нарисовать ее здесь или даже просто представить в уме было бы довольно затруднительно. В системе из тридцати кубитов размерность пространства будет более триллиона.

Все это наводит на мысль использовать квантовые компьютеры для решения NP-задач. Допустим, нам нужно найти клику размера 50 среди 20000 жителей Королевства. Имея около 500 кубитов, мы сможем воспроизвести сразу все группы размера 50, которые будут обрабатываться параллельно; чтобы отметить клику, квантовый компьютер выполнит определенную последовательность вращений и переворотов.

В результате система придет в квантовое состояние, представляющее собой совокупность приблизительно из 3 × 10¹⁵⁰ (т. е. 3 и 150 нулей) групп, часть которых отмечены как клики. Если мы научимся эффективно «вытаскивать» из квантовых состояний информацию о кликах, то получим быстрый квантовый алгоритм для поиска клики, а также для всех остальных NP-полных задач. Считывая квантовое состояние системы (т. е., в некотором роде, наблюдая за окончанием игры), мы видим лишь один исход, в данном случае – одну группу жителей; маловероятно, что именно эта группа окажется кликой.

Нам нужно научиться как-то выделять искомые клики, чтобы при считывании квантового состояния они попадались нам с большей вероятностью. Сделать это можно при помощи квантовых манипуляций с кубитами. Правда, при грубом подходе манипуляций потребуется столько же, сколько и групп, т. е. примерно 3 × 10¹⁵⁰, и все преимущества квантовых вычислений будут сведены на нет. В 1996 году сотрудник Лабораторий Белла в Нью-Джерси Лов Гровер разработал «умный» квантовый алгоритм, который мог обнаружить клику в Королевстве «всего» за 2 × 10⁷⁵ квантовых шагов. Однако даже при скорости триллион операций в секунду на это ушло бы в пять раз больше времени, чем живет наша вселенная.

Уже доказано, что при решении NP-полных задач на квантовом компьютере алгоритм Гровера в общем случае дает наилучший результат, поэтому квантовые алгоритмы вряд ли позволят приравнять классы P и NP. Если физики когда-нибудь и построят полноценные квантовые компьютеры, самые трудные проблемы все равно окажутся им не по зубам.

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