М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 79
Текст из файла (страница 79)
Из рис. 6.3 видно, что вектор нашего начального состояния ф) = ()00) + )01) + )10) + )11))/2 отклонен на угол 30' от вектора )а), и один поворот на угол 60' переводит )Ф) в ))3). Вы можете самостоятельно (с использованием квантовых схем) непосредственно проверить тот факт, что измерение над двумя верхними кубитами дает результат хс (после однократного использования оракула).
Напротив, с использованием классического компьютера (или классической схемы) попытка различить четыре состояния потребует в среднем 2,25 обращений к оракулу. главы. В конкретных применениях, конечно, необходимо понимать, как именно устроен оракул, и в каждой из таких конкретных задач будет обсуждаться реализация используемого в ней оракула. 6.2. Квантовый поиск как квантовое моделирование 321 Упражнение 6.6. Проверьте, что элементы, заключенные в пунктирную рамку на нижнем рисунке вставки 6.1, выполняют операцию условного фазового сдвига (2(00) (00) — Ц (с точностью до несущественного общего фазового множителя). 6.2 Квантовый поиск как квантовое Н = !х)(х/ + /ф)(ф/, Н = /я)(«Р/ + )ф)(х!. (6.18) (6.19) Оказывается, оба этих гамильтониана приводят к квантовому алгоритму поиска! Однако пока ограничимся изучением гамильтониана (6.18).
Напомним (см. подразд. 2.2.2), что через время 1 состояние квантовой системы, эволюция которой описывается гамильтонианом Н, а начальное состояние определялось вектором ~«Г), имеет вид ж моделирование Правильность квантового алгоритма поиска легко проверить, но неясно, как можно было бы придумать такой алгоритм «с нуля». В этом разделе мы ознакомим читателя с эвристическими средствами, с помощью которых можно «получить» квантовый алгоритм поиска, с тем чтобы у читателя выработался некий интуитивный подход, полезный в сложном деле построения квантовых алгоритмов.
В качестве полезного побочного эффекта мы получим де«перминироеанный квантовый алгоритм поиска. Поскольку цель состоит в приобретении интуиции, а не общности, для простоты предположим, что у задачи квантового поиска только одно решение з. Предлагаемый метод состоит из двух шагов. Вначале необходимо угадать гампльтиояиая, который решает задачу. Точнее говоря, мы выписываем гамильтониан Н, который так зависит от решения х и начального состояния ф), что квантовая система, эволюция которой описывается оператором Н, перейдет из состояния ~Ф) в ~х) за некоторое заданное время. После нахождения такого гамильтониана и начального состояния можно перейти ко второму шагу, который заключается в попытке смоделировать действие гамильтониана с использование квантовой схемы.
Удивительно, но следуя этой процедуре, можно быстро получить квантовый алгоритм поиска! Мы уже встречались с этой процедурой из двух шагов, когда изучали универсальность в квантовых схемах (см. задачу 4.3), и она также хорошо помогает в изучении квантового поиска. Предположим, что в начале выполнения алгоритма квантовый компьютер находится в состоянии ~Ф). Позже мы укажем это состояние, однако сейчас удобно оставить его неопределенным, пока мы не поймем работу алгоритма. Задача квантового поиска состоит в переводе состояния ~ф) в ~х) или в некоторое приближение к последнему. Какой гамильтониан следует выбрать, чтобы он задавал такую эволюцию? Исходя из требований простоты, хотелось бы построить гамильтониан, оперируя только терминами «~ф)» и «)х)». Таким образом, гамильтониан должен быть представлен суммой слагаемых вида ф) (ф, )х)(х(, («г)(х( и )з)(ф. Вероятно, наиболее простыми гамильтоиианами подоб ного типа являются следующие: 322 Глава 6.
Квантовые алгоритмы поиска ехр( — 4Н~) ф). (6.20) С интуитивной точки зрения все выглядит замечательно: для малых 4 эволюция заключается в переводе состояния ~ф) в (Х вЂ” ЙН)~ф) = (1 — Ю)~ф)— Ы(х)ф) ~х). Таким образом, вектор (ф) слегка поворачивается в сторону вектора (х). Проведем полный анализ для того, чтобы определить, существует ли такое 1, что ехр( — гН$)~ф) = ~я). Очевидно, что можно ограничиться двумерным пространством, порожденным векторами ~х) и ~ф). Выполняя процедуру Грама-Шмидта, можно найти такой вектор ~у), что ~х) и ~у) образуют ортонормированный базис в этом пространстве и ф) = а~х) + Ду) для некоторых а и 17, удовлетворяющих условию аз + 1?э = 1 (для удобства выберем фазы состояний ~х) и ~у) таким образом, чтобы числа а и 13 были действительными и неотрицательными).
В базисе ~х), ~д) получим Н= 0 0 + 8 бг = 3 1 з =7+пРХ+п~) (621) Таким образом, выполняется равенство ехр(-4Нй) !ф) = ехр( — й)(сов(ай) !ф) — 4 эш(ай)(1?Х + аЯ) ф)). (6.22) Можно не учитывать общий фазовый множитель ехр( — й), тогда простые алгебраические вычисления показывают, что (~3Х + аЯ) ~ф) = ~я), поэтому состояние системы через время 4 можно представить вектором соэ(а8) ~ф) — 4 эш(аФ) ~х). (6.23) Следовательно, измерение, выполненное над системой через время Ф = я/2а, даст результат ~х) с вероятностью единица: мы нашли решение задачи поиска( К сожалению, время наблюдения зависит от а, т. е. от компоненты вектора ~ф) в направлении ~х), а значит от числа х, которое мы и хотим найти. Очевидное решение этой проблемы заключается в том, чтобы попытаться подобрать число а одинаковым для всех )х), т.
е. сделать |ф) однородной суперпозицией: (6.24) Этот выбор приводит к величине а = 1/~Ф, одинаковой для всех я, тогда время наблюдения составит 4 = я'/Ж/2 вне зависимости от неизвестного заранее значения х. Кроме того, состояние (6.24) обладает тем очевидным преимуществом, что мы уже знаем, как его получить с использованием преобразования Адамара. Теперь нам известно, что гамильтониан (6.18) описывает поворот вектора (ф) в ~х).
Можем ли мы найти квантовую схему, моделирующую гамильтониан (6.18), и таким образом построить квантовый алгоритм поиска? Применяя метод, изложенный в равд. 4.7, можно видеть, что естественный способ 6.2. Квантовый поиск как квантовое моделирование 323 моделирования оператора Н состоит в поочередном моделировании гамильтонианов Н1 ен )х)(х) и Нз рэ 'рр)()(~! на короткие промежутки времени Ы. Эти гамильтонианы легко моделировать, используя методы, рассмотренные в гл.
4 (рис. 6.4 и 6.5). Упражнение 6.Т. Проверьте, что схемы, показанные на рис. 6.4 и 6.5, реализуют соответственно операции ехр(-1(х)(х)ы) и ехр( — ()4)(зр~ьФ), где (ф) определяется уравнением (6.24) . Рис. 6.4. Схема, реализующая операцию ехр( — Щ(с!Ьа) при помощи двух обращений к оракулу.
1у)( Рис. 6Л. Схема, реализующая операцию ехр(-1ф)(ЕЛЖ) при помощи двух обращениИ к оракулу. Число обращений к оракулу при квантовом моделировании определяется тем, насколько малый шаг по времени требуется для получения достаточно точных результатов. Предположим, мы используем шаг моделирования ~М, который дает точность 0(.лаз). Полное количество необходимых шагов равно $/сзс = 9(з/Ж/Ь2), а следовательно, накапливаемая ошибка составит 0(сказ х 1/Ж/пас) = 0(Ь|х/М). Чтобы получить достаточно высокую вероятность успешного завершения алгоритма, необходимо, чтобы ошибка имела порядок 0(1), а это означает, что мы должны выбрать Ы = 9(1/~/Ф), т. е.
требуемое количество обращений к оратору равно 0(М) — не лучше, чем в классическом случае. Что, если попробовать воспользоваться более точным методом квантового моделирования, дающим, например, точность 0(Ы~)2 Накапливаемая ошибка в этом случае составит 0(Ь22х/Ф), поэтому чтобы вероятность успешного завершения алгоритма была достаточно высока, необходимо выбрать Ы = сз(Л 1У4); тогда число обращений к оракулу имеет поря- 21 324 Глава 6. Квантовые алгоритмы поиска док О(!У~~~), что является существенным улучшением по сравнению с классическим случаем, хотя все еще не настолько хорошо, как было в квантовом алгоритме поиска в равд.
6.1! Обычно улучшение точности квантового моделирования приводит к уменьшению числа обращений к оракулу при моделировании (см. упражнение 6.8). Упражнение 6.8. Предположим, что шаг моделирования выполняется с точностью 0(Д!"). Покажите, что число обращений к оракулу при моделировании гамильтониана Н с достаточной точностью имеет порядок 0(№~з<" ц). Обратите внимание, что г становится большим, когда показатель степени у И приближается к 1/2. Мы исследовали точность квантового моделирования гамильтониана (6.18) с использованием общих результатов равд. 4.7, относящихся к квантовому моделированию.
Конечно, в этом примере мы работаем с особым гамильтонианом, а не с общим случаем, поэтому было бы интересно непосредственно вычислить результат шага моделирования со временем Д!, а не полагаться на общий анализ. Это можно сделать для любого конкретного выбора метода моделирования — находить результат шага моделирования немного скучно, зато это вычисление является непосредственным. Очевидный начальный шаг — вычислить в явном виде действие моделирования в первом приближении, т.
е. вычислить одно или оба из выражений ехр( — г)х)(х)ДФ) ехр(-з)ф)(фД!) и ехр( — !~4)(ф)Д!) ехр( — !(х)(х(ДФ). Результаты будут одинаковыми в обоих случаях; мы будем изучать оператор сГ(Д!) эз ехр( — !)ф)(ф(ДФ) ехр( — г!х)(х(Д!). Он действуег нетривиальным образом только на пространство, порождаемое опе. раторами !х)(х! и )6)(Ф!, поэтому ограничимся рассмотрением этого пространства, используя базис !х), !р), где )у) — вектор, определенный вьппе. Обратите внимание, что в этом представлении !х)(х~ = (1+ Я)/2 = (1+ 2 о)/2, где Я = (О, О, 1) — единичный вектор в направлении оси з; (ф) (ф! = (1+ ф ° а)/2, где ф = (2гг!9,0, ггз — ф) (напомним, что это векторное представление Блоха, см. равд.
4.2). Простое вычисление показывает, что с точностью до несущественного общего фазового множителя у(д!) = 2 Д" — !Пз 14 Ф. 2 1 — 2! зш — соз — — + зш — — ° о. (6.25) Упражнение 6.9. Проверьте уравнение (6.25). (Указание: см. упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
