М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 80
Текст из файла (страница 80)
4.15,) Уравнение (6.25) означает, что сГ(Д!) — вращение на сфере Блоха вокруг оси г, определяемой выражением г" = соз — + з!и (6.26) 6.2. Квантовый поиск как квантовое моделирование 325 на угол д, задаваемый соотношением (6.27) соз — = соз — — 81п — ф 3) которое при замене ф 2 = аз — 11з = (2/Ж вЂ” 1) упрощается до вида (6.28) соз — = 1 — — з(п Заметьте, что ф г = 2 и", поэтому операторы (ф)(ф( и )я)(х~ лежат на проведенной вокруг оси и окружности на сфере Блоха. Подведем итог: действие оператора У(Ы) заключается в повороте оператора ~ф)(ф вокруг оси и" на угол д, как показано на рис.
6.6. Мы прервем процедуру, когда выполнено уже достаточно поворотов для того, чтобы перевести оператор ~ф) (ф~ в окрестность оператора ~х) (х). Вначале мы предполагали, что величина Ы мала, поскольку рассматривался случай квантового моделирования, однако из уравнения (6. 8) 6.28 следует, что было бы разумно выбрать Ы = я, чтобы максимизировать угол поворота д. Если поступить таким образом, то получим соз(0/2) = 1 — 2/Ф, что при больших Л соответствует значению 9 4/ь/М, а число обращений к оракулу, необходимых для отыскания решения (х), будет иметь порядок 0(ь~ ), О,/У1 как и в исходном квантовом алгоритме поиска. о о — + Г з.
Ъ. ег еу '.,ага~ Рис. 6.6. Сфера Блаха, на которой показан поворот начального состояния вг вокруг оси г в сторону конечного состояния з В самом деле, если выбрать Ь1 = и, то такое «квантовое моделирование» идентично исходному квантовому алгоритму поиска, поскольку при квантовом моделировании применяются операторы ехр( — Йг)ф)(ф)) = 1 — 2)ф)(ф( и 326 Глава 6. Квантовые алгоритмы поиска ехр( — йг)х) (хО = 1 — 2)х) (х), которые с точностью до общего фазового множителя идентичны шагам в итерации Гровера. При таком рассмотрении изображенные на рис.
6.2 и 6.3 схемы для квантового алгоритма поиска являются упрощениями схем, показанных на рис. 6.4 и 6.5 для моделирования, в частном случае Ы = вй Упражнение 6.10. Покажите, что путем подходящего выбора ЬГ можно получить квантовый алгоритм поиска, где используется 0(ч/Ф) обращений и для которого вектор конечного состояния «почно равен ~х), т. е. алгоритм срабатывает с вероятностью единица, (а не какой-либо меньшей). Мы получили заново квантовый алгоритм поиска другим способом — используя методы квантового моделирования. Почему этот подход действует? Можно ли его использовать для поиска других быстрых квантовых алгоритмов? Трудно определенным образом ответить на эти вопросы, однако выскажем несколько соображений, представляющих интерес. Основная процедура содержит четыре шага: 1) определить задачу, требуклпую решения, включая описание необходимых входных и выходных данных для квантового алгоритма; 2) угадать гамильтониан, который дает решение поставленной задачи, и проверить, что он действительно работает; 3) найти процедуру, которая моделирует гамильтониан и 4) изучить ресурсы, используемые для моделирования.
Данный подход отличается от обычного в двух отношениях: необходимо угадать гамильтониан, а не квантовую схему; кроме того, отсутствует аналогия с шагами моделирования в стандартном подходе. Более важным из указанных двух различий является первое. Существует большая свобода в выборе квантовой схемы, решающей задачу. С одной стороны, эта свобода определяет большую мощь квантовых вычислений, с другой — делает поиск эффектных схем весьма непростым занятием. Напротив, определение гамильтониана — более жесткая задача, следовательно, для ее решения имеется меньше свободы, но эти же самые ограничения на самом деле упрощают поиск эффективного квантового алгоритма. Мы видели, что это происходит с квантовым алгоритмом поиска, вероятно, с помощью такого метода можно найти и другие квантовые алгоритмы — это не известно.
По крайней мере неоспоримо то, что подход «квантовые алгоритмы как квантовое моделирование» дает интересную альтернативу для развития квантовых алгоритмов. 'Упражнение 6.11 (квантовый поиск нескольких решений в непрерывном времени). Угадайте гамильтониан, позволяющий в непрерывном времени решить задачу поиска в случае, когда имеется М решений.
Упражнение 6.12 (альтернативный гамильтониаи для квантового по. иска). Пусть Н = !х)(ф(+ !Ф)(х!. (6.29) 1. Покажите, что для поворота состояния !ф) до состояния /х) требуется время 0(1), если эволюция описывается гамильтонианом Н. 2. Объясните, как может быть выполнено квантовое моделирование гамильтониана Н, и определите, сколько обращений к оракулу требуется в этом случае, чтобы получить решение с высокой вероятностью. 6.3.
Квантовое перечисление 327 6.3 Квантовое перечисление Насколько быстро можно определить количество решений М в задаче поиска из Ж элементов, если М заранее не известно? Очевидно, что на классическом компьютере потребуется 9(Ж) обращений к оракулу. С помощью квантового компьютера можно определить число решений гораздо быстрее, чем с помощью обычного — необходимо использовать итерации Гровера и процедуру определения собственного числа, основанную на квантовом преобразовании Фурье (см. гл. 5). Рассмотрим важные применения этого факта. Во-первых, если мы умеем быстро определять число решений, то так же быстро можно находить решение, даже если заранее неизвестно, сколько их.
Для этого нужно сначала определить число решений, а потом применить квантовый алгоритм поиска для нахождения решения. Во-вторых, квантовое перечисление позволяет установить, существует ли вообще решение для данной задачи поиска: мы просто должны понять, равно число решений нулю или нет. Имеются применения этой идеи, например, для решения МР-полных задач, которые могут быть сформулированы как вопрос о существовании решения задачи поиска.
Упражнение 6.13. Рассмотрите классический алгоритм для решения задачи перечисления, который выбирает равномерно и независимо й рэз элементы из пространства поиска; пусть Хм..., Хь — результаты, полученные при обращениях к оРакулу, т. е. Х = 1, если 1-е обращение к оракулу дало решение задачи, и Х1 = О, если зе обращение к оракулу не дало решения.
Этот алгоритм выдает оценку Я ы Ф х 2 „. Ху/й для числа решений задачи поиска. Покажите, а * * ЯР ЬЕ-~м(Т-м)~~.Д жите, что для получения с вероятностью не менее 3/4 правильной с точностью до ~/М оценки для М при любых значениях М следует принять /с = П(Л). Упражнение 6.14. Докажите, что любой классический алгоритм перечислении, дающий с вероятностью не меньше 3/4 правильную оценку для М с точностью с~/М при некоторой константе с для любых значений М, должен использовать Й(Ф) обращений к оракулу. Квантовое перечисление — это применение описанной в разд. 5.2 процедуры нахождения собственного числа итерации Гровера С, позволяющее определить количество решений М задачи поиска.
Пусть |а) и ~Ь) — два собственных вектора итерации Гровера в пространстве, натянутом на векторы ~а) и ф», а д— угол поворота, определяемый итерацией Гровера. Из уравнения (6.13) следует, что соответствующие собственные числа равны еш и едэх э~. Для простоты анализа удобно предположить, что оракул был расширен, как это описывалось в разд. 6.1, за счет увеличения количества элементов в пространстве поиска до 2Ь7 и обеспечения выполнения условия з1пз(6/2) = М/2Ю. Схема определения собственного числа, используемая для квантового перечисления, показана на рис.
6.7. Ее значение состоит в том, чтобы определить д с точностью 2 ™ при вероятности успеха не менее (1 — е). Первый регистр содержит $ = гл + [(ой(2+ 1/2е)» кубитов, как в процедуре определения собственного числа, а второй включает (М + 1) кубит, что является достаточным для реализации итерации Гровера на расширенном пространстве поиска. Со- 328 Глава 6.
Квантовые алгоритмы поиска стояние второго регистра переводится в суперпозицию всех возможных входных значений с равными весами ( ~х)) с помощью преобразования Адамара. Как показано в равд. 6.1, это состояние есть суперпозиция собственных состояний ~а) и ~б), поэтому, согласно результату равд. 5.2, схема, изображенная на рис. 6.7, дает ответ 0 или (2я — В) с точностью )ЬВ! < 2 ™ при вероятности не менее (1 — с). Более того, ответ 2т — 0, очевидно, эквивалентен ответу 0 с той же точностью, псетому в действительности процедура определения собственного числа определяет значение 0 с точностью 2 ~ и вероятностью успеха (1 — с). !О) регистр 1 г кубитоа 1О) !0) ~0) 1О) регистр 2 и+1 кубитов 1О) 1О) Рис.
6.7. Скема для выполнения приближенного квантового перечисления на квантовом ком- пьютере. Используя уравнение еш (О/2) = М/2И и нашу оценку для величины О, получим оценку для количества решений М. Насколько большой будет ошибка ЬМ в этой оценке? Выполним следующую последовательность вычислений: — зш + зш — зш — з)п — . (6.31) Из курса анализа известно, что (в)п((0+ 2),0)/2) — вш(0/2)( < (к),0(/2, поэтому (с учетом очевидного тригонометрического неравенства ! з!п((0+ ЬВ)/2! < ) зш(0/2)(+ (ЬВ/2() получим оценку (6.32) Сделав подстановку зш~(0/2) = М/2Л и учитывая тот факт, что )сХВ( < 2 ™, получим окончательную оценку для ошибки определения величины М: )ЬМ( < ЛМЖ+ 2 (6.33) 6.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
