М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 73
Текст из файла (страница 73)
В начале выберем случайное число, взаимно простое с М; предположим, мы выбрали х = 7. Теперь вычислим г — порядок х по модулю Р7 — с помощью квантового алгоритма: начнем с состояния )0) (0) и создадим состояние г'-1 — /Й))0) = — ~!О) + )1) + !2) + ° )2' — 1)1 !0), ~(2,, ~/2 (5.61) применяя 8 = 11 преобразований Адамара к первому регистру. При вы- боре этого значения 4 вероятность ошибки, обозначаемая с, не будет пре- вышать 1/4.
Затем вычислим ДЙ) = х" (шобМ) и оставим результат во втором регистре: г'-г — )Й))х" шоб 17) (5.62) ч'2' = — [/0)!1) + !1)/7) + !2)/4))3)/13) + 14)!13) + )4)!1) + )5)!7) + )6)/4) + . .1. Теперь применим обратное преобразование Фурье РТ1 к первому регистру и измерим его. Один из возможных способов изучить распределение результатов — вычислить редуцированную матрипу плотности для первого регистра, применить к ней РТ1 и найти статистику измерений. Однако поскольку никаких дальнейших операций со вторым регистром производиться не будет, вместо этого можно применить принцип неявного измерения (равд. 4.4) и принять, что второй регистр измеряется, причем получается слрчайнья1 результат: 1, 7, 4 или 13.
Пусть вышло 4 (подошел бы и любой другой результат); это означает, что на вход оператору РТ1 подается ~/ф 02) + )6) + 110) + )14) +...). Применив РТ~, получим некоторое состояние 2 ~ сч(Ц (на рисунке показано распределение вероятностей для 2' = 2048). з пражнение 5.19.,Покажите, что М = 15 — наименьшее число, для которого при разложении на множители по описанному алгоритму требуется нахожде- ние порядка (т.
е. наименьшее составное число, не являющееся ни четным, ни степенью меньшего числа). 5.4. Общие приложения квантового преобразования Фурье 297 0.25 0.2 н ОЗ5 оа 0.05 Таким образом, заключительное измерение дает О, 512, 1024 или 1536 (каждый результат — с вероятностью 1/4). Пусть мы получили 1 = 1536; разложив в цепную дробь, имеем 1536/2048 = 1/(1+ (1/3)), так что 3/4 является подходящей дробью в разложении, откуда т = 4 является порядком числа х = 7. Удачным образом оказывается, что т четно, и более того, х"?2 пюй И = 72 пюд 15 = 4 55 — 1 (пюд 15), так что алгоритм успешно сработал: вычисляя наибольшие общие делители НОД(хг — 1, 15) = 3 и НОД(хг + 1, 15) = 5, получим, что 15 = 3 х 5. 5.4 Общие приложения квантового преобразования Фурье Основные приложения квантового преобразования Фурье, описанные выше,— определение собственного числа и нахождение порядка.
Какие еще задачи можно решить таким образом? В этом разделе мы сформулируем общую задачу, известную как задача о скрып»ой подгруппе, и опишем эффективный квантовый алгоритм ее решения. Эта задача, включающая все известные гэкспоненциально быстрые» приложения квантового преобразования Фурье, может рассматриваться как обобщение задачи о нахождении неизвестного периода периодической функции в ситуации, когда область определения и множество значений функции очень сложные. Чтобы представить эту задачу в более доступной форме, начнем изложение с двух частных приложений: нахождения периода (у одномерной функции) и вычисления дискретного логарифма, а затем вернемся к общей задаче о скрытой подгруппе.
Материал в этом разделе представлен более сжато, чем в начальных разделах главы, а это означает, что читатель, желающий вникнуть во все детали, должен будет приложить больше усилий. 5.4.1 Нахождение периода Рассмотрим следующую задачу. Пусть / — периодическая функция, значения которой 0 и 1, удовлетворяющая условию /(х+ т) = /(х) для некоторого неизвестного т, (О < т < 2"), где х,т Е (0,1,2,...). Если дан квантовый черный ящик У, выполняющий унитарную операцию 57(х) (у) » )х) (уй/(х)) (здесь ®вЂ” 298 Глава 5.
Квантовое преобразование Фурье и его приложения сложение по модулю 2), то сколько обращений к этому черному ящику и прочих операций слепует сделать для нахождения ту Заметим, что на практике У действуег на конечном множестве, размер которого определяется точностью, с которой надо определить т. Приведем квантовый алгоритм, находящий т за один запрос и 0(Ьг) других операций.
Алгоритм: нахождение периода Вход: 1) черный ящик, выполняющий операцию Цх))р) -т )х))у Ю/(х)); 2) ре- гистр, в который будут записываться значения функции, его кубиты установ- лены в состояние )О); 3) Е = 0(Ь + !о8(1/с)) кубитов в состоянии )О). Выход: наименьшее целое т ) О, для которого верно тождество /(х+ т) = /(х). Время выполнения: одно использование У и 0(Е~) операций; вероят- ность успеха Й(1), Процедура: 1. )0))0) Начальное состояние 1 г'-1 2. — т — ~ )х))0) 1/2,', 3.
-+ — ~ )х))/(х)) 1 г'-1 1/21 о Применить У т-1 г -1 — ег еы/" (х))/())) 1=от о т-1 4. — ', '')Е/т)!/Ж) ~/ е-о 5. е/т 6. -+ т Создать суперпозицию Применить обратное преобразование Фурье к первому регистру Измерить первый регистр Применить алгоритм цепных дробей т-1 )/(Ю)) ш — ) е ~' /т)/(х)), я=о (5.63) являющееся преобразованием Фурье от )/(х)). Тождество, использованное в шаге 3, основано на равенстве т-\ ~/(х)) = — Е "ее*'"йв* е=о (5.64) котоРое легко пРовеРить, если заыетить, что сУмма 2 е „ег™/' Равна т, если х делится на т, и нулю в противном случае.
Знак приближенного равенства на Основным в этом алгоритме, основанном на определении собственного числа и очень похожем на квантовый алгоритм нахождения порядка, является шаг 3, на котором мы вводим состояние 5.4. Общие приложения квантового преобразования Фурье 299 шаге 3 стоит потому, что, вообще говоря, 2' не обязано делиться на г (эта возможность учитывается процедурой определения собственного числа). С учетом формулы (5.22) применение обратного преобразования Фурье к первому регистру на шаге 4 дает оценку фазы 4/г, где 4 выбирается случайно.
Число т находится на последнем шаге с помощью цепных дробей. Вставка 5.5. Инвариантность преобразования Фурье относительно сдвигов Преобразование Фурье (5.1) обладает интересным и полезным свойством, известным как инвариантносшь относительно сдвигое. Запишем квантовое преобразование Фурье в виде аЬ |й) — ~~~ ад )д), (5.65) деп ЬеН где ад — — ~ ьен сгь ехр(2хгдй/~С~), Н вЂ” подмножество в С, а С вЂ” множество индексов, нумерующих состояния из некоторого ортонормальиого базиса в гильбертовом пространстве (например, для п-кубитовой системы С может быть множеством чисел от О до 2" — 1), а 1С~ — число элементов в С. Предположим, мы применили к начальному состоянию унитарный оператор Уь, действующий по формуле (5.66) (?ЬЫ = Ь+ й), а затем — преобразование Фурье. Полученный результат Нь ~~~ аь(й) = ~~~ аь)й+ й) -+ ~~~ ег гд~д~~ад)д) (5.67) ЬеН Лел деп обладает тем свойством, что абсолютные величины амплитуд состояний ~д) не меняются, каким бы ни было й: ~ ехр(2ягдй/)С~)ад) = 1йд!.
На языке теории групп С вЂ” это группа, Н вЂ” ее подгруппа, а утверждение состоит в том, что если функция / постоянна на смежных классах по Н, то и ее преобразование Фурье инвариантно относительно Н. Почему же этот алгоритм работает? Можно, например, рассмотреть (5.63) как преобразование Фурье функции ~/(х)) на множестве (О, 1,...,2г — 1) (см. упр. 5.20); это преобразование Фурье обладает интересным свойством, называемым инварнантностью относительно сдеигое, описанным во вставке 5.5.
Другой способ понять, на чем основан этот алгоритм, — заметить, что алгоритм нахождения порядка определяет период функции /(й) = х" шод Н, так что не удивительно, что аналогичным методом можно найти период и произвольной функции. Еще один способ — заметить, что черный ящик У естественным образом реализуется с помощью унитарного оператора, собственные числа ко- 300 Глава 5.
Квантовое преобразование Фурье и его приложения торого как рвз равны ( т(в)) (см. упр. 5.21), так что можно применить процедуру определения собственного числа из равд. 5.2. 'Упражнение 5.20. Пусть у(х+т) = Дх) и 0 < х ( И, где Ж вЂ” целое кратное числа т. Вычислите (5.68) и сравните свой результат с (5.65). Вам понадобится тот факт, что (5 69) ) 0 иначе. ье(е,агт,,тт-т1 Упражнение 5.21 (иахождение периода и определение собственного числа).
Пусть дан унитарный оператор Пю осуществляющий преобразование Ув1у(х)) = 1у(х + у)) для описанной выше периодической функции. 1. Покажите, что собственными векторами этого оператора являются 17(1)) и найдите их собственные числа. 2. Покажите, что в предположении, что дано 11(хс)) для некоторого хс, с помощью оператора Ув можно реализовать черный ящик, который можно использовать для нахождения периода.
5.4.2 Дискретный логарифм Задача нахождения периода, которую мы только что рассмотрели, проста в том отношении, что функция отображала целые числа в целые числа. Что происходит с более сложными функциями? Рассмотрим функцию Дхм хг) = а'*'+*' шод Л (переменные — целые числа), и пусть т — порядок х по модулю Ж. Эта функция периодическая, поскольку 1(х~ +1, хг — 1в) = ~(хм хг) для целых 1, но здесь периоды — это пары целых чисел (1, — 1в).
Эта функция производит странное впечатление, но она очень полезна в криптографии, поскольку нахождение в позволяет решить задачу, известную как задача о дискретном логарифме: даны а и Ь = а', чему равно в? Ниже приводится квантовый алгоритм, решающий эту задачу за одно обращение к черному ящику П, осуществляющему унитарное преобразование Цх~) 1хг)(у) = 1хг) 1хг) 1у Ю У(Х)) (где Ю— побитовое сложение по модулю 2) и 0(11о8 т1г) других операций. Мы предполагаем, что число т (порядок а по мОдулю И) уже найдено с помощью алгоритма нахождения порядка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
