М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 71
Текст из файла (страница 71)
Первому требованию удается удовлетворить благодаря процедуре, известной под названием возведение е степень по модулю М, с помощью которой можно реализовать всю последовательность используемых при определении собственного числа операций «упрэвляемое с7~' », затратив на это 0(Ьэ) элементов. Как это делается, описано во вставке 5.2.
288 Глава 5. Квантовое преобразование Фурье и его приложения помощью обращения вычислений. Алгоритм включает два этапа. Сначала, последовательно возводя в квадрат по модулю !У, мы находим х»' (шоб Ф) длявсеху,непревосходящих$ — 1.Унас8 = 2Ь+1+!!о8(2+1/(2е))~! = 0(Ь), так что для этого требуется ! — 1 = 0(Ь) возведений в квадрат, каждое за 0(Ь~) операций (подразумеваегся, что мы возводим в квадрат путем умножения столбиком), поэтому общее количество операций на первом этапе есть 0(Ь2).
Второй этап алгоритма основан на том, что, как было отмечено, х'(шо«! М) = (х"~ (шо«! Ф)) (х"-'2 (шод М))... (х*'~ (апой И)). (5.43) Проведя 1 — 1 умножение по модулю 5!, каждое за 0(Ь~) операций, получим, что произведение можно вычислить с использованием 0(Ь~) элементов. Для ваших целей такой производительности достаточно, но имеются и более эффективные алгоритмы, основанные иа быстрых алторитмах умножения (см. раздел «История и дополнительная литература» в конце главы).
Теперь с помощью метода из подразд. 3.5, легко построить обратимую схему из 0(Ьз) элементов с 8- и Ь-битовым регистрами, которая переводит состояние (з,у) в (з,х'у (шос! И)); зту схему можно переделать в квантовую схему, использующую 0(Ь~) регистров и вычисляющую преобразование (х)(у) т )2)(я*у (гпод !У)). Второе требование более изощренное: ведь чтобы приготовить !и»), необходимо заранее знать г, о чем и речи быть не может. К счастью, одно остроумное наблюдение позволяет обойти эту проблему.
Заметим, что (5.44) При определении собственного числа используем $ = 2Ь+ 1+ !оя 2+ — /! 2е 1) 1 т-1 е2«»ь/т~о«) !хь шот1 А!) «=О (5.45) (Указание: ',с'„' О ехр( — 2тэИ/г) = гбьс.) кубитов в первом регистре (в соответствии с обозначениями на рис. 5.3) и приготавливаем второй регистр в состоянии (1), что тривиально.
Тогда для каждого э из иитервала [О; г — 1] найдем оценку фазы собственного числа !О и э/г сточностью2 2~ 1 ивероятностьюуспеханеменее (1 — е)/г. Общая схема работы алгоритма нахождения порядка изображена на рис. 5.4. Упражнение 5.13. Выведите формулу (5.44). Докажите, что на самом деле 5.3. Приложения: нахождение порядка и факторизация 289 Упражнение 5.14. Квантовое состояние, получаемое в алгоритме нахожде- ния порядка до применения обратного преобразования Фурье, имеет вид г'-1 г'-1 )гр) = ~~~ '1ЯГ')1) = ~~~ (2))яУ пюд гт), (5.46) если начальное состояние второго регистра ~1). Покажите, что получится то же состояние, если УУ заменить на другое унитарное преобразование: )У(Я)к) = (Я)й+ аз пюд гт'), (5.47) и если начальным состоянием второго регистра был ~0).
Объясните также, как сконструировать У с использованием 0(Ь~) элементов. Первый регистр (1кубитов) Второй регистр (Ь кубитов) Разложение е непрерывную дробь Сведение задачи вычисления порядка к определению собственного числа будет завершено, когда мы опишем, как находить искомое число г, исходя из числыр ~ зуг, являющегося результатом работы процедуры определения собственного числа.
Нам известно число уу только с точностью 2 ~~ ', но также известно, что это рациональное число — отношение двух целых, величина которых ограничена сверху, поэтому если мы сможем вычислить ближайшее к ~р число с такими свойствами, то мы найдем н г. Замечательным образом существует алгоритм, эффективно решающий.эту задачу; он известен под названием алгорипьма цепных дробей. Пример того, как он работает, приведен во вставке 5.3.
Объяснение того, почему этот алгоритм отвечает нашим целям, дает следующая ниже теорема, доказательство которой приведено в Приложении 4. Теорема 5.1. Пусть г(з — такое рациональное число, что ~г ! 2гг (5.48) Тогда зуг является подходящей дробью для ~р и тем самым может быть вычислена за 0(Ьа) операций с помощью алгоритма разложения в цепную дробь. 19 К тн ныл Рис. 5.4. Квантовая схема для алгоритма нахождения порядка На рисунке кубиты второго ре- гистра установлены в состояние )1), но если применить метод упр 5 14, то их можно установить и в состояние )О). Если использовать результаты подразд 5 5 2, то зту схему можно применить и для факторизации. 290 Глава б. Квантовое преобразование Фурье и его приложения Поскольку ~р является приближением для в/г с точностью 2 зь ~, то ]в/т — 1з] < 2 ~~ ' ( 1/2гз, так как т ( А1 < 2~.
Таким образом, теорема в нашем случае применима. Алгоритм цепных дробей эффективно вычисляет такие взаимно-простые числа з' и т', так что з'/г' = з/т. Число т' является нашим кандидатом на то, чтобы быть порядком х. Можно проверить, действительно ли это порядок, вычислив х" шест Ф и посмотрев, получится ли 1. Если получилась 1, то г' является порядком х по модулю А1. Как же все-тааки найти порядокр Вставка 5.3.
Алгоритм цепных дробей Идея алгоритма цепных дробей состоит в том, чтобы представить действи- тельные числа с помощью целых, используя выражения вида 1 [ае,,ам] = ао+ а~+ - — — т— аа+ — г "М (5.49) где ас,..., ам — целые положительные числа. (Применительно к квантовым вычисленинм удобно считать, что ае = 0.) Определим тп-ую (О < т < М) подходяи1ию дробь как [ае,...,'а ]. Алзоритм цепных дробей— это алгоритм для нахождения разложения произвольного действительного числа в цепную дробь. Рассмотрим пример.
Пусть мы хотим представить в виде цепной дроби число 31/13. Первый шаг — выделить в дроби 31/13 целую часть: В каких случаях алгоритм нахождения порядка может дать неверный результат? Для этого имеется две возможности. Во-первых, определение собственного числа может выдать плохое приближение для в/г. Такое случается с вероятностью, не превосходящей з, и эту вероятность можно сделать сколь угодно малой за счет несущественного увеличения размеров схемы.
Более серьезная проблема состоит в том, что у в и т может быть общий множитель, и в этом случае разложение в цепную дробь даст не само число т, а число т', являющееся его делителем. Однако существует не менее трех способов обойти эту проблему. Возможно, самый простой способ — заметить, что для случайно выбранного з Е [О; т — 1] весьма вероятно, что з будет взаимно просто с т, а в этом случае алгоритм цепных дробей выдаст г.
Чтобы повить, почему это так, укажем, что, согласно задаче 4.1 количество простых чисел, меньших г, не менее т/2 1ой т, и тем самым вероятность того, что в просто (и тем самым взаимно просто с г), не менее, чем 1/2 1об т > 1/2 1об Ф. Таким образом, повторив алгоритм 2 1ой Ж раз, можно с высокой вероятностью измерить такую фазу з/т, что в и т взаимно просты, и тогда алгоритм цепных дробей выдаст т, что и требовалось.
5.3. Приложения: нахождение порядка и факторизация 291 31 5 — = 2+ —. 13 13 Обратив дробную часть, получим (5.50) 31 1 =2+ ~з 13 (5.51) Теперь применим ту же операцию (выделение целой части и обращение дробной) к 13/5: =2+ з =2+ 31 1 1 (5.52) 13 213 Далее выделим целую часть и обратим дробную у 5/3: 31 1 1 — =2+ =2+ 13 2 + — -'~ 2 + — ~1~ (5.53) На этом разложение в цепную дробь завершается, поскольку 3 1 — =1+— 2 2 (5.54) может быть записано с единицей в числителе, и обращать дробную часть уже незачем; окончательно разложение 31/13 в цепную дробь имеет вид 31 1 — =2+ 13 2+ —,— (5.55) Ясно, что алгоритм цепных дробей завершается за конечное число шагов для любого рационального числа, так как последовательность числителей (31,5,3, 2, 1 в приведенном здесь примере) является строго убывающей.
Насколько быстро заканчивается этот алгоритм? Оказывается, что если у = э/г — рациональное число, причем э и г являются Ь вЂ” битовыми целыми числами, то разложение <р в цепную дробь можно провести за О(Х з) операций: 0(Ь) операций для выделения целой части и обращения дробной, каждая из которых использует О(Ьз) операций для выполнения арифметических действий. Второй способ состоит в том, чтобы заметить, что если г' ~ т, то г' обязательно будет делителем т (кроме случая, когда э = О, но вероятность этого равна 1/т < 1/2, причем с помощью повторений эту вероятность можно быстро уменьшить). Заменим а на а' = а' (шест И). Тогда порядок а' будет равен г/г'.
Повторим алгоритм и попытаемся посчитать порядок а', если все получится, то мы будем знать и порядок а, поскольку г = г' х г/г'. Если не получится, 292 Глава 5. Квантовое преобразование Фурье и его приложения то в нашем распоряжении будет число т", являющееся делителем т./г', и мы попробуем найти порядок числа а" ы (а')" (пюй И). Будем продолжать эту процедуру, пока порядок а не будет найден.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
