Программируя Вселенную. Квантовый компьютер и будущее науки - Сет Ллойд

Конечно, алгоритм Гроувера работает и при количестве вариантов больше четырех. Если вы ищете нечто, что может находиться в 100 возможных местах, то чтобы найти его, достаточно выполнить квантовый поиск всего 10 раз. При классическом поиске вам придется выполнить в среднем 50 операций. Если вы ищете что-то в миллионе возможных мест, нужно будет выполнить квантовый поиск всего 1000 раз вместо полумиллиона классических поисковых операций. В общем, количество операций квантового поиска, необходимых для того, чтобы найти искомое, составляет квадратный корень из количества мест, в которых оно может находиться.

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

Создание квантового компьютера

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

Джефф Кимбл – долговязый техасец, который хорошо умеет обращаться с атомами и светом. Его представили мне как человека, который «так сильно сжал свет, как до него еще никому не удавалось», и если этот свет чувствовал себя так же, как моя рука после рукопожатия Джеффа, я склонен этому верить. Мы начали беседу, и я заметил две вещи. Во-первых, Джефф без всяких колебаний говорит то, что думает. Если он смотрит на ваше уравнение и произносит, со своим мягким техасским акцентом, что «есть проблема в Ривер-сити»[29], это значит, что вы в беде. Во-вторых, когда он описывает свои эксперименты, я понимаю примерно одно слово из трех.

Той осенью, неделю за неделей, я много общался с Джеффом и его студентами, и постепенно стал понимать, чем они занимаются. Джефф брал отдельные фотоны и заставлял их взаимодействовать с отдельными атомами. По сути, он помещал фотон в емкость с атомом и встряхивал их. Емкость представляла собой оптическую полость, состоящую из двух зеркал на расстоянии нескольких миллиметров друг от друга. Фотон десятки тысяч раз метался туда-сюда между зеркалами, пока, наконец, не вырывался на свободу. Джефф вводил в полость атомы цезия, в то же время освещая ее фотонами лазерного пучка, а потом смотрел, что получилось. Каждый фотон и каждый атом проводили в небольшом пространстве оптической полости существенную долю секунды, и у них было достаточно времени для взаимодействий друг с другом.