М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 78
Текст из файла (страница 78)
Это означает, что 0(а!а) + Ь|33)) = а!а) — Ь)13). Аналогично, оператор 2!Ф)(ф — Е также производит отражение в плоскости, задаваемой векторами /а) и Щ, относительно вектора /ф). А композиция двух отражений представляет собой поворот! Таким образом, для любого й состояние С~~ф) остается в пространстве, натянутом на векторы а и 33). Отсюда можно получить угол поворота. Пусть соз(6/2) = (И вЂ” М)/Ж, так что )ф) = соз(д/2))а) + в1п(6/2)ф).
Как показано на рис. 6.3, после выполнения двух отражений, композиция которых равна повороту С, вектор ~ф) переходит в 6.1. Квантовый алгоритм поиска 317 где д — действительное число в диапазоне от 0 до и/2 (для простоты будем считать, что М < г//2; вскоре мы снимем зто ограничение), выбранное таким образом, что ,,„в 2 й(н:и) (6.14) 6.1.4 Эффективность Какое количество итераций Гровера необходимо выполнить, чтобы повернуть вектор )ер) близко к вектору )Д? Начальное состояние системы задается век- ~Ф) = ттр-В77М )+ 'Л7рФЬ вгссоз /М/Ж вектор состояния переходит в ф).
Обозначим через С1(х) целое число, ближайшее к действительному числу х; будем считать, что половина всегда округляется в меньшую сторону, т. е. С1(3.5) = 3. Тогда, повторив итерацию Гровера агссоз т/гМ/Ж д (6.15) Рис. 6.3. Однократноедевствие итерации Гровера О вектор состояния поворачивается на угол Р в сторону суперпозиции ~)Д всех решений задачи поиска, В начальный момент вектор состояния отклонен на угол Р/2 от вектора )о) (состояния, ортогонального состоянию (Д) Оракул О отражает состояние относительно вектора )а), затем оператор 2рр) (ф — 7 отражает его относительно вектора ф).
Здесь векторы )о) и Щ для наглядности изображены немного длиннее, чем должны быть (все векторы должны иметь единичную длину) После многократного применения итерации Гровера вектор состояния оказывается близко к вектору (Д, после чего наблюдение в вычислительном базисе дает с большой вероятностью решение задачи поиска Алгоритм обладает эамечательноЯ эффективностью, поскольку Р ведет себя как П(ьуМ/АГ), т е требуется порядка О(ь/Й/М) итерациЯ, чтобы повернуть вектор состояния в положение, близкое н векору !6) 318 Глава 6.
Квантовые алгоритмы поиска рэз, мы уменьшим угол между образом вектора ~г/г) и вектором Щ до величины, меньшей 9/2, причем д/2 < я/4. Измерение, проведенное над этим состоянием в вычислительном базисе, даст решение задачи поиска с вероятностью не менее 1/2. На самом деле, для специально выбранных значений М и гг' можно достичь гораздо большей вероятности успеха. Например, когда М « Аг, получим 6 ю э1пд ж 2~/М/Н, т. е.
отличие по углу на конечной стадии не превышает д/2 — ~/М/АГ, что приводит к вероятности ошибки, не превышающей М/Ж. Обратите внимание, что В зависит от числа решений М, а не от того, чему они равны, поэтому, если известно число М, можно применить описанным выше образом квантовый алгоритм поиска. В равд. 6.3 мы объясним, как применять алгоритм поиска даже при неизвестном значении М.
Выражение (6.15) полезно для точного определения числа вызовов оракула при квантовом поиске. Однако удобно было бы иметь более простое выражение, передающее в общих чертах поведение величины В. Предположим пока, что М < Ф/2, тогда В,В 1М вЂ” > э1п — = 1,г —, 2 2 г" йг' (6.16) откуда следует верхняя оценка числа итераций а [. З~ (6.17) Таким образом, чтобы получить решение задачи поиска с высокой вероятностью, необходимо выполнить В = 0(~гГЙ/М) итераций Гровера (а следовательно, и обращений к оракулу); т. е. мы имеем квадратичное улучшение по сравнению с классической оценкой 0(Ж/М). Квантовый алгоритм поиска описывается виже (рассмотрен случай М = 1).
Начальное состояние Применить Нв". к первым и кубвтам и НХ к последнему ку- биту Применить итерацию Гровера В примерно [я42"/4) раз Измерить первые и кубитов 4. — хс Алгоритм: квантовый поиск Вход: 1) черный ящик с оракулом О, который выполняет преобразование 0)х)р7) = )х))г7 ® /(х)), где /(х) = 0 при 0 < х < 2" за исключением х = хс, для которого /(хе) = 1; 2) (и + 1) кубит в состоянии )0). Выход: хс. Время выполнения: 0(~/2") операций. Вероятность успеха 0(1).
Процедура: 1. )0)н"10) 2. — + ~~„~ „(х) ~)-Щ-1~ 6.1. Квантовый алгоритм поиска 319 Упражнение 6.4. Выпишите в явном виде шаги квантового алгоритма поис ка, аналогичные приведенным выше, но для случая М решений (1 < М < Ж/2). Что происходит, когда более половины элементов являются решениями за д~,*.. м>к!си„р,в= .~а,~м[~Г~м~н~ (сравните с формулой (6.14)) можно заметить, что угол 6 уменьшается, когда М меняется от Ж/2 до Ф. Из этого следует, что количество итераций в алгоритме поиска растет с увеличением М (при М > Ф/2).
Интуитивно представляется, что это неподходящее свойство для алгоритма поиска: казалось бы, решения проще найти, когда их число растет. Существуют, по крайней мере, два способа обойти эту проблему. Если заранее известно, что М больше, чем Ж/2, то можно просто выбрать случайным образом элемент из пространства поиска, а затем с использованием оракула проверить, является ли он решением задачи поиска. Вероятность успеха такого подхода не менее половины, и требуется одно обращение к оракулу. Неудобство этого способа заключается в том, что мы можем не знать заранее величину М. В том случае, когда неизвестно, выполняется ли условие М > Ф/2, можно использовать другой подход.
Он интересен сам по себе, и для него существует полезное применение — он упрощает анализ квантового алгоритма для вычисления количества решений задачи поиска (см. разд. 6.3). Основная идея заключается в удвоении количества элементов в пространстве поиска путем добавления к пространству поиска Ф дополнительных элементов, ни один из которых ие является решением.
В результате в новом пространстве решениями будет являться менее половины элементов. Это осуществляется за счет добавления одного кубита ~д) к переменной, нумерующей элементы пространства поиска, из-за чего количество элементов, среди которых ведется поиск, удваивается и становится равным 2Ф. После этого строится новый расширенныб оракул О', который помечает элемент только в том случае, если он является решением задачи поиака, а дополнительный бит равен нулю. В упражнении 6.5 предлагается объяснить, как оракул О' может быть построен с использованием одного обращения к оракулу О.
Для новой задачи поиска имеется только М решений из 2Ф элементов, и мы увидим, что при запуске алгоритма поиска с новым оракулом О' потребуется самое большее В = (к/4) ~/2Ф/М обращений к оракулу О', а, следовательно, для решения задачи поиска необходимо О(1/Й/М) обращений к оракулу О. Упражнение 6.5. Покажите, что расширенный оракул О' может быть построен с помощью од(ократно использованного оракула О и применяемых к дополнительному кубиту ~д) базисных квантовых элементов. Квантовый алгоритм поиска имеет много применений, некоторые из них будут описаны в последующих разделах.
Квантовый алгоритм поиска очень полезен, поскольку мы не делаем предположений о какой-либо конкретной структуре решаемой задачи поиска. В этом большое преимущество формулирования задачи в терминах оракула, представляющего собой черный ящик, и мы будем использовать этот подход везде, где это окажется удобным в оставшейся части 320 Глава 6. Квантовые алгоритмы поиска Вставка 6.1. Квантовый поиск: двухбитовый пример Приведем пример, иллюстрирующий работу квантового алгоритма поиска на пространстве поиска с г1 = 4. Оракул, для которого /(з) = 0 при всех я, кроме такого х = хе, что Дхс) = 1, может задаваться одной из четырех схем соответствующих хс = О, 1, 2, 3 (слева направо), при этом два верхних кубита содержат запрос х, а нижний — ответ оракула.
Квантовая схема, которая выполняет начальные преобразования Адамара и одну итерацию Гровера, имеет вид В начальный момент два верхних кубита приготавливаются в состоянии ~0), а нижний — в состоянии ~1). Элементы, находящиеся внутри пунктирной рамки, выполняют операцию условного фазового сдвига 2(00) (00)— 1. Сколько раз следует повторить операцию О, чтобы получить хс? Из уравнения (6.15), используя условие М = 1, найдем, что требуется меньше одной итерации. Это следует из того, что д = я/3, согласно формуле (6.14), и в этом особом случае необходима точно одна итерация, чтобы идеальным образом получить хс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
