Физика квантовой информации - Бауместер Д.
ISBN 5-94057-017-8
Скачать (прямая ссылка):
Обсудив некоторые основные вычислительные достоинства кван-
146 Концепция квантовых вычислений
товой теории в общем виде, мы теперь опишем работу различных основных квантовых алгоритмов.
4.2.4 Оракулы и алгоритм Дойча
Алгоритм Дойча [124, 138] был первым явным примером вычислительной задачи, которую с помощью квантовых эффектов можно решить экспоненциально быстрее, чем с помощью любых классических средств. Затем он был улучшен в работе [139], и мы здесь опишем его самую новую форму.
Рассмотрим все четыре возможных однобитных функций f .B—>В. Среди них есть две постоянных функции:
/(0) = 0 /(0) = 1 или
/0) = 0 /(1) = 1 (4.6)
и две «сбалансированных» функции (сбалансированных в том смысле, что выходные значения 0 и 1 появляются с одинаковой частотой).
Д0) = 0 Д0)=1
или
Д1) = 1 Д1) = 0 . (4.7)
Предположим теперь, что у нас есть «черный ящик» или «оракул», который вычисляет одну (неизвестно, которую) из этих функций. Оракул можно изобразить как запечатанный ящик (см. Рис. 4.4), который выдает значение функции для любого значения, заданного на входе (или суперпозиции, заданной на входе, как на Рис. 4.5). Или же мы можем представить себе оракула в виде компьютерной подпрограммы, которую мы можем запускать, но чей текст или внутренний принцип работы мы узнать не можем. (Позже мы обсудим важность этого ограничения нашего доступа к оценке/). Наша задача - узнать, что вычисляет оракул, - сбалансированную функцию или константу.
В рамках классической механики нам, разумеется, необходимо запустить оракул дважды, чтобы наверняка решить задачу. Ведь если нам известно только одно значение функции (например, /(0) или/(1), то у нас совсем нет информации о том, сбалансирована ли функция или же она равна константе! Теперь мы покажем, что на квантовом компьютере проблему можно решить точно, обратившись к оракулу всего один раз.
Мы используем возможность квантового параллельного вычисления (как описано выше) с одним дополнительным трюком - в самом начале установим выходной регистр на 1A/~2(| 0) - 11)). Квантовое вычисление идет следующим образом. Начав со стандартного состояния |0) |0) во входном и выходном регистре, мы применяем операцию НЕ к выходному регистру, и затем Н к обоим, что дает
Квантовые алгоритмы 147
(\°Щ
{ V2 J 1 V2 J
_1_
Гг
IJ*>
Гг
(4.8)
Затем мы даем это состояние оракулу, то есть, применяем Uf. Вспоминая, что Uf преобразует |х)|_у) в |х)|_у ®/(х)), мы видим, что
WO0)-!1»если f(x)=o
[-jxXI0)-!1» если f(x) = 1.
Таким образом
хеВ
я
ев
I0)-!1)
Я
(4.9)
В течение всего процесса выходной регистр оставался в состоянии 1/V2(|0)-|1)). Входной регистр оставлен в состоянии 1Л/~2Е1бВ (-1/х)|х). Если /- постоянная функция, то мы получаем ±1Л/"2(|0)+|1)), а если / сбалансирована, то получаем ± 1/л/2(|0)—11)). Легко проверить, что операция Н обратна самой себе, то есть, что НН =/. В заключение процедуры, применим Н ко входному регистру, и получим (с учетом (4.2)) состояние ± |0), если/ - постоянная функция, и ± |1) если/сбалансирована. Эти значения легко различить с помощью измерения в стандартном базисе, таким образом наверняка различив сбалансированную и постоянную функции после всего лишь одного обращения к оракулу. Полная последовательность операций приведена на сетевой диаграмме на Рис. 4.6.
|0>
Рис. 4.6. Алгоритм Дойча для 1-битных функций. Измеренное значение О (соответственно, 1) означает, что функция /- постоянная (соответственно, сбалансированная).
Само по себе различие между одним и двумя обращениями к оракулу не имеет значения при рассмотрении формальной сложности. Однако идею описанного выше процесса можно легко обобщить на случай, когда действительно проявляется экспоненциальное различие между классическим и квантовым процессами.
148 Концепция квантовых вычислений
Вместо рассмотрения функций, отображающих один бит на один бит, предположим, что у нас есть оракул, который вычисляет некоторую функцию от п битов на один бит:
(и мы также знаем значение п). Пусть известно, что эта функция есть либо константа (т.е. все ее 2" значений одновременно равны либо О, либо 1), либо она сбалансирована, где под сбалансированностью понимается то, что ровно половина (т.е. 2я-1) ее значений равна 0, а другая половина равна 1. Заметим, что для n > 1, в общем случае функция из п битов в 1 бит не является ни сбалансированной, ни постоянной, но, тем не менее, существует огромное количество сбалансированных функций. Наша задача снова состоит в том, чтобы определить (с полной определенностью), является ли / константой или сбалансированной функцией. Случай п= 1 - это, в точности, задача, рассмотренная выше.
В классическом сценарии, если мы обратимся к оракулу 2пА раз, чтобы получить 2я'1 значений f то, каким бы образом последующие запросы ни зависели от ответа на предыдущие, мы все равно не сможем решить задачу в каждом случае. Действительно, предположим, что все 2я'1 ответов оказались равны между собой (что всегда возможно, хоть и маловероятно, в случае сбалансированной функции). Независимо от выбора аргументов на входе, всегда найдутся постоянная и сбалансированная функции, полностью согласующиеся с собранной информацией. Следовательно, любое классическое решение задачи должно содержать более, чем 2я'1 обращений к оракулу - то есть, по меньшей мере, экспоненциальное (по п) их число. На самом деле, легко видеть, что 2я'1+1 обращений будет всегда достаточно. В квантовом случае, проблему можно решить с определенностью с помощью всего лишь одного обращения к оракулу. Метод решения -это прямое обобщение случая одного бита.
