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

Работа любой вычислительной машины – это неизбежно физический процесс. Тем не менее, стандартная математическая теория, которая используется для изучения возможностей и ограничений вычислений (например, произведенных на машинах Тьюринга), не признает квантовые механические эффекты, в частности наличие когерентных суперпозиций при вычислениях. Подходящее определение квантового компьютера, который, как и машина Тьюринга, идеализирован, как работающий безошибочно и имеющий неограниченные возможности памяти, но который способен использовать квантовые эффекты программируемым способом, было сформулировано одним из нас в 1985 г. (Дойч, 1985). Квантовые компьютеры не могут вычислять функции, которые в свою очередь не вычислимы по Тьюрингу, но они обеспечивают новые типы вычислений для многих классов задач. В данной статье мы продемонстрируем важность квантовых процессов для достижения результатов в теории вычислительной сложности. Мы описываем задачу, которая может быть решена более эффективно с помощью кванто-
${ }^{*}$ Proc. R. Soc. Lond. A (1992) 439, 553-558.

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

Пусть $U_{f}$ – устройство, которое вычисляет функцию $f: \mathbb{Z}_{m} \rightarrow \mathbb{Z}_{n}$. Задав значение на входе $i, U_{f}$ через некоторое время выдаст значение $f(i)$. В общем случае, класс вычислительных задач, который мы рассмотрим, заключается в использовании $U_{f}$ для вычисления некоторого свойства $G[f]$ (это некоторая функция $G$ от последовательности $f(0), f(1), \ldots f(m-1))$ за наименьшее время.

При анализе данного типа задач часто предполагают, что схема внутренней работы $U_{f}$ недоступна. В этом случае $U_{f}$ называется оракулом для $f$. Приближение будет почти точным, если $U_{f}$ определить как новый тип физического объекта с неизвестными законами движения.

Если $U_{f}$ просто программа для вычисления $f$ на компьютере, то высказанное предположение равносильно тому, что не существует более быстрого метода получения $G[f]$ при помощи программы $U_{f}$ (например, текстовым анализом), чем с помощью выполнения $U_{f}$ для получения достаточно большого числа значений $f(i)$ для определения $G[f]$. Кажется очевидным, что это справедливо для всех свойств $G$, однако это утверждение, также как и неравенство $P
eq N P$, трудно доказуемо.

Если $U_{f}$ было бы ROM (read-only memory), содержащее последовательность из $m$ целых чисел, принадлежащих $\mathbb{Z}_{n}$, то предположение звучало бы так, что не существует более быстрого способа получения $G[f]$ из $U_{f}$, чем чтением из ROM достаточно большого числа значений $f(i)$ для определения $G[f]$. Ясно, что в общем случае это утверждение несправедливо, поскольку могут быть физические способы прямого определения $G[f]$, как, например, измерение полного спина, если значения $f(i)$ хранятся как значения индивидуальных спинов, однако рассмотренный пример хорошо демонстрирует многие реальные ситуации.

Удобно разделить вычислительные задачи на вычисление функций и решения задач. В случае функций, задача заключается в получении единственного выходного значения, которое является определенной функцией от входных данных. Например, $U_{f}$, в том виде, в котором мы ее определили, вычисляет функцию $f$. В случае решения задач, целью является получение любого одного выходного значения, которое имеет определенное свойство. Например, поиск множителя заданного составного числа является задачей. Поиск наименьшего простого множителя – это вычисление функции.

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

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

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

Допустим, что операция $U_{f}$ – это когерентный квантовомеханический процесс. Разумеется, все физические процессы подчиняются данному предположению на некотором достаточно полном уровне описания, возможно включающем их окружение. Но мы имеем в виду, что $U_{f}$ может быть подходящим образом сделано частью когерентного вычисления квантового компьютера.
Пусть $\mathscr{H}_{m n}$ – гильбертово пространство размерности $m n$ и пусть
\[
\{|i, j\rangle\}\left(i \in \mathbb{Z}_{m}, j \in \mathbb{Z}_{n}\right)
\]

