(Март 2000)
К итогам конференции по квантовым вычислениям в Беркли
В середине февраля нынешнего (2000) года в Исследовательском институте математических наук в Беркли (Калифорния, США) прошла конференция по проблемам квантового компьютинга. На конференцию собирались академические ученые и исследователи из промышленности, чтобы обсудить реальные достижения и проблемы в той области, которую еще десяток лет назад считали если и возможным, то весьма отдаленным будущим.
Сегодня, однако, вопросами квантовых вычислений непосредственно занимаются многие университеты и несколько ведущих исследовательских центров компьютерной индустрии, таких как AT&T Labs, IBM и Microsoft Research. Всерьез задумываются над созданием собственных исследовательских групп по квантовым вычислениям в НАСА, в Hewlett-Packard, во многих других научных и промышленных центрах.
В течение последних нескольких лет в лабораториях мира созданы несколько простейших моделей квантовых компьютеров. По сравнению с весьма скромными пока практическими успехами, теория квантовых вычислений ушла значительно дальше, исследуя, какого рода задачи смогут решать более сложные машины, когда (и если) они будут построены.
Очень многие из работающих в этой области ученых, можно сказать, пишут алгоритмы и программы для устройств, которых пока еще не существует в действительности. Но при этом даже на бумаге полученные исследователями результаты выглядят очень впечатляюще: алгоритм, способный факторизовать числа в миллиарды раз быстрее, чем нынешние неквантовые методы; поисковая машина, способная обследовать все закоулки Интернета за полчаса; машина тотального перебора криптоключей, способная вскрывать DES-алгоритм за пять минут…
Самая же удивительная вещь в квантовых вычислениях – это, возможно, то, что идея их развивалась на редкость неторопливо. Ведь еще в 1920-е годы физики обнаружили, что мир субатомных частиц представляет собой совсем иное царство.
Однако, понадобилось еще примерно полвека, чтобы компьютерные ученые начали задумываться: а нельзя ли применять необычные квантовые эффекты для вычислений? Можно ли субатомные частицы использовать для хранения битов информации? Можно ли из них делать логические элементы (вентили)?
Если рассматривать, к примеру, электрон, то его можно уподобить крошечному магниту, вращающемуся вокруг собственной оси. Магнитный момент электрона может указывать в одном из двух направлений – «вверх» или «вниз». Таким образом, спин электрона оказывается квантованным: у него имеется лишь два возможных состояния, которые легко обозначить как «0» и «1», т.е. биты, используемые в обычном компьютерном процессоре. И эти биты тоже можно переключать, то есть изменять состояние «вниз» (0) на состояние «вверх» (1), просто прикладывая к квантовой системе немного энергии.
Но предположим, что энергии приложили несколько меньше, чем требуется для «переключения». При наблюдении состояния спина электрона опять будет установлено, что оно квантовано, и спин указывает либо вниз, либо вверх. Однако, тут появляется небольшое, но весьма существенное отличие.
Согласно правилам квантовой механики, вероятность наблюдения спина в том или ином положении изменится. Это изменение возникает благодаря качественно новому состоянию, не имеющему аналогов в обычных неквантовых законах физики, и именуемому суперпозицией двух состояний спина. Это некое комбинированное состояние, когда спин, скажем, на 60 процентов «вверх» и на 40 процентов «вниз».
То есть частица находится одновременно в обоих состояниях, обладающих определенными вероятностями до тех пор, пока не произведено измерение. Сам акт измерения, или «наблюдения», заставляет частицу однозначно выбрать одно из двух возможных состояний.
В 1970-80-е годы физики и компьютерные ученые начали исследовать, каким образом свойства квантовых суперпозиций можно было бы применять в компьютерных вычислениях. Первые работы в этой области были сделаны Чарльзом Бенетом (Charles H. Bennett) из Уотсоновского исследовательского центра IBM, Полом Беньофом (Paul A. Benioff) из Аргоннской национальной лаборатории и Дэвидои Дойчем (David Deutsch) из Оксфорда.
Уже в этих работах было показано, что частицы в состоянии суперпозиции вполне могут функционировать в качестве «квантовых битов» или «кубитов» (qubits), к которым можно применять стандартные логические операции И, ИЛИ и НЕ, используемые в классических компьютерах. Но в то же время квантовые биты теоретически допускали и совсем иные манипуляции, для классических систем представляющиеся «волшебными» и практически недостижимыми.
Поскольку электрон (атом, ион и т.д.) может пребывать в двух состояниях сразу, то набор таких кубитов – это уже не обычный компьютерный регистр, это нечто совершенно новое. Здесь вычисления осуществляются уже не последовательно, а, в некотором смысле, выполняются все сразу одновременно.
Имея систему, скажем, из 500 частиц, в принципе можно было бы создать квантовую систему, являющуюся суперпозицией 2500 возможных состояний. Квантовая операция применительно к данной системе, например импульс радиоволн, выполняющий, скажем, наложение отрицания на 175-й и 176-й кубиты, будет воздействовать одновременно на все 2500 состояний.
Таким образом, всего за один такт работы квантовая операция могла бы выполняться не с одним состоянием машины (как это делается в обычных компьютерах), а сразу со всеми состояниями одновременно. Конечно, в соответствии с физическими законами, акт измерения (наблюдение) системы приводит к ее коллапсу в единственное состояние, соответствующее единственному ответу. И, если алгоритм был составлен правильно, это будет единственно правильный ответ…
Естественным следствием данной концепции является то, что квантовые компьютеры работали бы настолько быстрее компьютеров классических, что вполне смогли бы решать те задачи, к которым обычные компьютеры и подступиться пока не могут.
Короче говоря, стало ясно, что если удастся построить функционирующий квантовый компьютер, то для реализации его потенциала просто необходимы алгоритмы, которые описывали бы выполнение надлежащих операций в правильном порядке. По этой причине вполне понятно, что открытие нескольких весьма эффектных алгоритмов такого рода в середине 90-х годов придало сильнейший импульс нынешнему обостренному интересу исследователей к квантовым вычислениям.
В 1994 году Питер Шор (Peter W. Shor), математик из AT&T Labs, открыл квантовый алгоритм факторизации, позволяющий раскладывать большие числа на простые множители почти с такой же эффективностью, какая свойственна перемножению чисел. Напомним, что для классического компьютера сложность задач перемножения и факторизации различается самым радикальным образом, на чем и построена стойкость известной криптосхемы RSA.
Алгоритм Шора опирается на хорошо известный в теории чисел факт, позволяющий преобразовывать проблему факторизации в оценку периодичности длинной последовательности. Но в классических алгоритмах для оценки периодичности необходимо иметь по крайней мере столько элементов последовательности, сколько их в длине периода. В алгоритме Шора все сделано намного интереснее.
Его метод работает по тому же принципу, который позволяет минералогам с помощью рентгеновской дифракции отыскивать периодичность в кристаллической решетке неизвестной твердой субстанции. Периодическая структура решетки позволяет распространяться в любом заданном направлении лишь излучению с определенными длинами волн.
Аналогичным образом и в алгоритме Шора квантовая система кубитов в состоянии суперпозиции позволяет «распространяться» лишь вполне определенным волноподобным вероятностям, связанным с квантовыми состояниями. Все же остальные вероятности затухают и исчезают. Затем алгоритм вычисляет эти «длины волн», оценивает периодичность и в конечном счете отыскивает множители числа. На сегодняшний день алгоритм Шора – это самый быстрый из известных алгоритмов факторизации.
Еще один интереснейший алгоритм более общего назначения был открыт в 1996 году Ловом Гровером (Lov Grover), исследователем из центра Bell Labs компании AT&T. Алгоритм Гровера использует принципы квантового компьютера для очень быстрого поиска в неупорядоченных базах данных.
Здесь, естественно, также используется волновая природа вероятностей для состояний суперпозиции, и сам Гровер описывает суть алгоритма как «бросание камешков в пруд таким способом, чтобы волны от них накладывались и взаимодействовали вполне определенным образом».
Алгоритм Гровера так устанавливает несколько траекторий вычислений, чтобы волны результатов (происходящих в квантовой системе одновременно) начали интерферировать друг с другом. Тогда нежелательные ответы сами себя гасят, а верные ответы, накладываясь, усиливают друг друга. В некотором смысле, квантовый компьютер – это «обратное вычисление»: предполагается, что компьютеру уже известны все возможные ответы, и алгоритму остается лишь отыскать верный…
Теперь самое время вернуться к собственно конференции в Беркли. Основные темы выступлений были сконцентрированы вокруг следующих проблем: алгоритмы для быстрого решения задач, не поддающихся решению с помощью классических компьютеров; осмысление пределов вычислительной мощности квантовых компьютеров; различные подходы к построению реальных устройств для квантовых вычислений; методы коррекции вычислительных ошибок.
Поскольку содержание докладов чаще всего носило характер сугубо научный и малопонятный для неспециалистов, то вполне объяснимо, что кульминацией всего мероприятия стала серия презентаций, подготовленных специально для Отдела информационных технологий Финансового управления Министерства обороны США. Здесь суть изысканий излагалась уже на вполне доступном уровне и в привлекательной для неспециалистов форме, поскольку упомянутый отдел МО в настоящее время рассматривает программу финансирования исследований в области квантовых вычислений.
Как рассказал на своей презентации д-р Шор, несмотря на свою потенциальную мощь, квантовые компьютеры вовсе не обязательно будут выполнять все задачи быстрее классических компьютеров. В действительности, по его оценкам, работоспособный квантовый компьютер каждую из операций будет выполнять даже медленнее, чем компьютер обычный. И лишь для некоторых проблем, там, где исследователи обнаружили методы эффективного использования возможностей столь гигантских объемов хранимой информации, научившись выделять нужный ответ за сравнительно небольшое количество шагов (намного меньшее, чем в классических компьютерах) – появляется возможность существенно ускорить вычисления.
Здесь можно добавить, что уже упомянутые алгоритмы Шора и Гровера и на сегодняшний день являются наиболее яркими примерами такого рода. В настоящее время множество ученых занято поисками квантовых алгоритмов для решения других интересных проблем, недоступных для возможностей обычных компьютеров. И одновременно многие, напротив, напряженно работают над созданием работоспособных квантовых криптосхем, которые смогли бы заменить классические алгоритмы шифрования, когда их полностью скомпрометирует будущий квантовый компьютер.
Д-р Умеш Вазирани (Umesh Vazirani), профессор компьютерной науки из Университета Беркли, был одним из организаторов нынешней конференции. Свою собственную презентацию он посвятил ограничениям, существующим для квантовых вычислений.
Например, строго доказано, что время работы алгоритма Гровера для поиска информации в неупорядоченной базе данных равно корню квадратному от того времени, что необходимо для аналогичного поиска компьютеру классическому. Но более того, квадратный корень – это вообще наилучший результат, который может быть достигнут.
По мнению Вазирани, подобные результаты дают основание полагать, что сложнейшие вычислительные проблемы могут так и остаться за пределами досягаемости квантовых компьютеров. С другой стороны, эти пределы дают луч надежды криптографам, поскольку теоретически обосновывают возможность существования таких криптосистем, которые не смогут вскрывать и квантовые компьютеры.
Д-р Айзек Чуанг (Isaac Chuang) из Олмейденского исследовательского центра IBM (г.Сан-Хосе) описал несколько конкурирующих технологий построения работоспособного квантового компьютера. Одна из действующих моделей построена на основе молекул жидкого хлороформа. На «регистре» из четырех кубитов исследователям удалось реализовать поисковый алгоритм Гровера. В Оксфордском университете аналогичное устройство было построено на основе ядер водорода в органическом веществе цитозин. Модель из 3 кубитов, реализующая алгоритм Шора, была продемонстрирована в 1998 году исследователями Лос-Аламосской национальной лаборатории.
Но все эти игрушечные модели, однако, упираются в гигантские проблемы масштабирования, необходимого для перевода устройств в разряд вычислителя, применимого на практике. Как говорит Чуанг, «основная трудность при создании квантового компьютера заключается в том, что вам нужно изолировать его от любых воздействий внешнего мира, и в то же самое время иметь возможность манипулировать им на высокой скорости».
Еще одна огромная трудность, по словам экспертов, – это исправление ошибок, неизбежно возникающих в процессе вычислений. В столь тонком устройстве хранимые состояния могут непреднамеренно «пихать» друг друга, в результате чего операции могут применяться не к тем квантовым битам.
Доклад д-ра Дэниэла Готсмэна (Daniel Gottesman) из Microsoft Research был посвящен обзору методов исправления ошибок, появляющихся в процессе квантовых вычислений. Начиная с блестящего прорыва 1995 года, когда Питером Шором и Эндрю Стини (Andrew M. Steane) из Оксфорда независимо друг от друга были созданы эффективные методы квантовой коррекции, исследователями к настоящему времени разработаны способы, позволяющие восстанавливать те квантовые состояния, что хранились в памяти, но частично подверглись коллапсу из-за непреднамеренных наблюдений.
Кроме того, исследования Готсмэна и его коллег показали, что можно корректировать не только состояния, но и собственно ошибки вычислений, если число их не очень велико. В настоящее время исследователи Microsoft Research заняты разработкой более эффективной техники исправлений, позволяющей охватывать большее количество ошибок.
В целом же итоги конференции выглядят следующим образом. Участники форума не могли не отметить явный прогресс в развитии технологии квантовых вычислений, ушедшей за последнее время намного дальше того состояния, в котором она находилась всего несколько лет назад. Но в то же время ученым приходится признать, что пока еще крайне далеко до полного понимания как потенциала, так и пределов технологии. Что же касается построения применимого на практике устройства, до до него путь еще очень и очень неблизок.
Однако, итоги такие, похоже, ничуть не смущают исследователей. Как выразился по этому повод профессор Ричард Йожа (Richard Josza) из Бристольского университета (Англия), «В чем ценность новорожденного младенца? Сейчас он еще ничего не умеет. Но потенциал его безграничен»…
Ну а то, насколько опасной и в то же время забавной вещью являются прогнозы, демонстрирует примечательная дискуссия по поводу компьютера ENIAC, опубликованная в мартовском, 1949 года номере журнала Popular Mechanics («Популярная механика»):
«В то время как вычислитель ENIAC оборудован 18 тысячами вакуумных ламп и весит 30 тонн, компьютеры будущего смогут состоять всего из 1 тысячи ламп и весить всего полторы тонны».
Дополнительное чтение
Существенно более подробный рассказ об истории рождения квантовых компьютеров и об успехах данной области за первое десятилетие 2000-х годов можно найти в следующем цикле материалов:
kiwi arXiv 