Сет Ллойд - Программируя Вселенную. Квантовый компьютер и будущее науки
Поиск
Разложение на множители – не единственная сложная проблема, которую в принципе могут эффективно решить квантовые компьютеры. В 1996 г. Лов Гроувер из Bell Laboratories показал, что квантовые компьютеры совершают операции поиска эффективнее, чем классические. Предположим, вы забыли, в какой из своих четырех карманов положили свой бумажник. Сначала вы проверяете один карман, потом другой. В худшем случае вам придется проверить все четыре кармана, а в среднем – два. Но предположим, что вы можете использовать квантовый параллелизм, то есть проверить все карманы сразу. Гроувер показал: чтобы найти бумажник, нужно произвести операцию квантового поиска всего два раза.
Конечно, алгоритм Гроувера работает и при количестве вариантов больше четырех. Если вы ищете нечто, что может находиться в 100 возможных местах, то чтобы найти его, достаточно выполнить квантовый поиск всего 10 раз. При классическом поиске вам придется выполнить в среднем 50 операций. Если вы ищете что-то в миллионе возможных мест, нужно будет выполнить квантовый поиск всего 1000 раз вместо полумиллиона классических поисковых операций. В общем, количество операций квантового поиска, необходимых для того, чтобы найти искомое, составляет квадратный корень из количества мест, в которых оно может находиться.
Какие еще задачи квантовые компьютеры могут решать более эффективно, чем классические? Чтобы по максимуму использовать симфоническую природу квантового параллелизма, нужно позволить всем элементам квантового вычисления интерферировать друг с другом. Но как непросто написать симфонию, столь же трудно и создать необходимую квантовую интерференцию, тем более что есть всего несколько квантовых алгоритмов, таких как разложение на сомножители и поиск, которые в настоящее время квантовые компьютеры могут выполнять лучше, чем их классические аналоги.
Создание квантового компьютера
Осенью 1994 г. мне позвонил Джефф Кимбл, профессор физики Калифорнийского технологического института. Джефф прочел пару моих статей о квантовых вычислениях и хотел обсудить возможность создания квантовых логических элементов на основе фотонов.
Джефф Кимбл – долговязый техасец, который хорошо умеет обращаться с атомами и светом. Его представили мне как человека, который «так сильно сжал свет, как до него еще никому не удавалось», и если этот свет чувствовал себя так же, как моя рука после рукопожатия Джеффа, я склонен этому верить. Мы начали беседу, и я заметил две вещи. Во-первых, Джефф без всяких колебаний говорит то, что думает. Если он смотрит на ваше уравнение и произносит, со своим мягким техасским акцентом, что «есть проблема в Ривер-сити»[29], это значит, что вы в беде. Во-вторых, когда он описывает свои эксперименты, я понимаю примерно одно слово из трех.
Той осенью, неделю за неделей, я много общался с Джеффом и его студентами, и постепенно стал понимать, чем они занимаются. Джефф брал отдельные фотоны и заставлял их взаимодействовать с отдельными атомами. По сути, он помещал фотон в емкость с атомом и встряхивал их. Емкость представляла собой оптическую полость, состоящую из двух зеркал на расстоянии нескольких миллиметров друг от друга. Фотон десятки тысяч раз метался туда-сюда между зеркалами, пока, наконец, не вырывался на свободу. Джефф вводил в полость атомы цезия, в то же время освещая ее фотонами лазерного пучка, а потом смотрел, что получилось. Каждый фотон и каждый атом проводили в небольшом пространстве оптической полости существенную долю секунды, и у них было достаточно времени для взаимодействий друг с другом.
Атом очень маленький, его диаметр – одна десятимиллиардная метра, а фотон (как ни странно) может быть гораздо больше. Как мы помним, фотоны – это частицы света, возникающие из колебаний электромагнитного поля. Из-за принципа неопределенности Гейзенберга существует компромисс между скоростью, с которой колеблется электромагнитное поле, и объемом, который занимает фотон: чем лучше определена частота колебаний поля, тем больший объем пространства занимает фотон. Фотоны, которые Джефф Кимбл запускает в свои оптические полости, имеют очень хорошо определенную частоту, а поэтому они тощие и длинные – в сотню метров длиной! Но длина самой полости – всего несколько миллиметров. Как же нечто длиной в 100 метров может поместиться в таком маленьком пространстве? Мне потребовалось некоторое время, чтобы это уяснить. Оказывается, фотон входит в полость так же, как змея вползает в банку из-под кофе: он складывается вдоль тысячи раз. В результате такого сворачивания, сила электромагнитного поля, соответствующего отдельному фотону, внутри полости в тысячи раз выше, чем снаружи. Поэтому фотон в полости очень сильно взаимодействует с атомом, находящимся в ней в этот момент.
Джефф и его студенты Квентин Тюршетт, Кристина Худ и Хидео Мабути в это время проводили эксперименты, в которых запускали два фотона в оптическую полость, где в тот момент находился атом, и смотрели, что происходило с фотонами, когда они выходили из полости. Оба фотона сильно взаимодействовали с атомом, а поэтому сильно взаимодействовали и друг с другом. Но было ли это взаимодействие достаточным, чтобы создать квантовые логические элементы, например схему «условное не»? Когда мы начали эксперименты, Джефф не знал, как действуют квантовые логические элементы, а я не знал, как ведут себя фотоны. После окончания экспериментов я показал, что почти любого взаимодействия между фотонами достаточно для создания квантового логического элемента, а Джефф и его студенты смогли предъявить первые фотонные квантовые логические элементы.
В то же самое время Дейв Уайнленд и Крис Монро из Национального института стандартов и технологии (NIST) в Боулдере экспериментально реализовали предложения Игнасио Сирака и Петера Цоллера из Университета Инсбрука по поводу архитектуры квантовых компьютеров, основанной на том, чтобы улавливать ионы с помощью колеблющегося электромагнитного поля, а затем обстреливать их лазерами. Ионы – это атомы, лишенные электрона, у них суммарный заряд является положительным, благодаря чему их несложно «поймать». (Старый физический анекдот: два атома заходят в бар. Один атом осматривает себя и говорит: «Эй, я потерял электрон!» – «Ты уверен?» – спрашивает второй атом. «Положительно!» – отвечает первый атом.) Когда ионы «пойманы», их можно охладить до очень низкой температуры и обстреливать лазером, чтобы заставить взаимодействовать и выполнять квантовые логические операции.
Эксперименты Кимбла и Уайнленда были проведены на уже существующих, хотя и модернизированных экспериментальных установках. Относительная легкость, с которой были выполнены первые квантовые логические операции, позволила предположить, что квантовый компьютер действительно можно создать.
Когда я начал работать в Массачусетском технологическом институте в декабре 1994-го, я стал сотрудничать с учеными и инженерами со всех концов мира в попытке создать квантовый компьютер. Дэвид Кори, профессор ядерной техники Массачусетского технологического института, вместе со своими коллегами Тимом Хэвелом и Амиром Фами показал, как можно заставить ядерные спины вычислять с помощью обстрела атомов, описанного выше. В применении к ядерным спинам, эти методы называют «ядерным магнитным резонансом» (ЯМР).
Вскоре после этого и независимо от них Нейл Гершенфельд из Media Lab Массачусетского технологического института выяснил, как можно использовать ЯМР для вычисления, и я начал работать вместе с Нейлом и с Айзеком Чуаном над простыми квантовыми вычислениями с помощью ЯМР. Построив всего лишь двухбитовый квантовый компьютер, мы смогли продемонстрировать квантовый параллелизм, заставив его выполнять несколько задач одновременно. Позже Чуан стал разрабатывать квантовые компьютеры ЯМР-типа все больших и больших размеров, и несколько лет назад он создал компьютер на семи кубитах, способный реализовать простую версию алгоритма Шора. Чуан использовал этот компьютер, чтобы разложить на множители число 15. Конечно, предстоит еще очень много сделать, прежде чем появится квантовый компьютер, способный разложить на множители число из 400 цифр[30]!
Простой квантовый компьютер можно собрать из цепочки ядерных спинов в молекуле. На рисунке ядерные спины имеют направления «вверх», «вверх», «вниз», «вниз», «вверх», иначе говоря, в них записаны квантовые биты 00110
Я продолжал сотрудничать с Джеффом Кимблом в области хранения и передачи квантовых битов на фотонах. Кроме того, я начал работать вместе с учеными из Массачусетского технологического института, чтобы заставить свет взаимодействовать с атомами. Джеффри Шапиро, Франко Вонг и Селим Шахрияр из Исследовательской лаборатории электроники изучали возможности квантовой связи, и вскоре мы написали предложение по созданию самого мощного в мире источника запутанных фотонов, а также описали метод, позволяющий «ловить» эти фотоны с помощью атомов, запертых в оптических полостях. Эта технология, как и сходные методы, предложенные Кимблом, Сираком и Цоллером, сформировали основу для попытки создать квантовый интернет – сеть квантовых компьютеров, оптически связанных друг с другом. (Сейчас я работаю над разработкой системы поиска в квантовом интернете с рабочим названием «Quoogle».)