фиксированный ортонормированный базис в $\mathscr{H}_{m n}$. Предположим, что $U_{f}$ принимает входные данные в любом состоянии базиса $|k, 0\rangle$, соответствующем величине $k$ и преобразует его в выходные данные в состоянии $|k, f(k)\rangle$, из которого значение $f(k)$ может быть получено с вероятностью 1. В общем случае можно предполагать, что $U_{f}$ выполняет унитарное преобразование
\[
|i, j\rangle \xrightarrow{U_{f}}|i, j+f(i)\rangle,
\]

где в выражении $j+f(i)$ сложение выполнено по модулю $n$. Тогда, учитывая линейность квантовой эволюции, $U_{f}$ преобразует входное состояние
\[
m^{-\frac{1}{2}}(|0,0\rangle+\ldots+|m-1,0\rangle)
\]

в выходное состояние
\[
m^{-\frac{1}{2}}(|0, f(0)\rangle+\ldots+|m-1, f(m-1)\rangle) .
\]

Таким образом, выполняя $U_{f}$ только один раз, мы получаем в некотором смысле вычисленными все $m$ значений функции $f$ в суперпозиции. Элементарная квантовая теория вычислений показывает, что квантовые вычисления, выполненные над системой в состоянии (4), не могут быть применены для получения более чем одного из $m$ значений $f(0), \ldots f(m-1)$. Однако, возможно извлечь некоторые общие свойства $G[f(0), \ldots f(m-1)]$ для $m$ значений, измеряя определенные
наблюдаемые, которые не диагональны в базисе (1). Этот прием называется методом вычислений на основе квантового параллелизма, он возможен только на компьютерах, вычисления в которых являются когерентными квантовыми процессами. Дальнейшие примеры можно найти в статьях Дойча (1985) и Джозса (1991).

В настоящее время все известные вычислительные задачи, которые могут быть выполнены более эффективно с помощью квантового параллелизма, чем с помощью любого классического метода, имеют два основных свойства. Во-первых, нет уверенности в том, что ответ будет получен за заданный промежуток времени, т. е. существует некоторая вероятность того, что программа сообщит о неудаче, уничтожая информацию о функции $f$, поэтому в общем случае придется все повторять несколько раз, прежде чем будет получен ответ. Во-вторых, хотя в некоторых случаях вычисления производятся быстрее, чем в любом классическом алгоритме, в среднем квантовый алгоритм не эффективнее классического. Можно показать (Дойч, 1985), что второе свойство должно проявиться, по крайней мере, для одного выбранного входного значения при квантовом вычислении любой функции.

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

Задача состоит в следующем: заданы натуральное число $N$ и оракул $U_{f}$ для функции $f: \mathbb{Z}_{2 N} \rightarrow \mathbb{Z}_{2}$. Найти истинное утверждение среди следующих:
(A) $f$ непостоянная функция (для 0 или 1 );
(В) последовательность $f(0), \ldots, f(2 N-1)$ значений функции $f$ не содержит в точности $N$ нулей.

Заметим, что для любой функции $f$ хотя бы одно из утверждений (А) или (В) всегда истинно. Возможно, что истинны оба утверждения, в таком случае или (A), или (B) является приемлемым решением. Это является причиной того, что решение задачи не обязательно равносильно вычислению функции. Стохастический или квантовый алгоритм решения задачи может иметь такое свойство: когда (A) и (В) оба истинны, то он возвращает один из ответов случайным образом. Но когда истинно только одно из утверждений, алгоритм должен возвратить именно его.

Рассмотрим сначала классическое решение. Мы выполняем $U_{f}$ несколько раз для вычисления значений $f$ в некотором порядке, скажем $f(\Pi(0)), f(\Pi(1)), f(\Pi(2)), \ldots$, где П – это перестановка $\mathbb{Z}_{2 N}$. Мы продолжаем процесс до тех пор, пока у нас не будет достаточно информации для подтверждения того, что (А) или (В) истинно. Это всегда достигается по крайней мере за $N+1$ вызовов $U_{f}$, хотя некоторые функции $f$ требуют меньшего числа вызовов. Представляя функцию $f$ последовательностью из $2 N$-элементов $f(\Pi(0)), \ldots f(\Pi(2 N-1))$ из нулей и единиц, мы получаем результаты, представленные в таблице 1.

