Как будут использоваться квантовые компьютеры?
Я в восторге от алгоритма факторизации Питера Шора (Shor, 1994). С помощью алгоритма Шора можно найти разложение $N$-значного числа на множители за время порядка $N^{3}$, в то время как считается (хотя
это не доказано), что время, нужное для этого любому классическому компьютеру, растет с $N$ быстрее, чем любая его степень. Этот ошеломляющий результат и изобретательность алгоритма вызвали большой интерес к квантовым вычислениям ${ }^{1}$.

Желание получить мощное факторизующее устройство (с криптографическими приложениями) расценивается как одно из первичных побуждений к созданию квантового компьютера. Но, в конечном счете, я не думаю, что факторизация будет среди наиболее важных приложений квантовых вычислений. На самом деле то, что задача факторизации считается сегодня особенно важной, представляется мне исторической случайностью.

Если не факторизация, что тогда? Я совершенно согласен с точкой зрения Фейнмана (Feynman, 1982) о том, что квантовый компьютер будет использоваться для моделирования поведения квантовых систем ${ }^{2}$.

Фейнман подчеркивал, что квантовое устройство может хранить квантовую информацию более эффективно, чем любой классический прибор; поскольку $N$ кубитов соответствуют гильбертову пространству размерности $2^{N}$, классическое устройство будет использовать $2^{N}-1$ комплексных числа, чтобы описать типичное квантовое состояние $N$ кубитов. Поэтому возможно, что квантовое моделирование является примером задачи, которая требует экспоненциальных ресурсов для классического компьютера, но не для квантового компьютера ${ }^{3}$.
(Экспоненциальный рост памяти не является действительно необходимым, но моделирование, возможно, потребует экспоненциально большого времени.) Кроме того, квантовое моделирование — весьма обширная область, со многими потенциальными приложениями, например, к наукам о материалах и к химии. Я думаю, что важно более подробно рассмотреть вопрос об использовании квантовых компьютеров в качестве квантовых моделирующих устройств, чтобы мы мог-
${ }^{1}$ Дэниел Саймон (Saimon, 1994) фактически проложил путь к алгоритму Шора, предложив первый пример квантового алгоритма, который эффективно решает интересную и трудную проблему.
${ }^{2}$ Однако мое мнение, что квантовое моделирование более важно, чем разложение на множители, было воспринято некоторыми участниками конференции как умозаключение ограниченного физика, который считает, что единственно важные проблемы — те, над которыми он работает!
${ }^{3}$ Но именно Дэвид Дойч (Deutsch, 1985), а не Фейнман, подчеркнул, что квантовые компьютеры могут лучше всего реализовать их вычислительный потенциал, эксплуатируя огромный квантовый параллелизм. Утверждение, что квантовая система может производить вычисление, впервые явно высказал Бенёв (Benioff, 1982).
ли лучше оценить те преимущества, которые получим при использовании в будущем квантовых компьютеров по сравнению с классическими (Lloyd, 1996; Zalka, 1996a; Wiesner, 1996; Meyer, 1996; Lidar\& Biham, 1996; Abrams\&Lloyd, 1997; Boghosian\& Taylor, 1997).

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

Например, $n$-частичные корреляции в основном состоянии могут быть вычислены за полиномиальное время на классическом компьютере. Классическое моделирование поведения квантовой системы в реальном времени является более трудной проблемой, но возможно, что при достаточной изобретательности могут быть развиты новые приближения, которые значительно улучшат эффективность такого моделирования. Использование квантового компьютера в значительной мере является стратегией решения «в лоб»; однако иногда выгоднее использовать именно «лобовой» метод решения проблемы, чем искать обходные пути, требующие исключительного ума.