Следовательно, при заданном большом числе случайных функций $f$ среднее число вызовов $U_{f}$, требуемое для решения задачи для каждой функции $f$ равняется
\[
\frac{N+1}{2^{N-1}}+\sum_{n=2}^{N} n\left(\frac{1}{2}\right)^{n-1}=3-\frac{1}{2^{N-1}},
\]

то есть примерно три вызова для достаточно большого числа $N$. Если же нам исключительно не повезло или если функции $f$ распределены неслучайно, но заданы кем-то, кто знает, какой алгоритм мы собираемся использовать, то требуется $N+1$ вызовов. В случае классического стохастического компьютера мы можем выбрать перестановку П случайным образом, поэтому процесс, который в среднем требует $O(\ln (N))$ шагов, может получить решение задачи за три вызова, однако в неудачных для нас случаях это значение может повыситься до $N+1$ вызовов плюс $O(N \ln (N)$ шагов.

Теперь представим один из методов решения, использующий квантовый параллелизм. Пусть $S$ – унитарная операция, определенная как
\[
S|i, j\rangle=(-1)^{j}|i, j\rangle .
\]

Эта операция может быть выполнена квантовым компьютером (ср., Дойч, 1985) за фиксированное число шагов, независимое от $N$ и $f$. Состояние
\[
|\phi\rangle=\frac{1}{\sqrt{(2 N)}} \sum_{i=0}^{2 N-1}|i, 0\rangle
\]
может быть получено, начиная с «пустого» входного состояния $|0,0\rangle$, за $O(\ln (N))$ шагов, независимо от $f$. Например, если $2 N$ – это степень числа 2 , то это можно сделать применением элементарного однобитного преобразования
\[
|x\rangle \rightarrow \frac{1}{\sqrt{2}}\left(|x\rangle+(-1)^{x}|1-x\rangle\right) \quad\left(x \in \mathbb{Z}_{2}\right)
\]

последовательно к каждому из $\log _{2}(2 N)$ битов, которые определяются значением $i$ в (7).

При заданном квантовом оракуле $U_{f}$ применим последовательно три операции $U_{f}, S, U_{f}$ к участкам памяти, находящимся в состоянии $|\phi\rangle$. Тогда из $(1),(6)$ и (7) получаем:
\[
\begin{array}{c}
|\phi\rangle \xrightarrow{U_{f}} \frac{1}{\sqrt{(2 N)}} \sum_{i=0}^{2 N-1}|i, f(i)\rangle \xrightarrow{S} \frac{1}{\sqrt{(2 N)}} \sum_{i=0}^{2 N-1}(-1)^{f(i)}|i, f(i)\rangle \rightarrow \\
\xrightarrow{U_{f}} \frac{1}{\sqrt{(2 N)}} \sum_{i=0}^{2 N-1}(-1)^{f(i)}|i, 0\rangle \equiv|\psi\rangle .
\end{array}
\]

Скалярное произведение
\[
|\langle\phi \mid \psi\rangle|=\frac{1}{2 N}\left|\sum_{i=0}^{2 N-1}(-1)^{f(i)}\right|
\]

равно нулю, когда утверждение (В) ложно, и равно единице, когда (А) ложно. Следовательно, если после выполнений операции в (9) мы измеряем проектор наблюдаемой $|\phi\rangle\langle\phi|$ и результат равен 0 , то можно быть уверенными в том, что $|\psi\rangle$ не было параллельно $|\phi\rangle$ и, следовательно, что (А) истинно. А если результат равен 1 , то можно быть уверенными в том, что $|\psi\rangle$ не было ортогонально к $|\phi\rangle$ и, следовательно, что (В) истинно. Результат должен быть равен или 0 , или 1 , поскольку они являются единственными собственными значениями проектора наблюдаемой. Следовательно, процедура точно установит истинность или (А), или (В).

Измерение $|\phi\rangle\langle\phi|$ может быть выполнено за $O(\ln N)$ шагов. Обратное преобразование, которое получает $|\phi\rangle$ из пустого состояния $|0,0\rangle$, а затем, измеряя $|0,0\rangle\langle 0,0|$, которое просто сводится к измерению каждого бита в отдельности. Оракул $U_{f}$ вызывается ровно дважды в (9), и более не требуется ни одного его вызова. Это явное преимущество по сравнению со средним числом вызовов, равным $3-2^{-N+1}$ при использовании лучшего классического или стохастического метода, и огромное преимущество по сравнению с худшим случаем ( $N+1$ вызовов) для любого из этих методов. Заметим, что задача решается в каждом из случаев наверняка.

Интересно сравнить вычислительную сложность рассматриваемой задачи относительно классического и квантового компьютеров. В классическом случае, полиномиальная эквивалентность в теории сложности (Гэри и Джонсон, 1979) основана на моделях детерминированных (DTM) и недетерминированных (NDTM) машин Тьюринга. Сперва отметим один важный результат (обозначаемый далее (*)), что для любого классического решения нашей задачи, используя DTM, существует функция $f: \mathbb{Z}_{2 N} \rightarrow \mathbb{Z}_{2}$, которая требует, по крайней мере, $N+1$ вызовов оракула. Чтобы показать это, предположим, что DTM может решить задачу для каждой такой функции $f$, используя только $M \leqslant N$ вызовов. Пусть $f_{c}$ – постоянная функция такая, что утверждение (А) ложно, и
машина должна заключить, что выражение (В) истинно. Тогда для любых $M$ вызовов оракула, какими бы не были выбраны входные данные, существует функция $g$, которая совпадает с $f_{c}$ для всех $M$ и имеет точно $N$ нулевых значений. Поскольку, по предположению, $M$ значений определяют всю информацию, которую DTM имеет о функции, она не может отличить $U_{f_{c}}$ от $U_{g}$, следовательно, не может заключить, что выражение (В) истинно. Тот же аргумент, применимый к NDTM, показывает, что решение задачи, является ли (В) истинным или нет, не принадлежит классу NP (хотя соответствующая задача для (A) решается в классе NP, а не в P).

Для оценки сложности задачи рассмотрим сначала идеализированную ситуацию, в которой полагается, что оракул выдает результат за один шаг вычисления и не влияет на размер входных данных задачи. Тогда задача определяется заданием $N$, которому соответствует размер $O(\ln N)$. Таким образом, из (*) следует, что для решения требуется экспоненциальное время. Квантовое вычисление, требующее только двух вызовов, и времени $O(\ln N)$, необходимое для установки состояния на входе, решает задачу за полиномиальное время. Таким образом, задача принадлежит QP – квантовому аналогу класса P.

Если мы желаем более реалистично смоделировать размер оракула и время вычисления, тогда мы могли бы принять размер оракула равным $O(N)$ для общего вида функции $f$, что будет равняться размеру оракула, который просто содержит список ROM значений функции. Также для любой функции $f$ существует оракул, который действует в течение времени $O(\ln N)$. Например, для поиска $f(k)$ оракул может обойти бинарное дерево в соответствии с бинарным разложением $k$. Из этих оценок и из (*) следует, что любой классический компьютер требует, по крайней мере, полиномиальное время, в то время как квантовый компьютер требует только логарифмическое время, что снова демонстрирует экспоненциальное ускорение.

Если мы ограничиваем входные значения $f$ классом функций, чьи оракулы имеют размер меньший чем $p(\ln N)$, где $p$ – фиксированный полином неизвестный для решающего, то эта ограниченная задача в классическом случае требует экспоненциальное время, а в квантовом случае только полиномиальное время. Это именно так, поскольку для любого заданного $N$ данное условие, с точки зрения объекта, вычисляющего задачу, не исключает произвольную функцию $f: \mathbb{Z}_{2 N} \rightarrow \mathbb{Z}_{2}$, следовательно, используя тот же аргумент, что и в случае общей задачи, получаем, что классическое решение нельзя получить за время, меньшее, чем экспоненциальное, даже для ограниченной задачи.