С момента появления алгоритма факторизации Шора, возможно, наиболее важное продвижение в квантовой сложности было осуществлено Гровером, предложившим чрезвычайно остроумный метод для поиска в случайной базе данных (Grover, 1996). В базе данных, содержащей $N$ записей, та из них, которая удовлетворяет некоторому указанному критерию, может быть найдена на квантовом компьютере за время порядка $\sqrt{N}$. На классическом компьютере перебор базы данных потребовал бы время порядка $N$, так что алгоритм Гровера — тот самый случай, когда мы знаем, что квантовый компьютер может обрабатывать важную в вычислительном отношении задачу быстрее, чем любой классический компьютер. (Это не было доказано для алгоритма разложения на множители, хотя кажется правдоподобным также и для него.) Ускорение достигается как за счет квантового параллелизма, так и за счет того, что вероятность в квантовой теории является квадратом амплитуды — алгоритм Гровера действует на начальное состояние, в котором все $N$ классических записей представлены с амплитудой $1 / \sqrt{N}$, и приводит исходное состояние за $\sqrt{N}$ шагов к состоянию, в котором искомая запись представ.ена с амплитудой порядка единицы.
По сравнению с классическими методами ускорение, достигнутое алгоритмом Гровера, конечно, не является настолько впечатляющем, как экспоненциальное ускорение, достигнутое в алгоритме Шора. Но даже неэкспоненциальное ускорение может быть очень полезно. Перебор базы данных — несомненно важная проблема со многими приложениями; например, ее можно использовать, чтобы решить любую NP-проблему (проблемы, в которых очень трудно найти решение, но очень просто его проверить). Если квантовые компьютеры будут использоваться в ближайшие 100 лет, я предположил бы, что они будут работать на основе алгоритма Гровера или похожего на него. Можно добавить еще кое-что относительно алгоритмов, подобных Гроверу, обеспечивающих неэкспоненциальное ускорение. В случае поиска в базе данных, вычисления, которые требуют времени $T$ на классическом компьютере, могут быть сделаны за время порядка $\sqrt{T}$ на квантовом компьютере. Было бы очень интересно найти общий способ выделения классических алгоритмов, которые допускают такой вид $\sqrt{T}$ квантового ускорения. В частности, классические компьютеры обычно решают полные NP-проблемы не вслепую, пока не встретится желательное решение, а делая перебор, который является значительно более продуманным и эффективным, и при этом остается достаточно приемлемым. До какой степени эти наиболее эффективные алгоритмы могут быть улучшены с помощью квантовых вычислений?

Рассуждения относительно перспектив квантовых вычислений часто ограничиваются NP-задачами, и часто основаны на ожидании, что квантовые вычисления будут допускать экспоненциальное ускорение для решения проблем в этом классе. В этой связи важный результат был получен Беннеттом, Бернштейном, Брассардом и Вазирани (Bennet, Bernstein, Brassard, и Vazirani, 1997a), которые показали, что алгоритм Гровера поиска в случайной базе данных оптимален; никакой другой квантовый алгоритм не может решить проблему быстрее, чем за время порядка $\sqrt{N}$. Этот результат наводит на мысль, что квантовые компьютеры не могут обеспечить возможность решения NP-полных проблем за полиномиальное время. По крайней мере это указывает, что не существует никакого полиномиального квантового алгоритма, основанного на чистой «квантовой магии»; скорее всего, потребуется более глубокое изучение структуры проблем в NP-полном классе.

Возможно, что полные NP-проблемы — не лучшая область для использования мощности квантовых вычислений. Может оказаться, что квантовые компьютеры окажутся способны к решению некоторых трудных задач, которые лежат вне NP-проблем, и что квантовое моделирование является таким примером. В нашей команде было даже предсказание, что возможность решения полных NP-проблем с помощью квантового моделирования должна бы требовать экспоненциальных ресурсов на классическом компьютере; то есть классический компьютер не способен эффективно моделировать квантовый компьютер ${ }^{1}$.

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

При условии корректности основного предположения классической теории сложности ( $\mathrm{P}
eq \mathrm{NP}$ ), существует класс проблем (класс NPI) промежуточного уровня трудности; эти проблемы не так трудны, как полные NP-проблемы, однако они все еще не могут быть решены машиной Тьюринга за полиномиально ограниченное время. Проблема факторизации расценена как вероятный кандидат для членства в этом классе (Garey \& Johnson, 1979), так что естественно задаться вопросом, могут ли быть изобретены эффективные квантовые алгоритмы для других проблем, которые, как предполагается, соответствуют NPI-классу. Один особенно перспективный пример — проблема изоморфизма графов (необходимо определить, являются ли два указанных графа эквивалентными после подходящего переобозначения вершин). Важно исследовать, могут ли быть изобретены хорошие квантовые алгоритмы для проблемы изоморфизма графов и аналогичных проблем. Я чувствую, что все еще недостает глубокого понимания, как работают квантовые алгоритмы. Несомненно, возможности квантовых компьютеров основаны на скрещениях, квантовом параллелизме и обширности гильбертова пространства, но я думаю, что этот вопрос будет полностью разрешен по мере понимания истинной сущности материи. Один из вопросов можно сформулировать так: как постоянная Планка $\hbar$ участвует в квантовых вычислениях, и какова природа «классического» предела $\hbar \rightarrow 0$ ? Я предполагаю, что лучшее понимание такого вида вопросов могло бы указать нам на новые типы квантовых алгоритмов.
${ }^{1}$ Фактически, ослабленная версия этого утверждения («относительно оракула») была продемонстрирована Бернштейном и Вазирани (Bernstein \& Vazirani, 1993).
В другом выступлении на этой конференции (Preskill, 1997) я оценил ресурсы, которые будут необходимы, чтобы решить интересную проблему разложения на множители на квантовом компьютере. Оценка, несомненно, обескураживала. Возможно, что интересная задача квантового моделирования могла быть эффективно выполнена и с более скромными ресурсами. Но также естественно спросить, что можно делать с небольшим квантовым компьютером, который может хранить, скажем, десятки кубитов и содержать сотни гейтов. Если мы могли бы построить такой прибор в ближайшее время, было бы это полезно? Имел бы он коммерческий потенциал?

Одним из возможных применений квантового компьютера скромных размеров была бы квантовая криптография (Bennett \& Brassard, 1984). Конечно, в отсутствие квантового устройства факторизации, обычное шифрование с открытым ключом может быть безопасным, но я полагаю, что всегда найдутся пользователи, которые будут настаивать на полной секретности, и поэтому предпочтут распространение квантовых ключей. (С другой стороны, пользователь может опасаться, что его сообщение будет сохранено и расшифровано через некоторое время в будущем, когда станут доступными более мощные методы разложения на множители.) Хотя в принципе распространение квантовых ключей может быть безопасно, имеется серьезное ограничение: сигнал затухает в канале связи (типа волоконного световода), и не может быть усилен из-за теоремы, запрещающей клонирование (Wootters \& Zurek, 1982). Так что или мы должны быть удовлетворены связью, ограниченной расстояниями порядка длины затухания в волокне (возможно, десятки километров), или следует полностью доверять посредникам, что повлечет за собой серьезный риск для безопасности. Но квантовое исправление ошибки может обеспечить альтернативу: если мы можем приготовить, послать и получить скрещенные многофотонные состояния, то в принципе мы могли бы использовать квантовые коды для исправления ошибок, чтобы расширить возможности квантовой связи. «Повторители» могли бы разместиться вдоль линии связи; они не читали бы квантовую информацию, которая передается, а лишь диагностировали и исправляли бы ошибки, которые возникают при передаче. Можно было бы посылать, скажем, блоки из пяти фотонов, которые кодируют один логический кубит (Беннетт et al., (Bennett, 1996), Лафлам et al., (Laflamme, 1996)), помещенный случайным образом в одно из двух неортогональных состояний, и разместив повторяющие станции достаточно близко, для того, чтобы вероятность ошибки в течение передачи между последовательными станциями была мала. Наши квантовые компьютеры должны быть способными к передаче отказоустойчивого признака измерения и исправления ошибки для пятикубитового кода с малой вероятностью ошибки (Shor, 1996; DiVincenzo \& Shor, 1996). Для достижения приемлемой скорости передачи мы должны уметь быстро обновлять вспомогательные биты, используемые для вычисления признака. Конечно, с более мощными квантовыми компьютерами можно использовать лучшие коды и улучшать функционирование сети.

Возможно, что лучшие часы достаточно близкого будущего будут содержать квантовый компьютер. Точность некоторых атомных часов ограничена конечностью времени жизни возбужденных состояний атома. Применение кодов, исправляющих ошибки, могло бы, в принципе, увеличить время активной работы этих состояний и привести к более высоким стандартам частоты. Группа NIST (Bollinger et al., 1996) предложила другой способ применения квантового скрещения для увеличения точности часов и интерферометров.

Если для определения эталона частоты использовать изменение фазы состояния $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ двухуровневой системы, то состояние $\frac{1}{\sqrt{2}}(|000 \ldots 0\rangle+|111 \ldots 1\rangle)$, построенное из $N$ таких систем, будет осциллировать в $N$ раз быстрее и может быть, в принципе, использовано для установления более точного стандарта ${ }^{1}$.

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

Но предположим, что я могу купить имеющийся в наличии действительно мощный квантовый компьютер сегодня — что я буду с ним делать? Я не знаю, но мне кажется, что над этим придется подумать! Мой внутренний голос говорит, что если мощные квантовые компьюте-
${ }^{1}$ Однако увеличение точности, которая может быть достигнута при использовании скрещенных состояний, сильно ограничено эффектами некогерентности. Поскольку скрещенные состояния осциллируют быстрее нескрещенных, они быстрее и хаотизируются (Huelga et al., 1997).
ры будут доступны, нам придется много и долго думать, как поумнее использовать их возможности.