М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 75
Текст из файла (страница 75)
Но и здесь квантовые алгоритмы приходят на помощь: покажите, как с помощью алгоритмов этой главы можно эффективно найти разложение группы С. д'пражнение 5. 28. Выпишите подробное описалие квантового алгоритма, решающего задачу о скрытой подгруппе для конечных абелевых групп; оцените время работы и вероятность успеха.
д'пражнение 5.29. Постройте квантовые алгоритмы, решающие задачи Дойча и Саймона из таблицы на рис. 5.5, руководствуясь решением задачи о скрытой подгруппе. 5.4.4 Возможны ли другие квантовые алгоритмы? Один из наиболее интересных аспектов задачи о скрытой подгруппе состоит в том, что возможно решение и более сложных задач путем рассмотрения различных групп С и функции 7. Мы описали решение задачи только для абелевых групп. Как обстоят дела с неабелеемми группами, которые довольно интересны (см.
Приложение 2 по поводу преобразования Фурье на неабелевых группах)? Например, задача об пломорфизма графов состоит в том, станут ли два данных графа одинаковыми после какой-нибудь из перестановок вершин (см. подразд. 3.2.3). Эти перестановки можно рассматривать как элементы симметрической группы Я„, и существуют алгоритмы для вычисления быстрого преобразования Фурье на таких группах. Однако квантовый алгоритм, эффективно решающий задачу об изоморфизме графов, пока неизвестен. 306 Глава 5. Квантовое преобразование Фурье и его приложения Хотя квантовые алгоритмы для решения более общих случаев задачи о скрытой подгруппе пока не найдены, полезным оказывается уже наличие общего подхода, поскольку он позволяет ставить вопросы о том, как выйти за его пределы. Слабо верится, что все быстрые квантовые алгоритмы, которые будут когда-либо открыты, окажутся лишь частными случаями решения задачи о скрытой подгруппе.
Если считать, что решение задачи о скрытой подгруппе основано на инвариантности преобразования Фурье, то, возможно, в поисках новых алгоритмов стоило бы исследовать другие преобразования, обладающие другими свойствами инвариантности. Рассуждая в ином направлении, можно спросить: какие трудные задачи о скрытой подгруппе можно решить, если разрешается воспользоваться некоторым произвольным (но заданным независимо от задачи) квантовым состоянием? В конце концов в гл. 4 мы выяснили, что большинство квантовых состояний обладает тем свойством, что построить их— экспоненциально трудная задача. Такое состояние могло бы стать полезным ресурсом (вонстнну еквантовым оракулом»!), если бы существовали квантовые алгоритмы, которые могли его использовать для решения трудных задач.
Задача о скрытой подгруппе демонстрирует также важное ограничение, за пределы которого квантовые алгоритмы, дающие экспоненциальное ускорение по сравнению со своими (известнымн на данный момент) классическими аналогами, не выходят: эта задача имеет следующий вид: снам заранее известно, что Р(Х) обладает таким-то свойством; охарактеризуйте его».
Возможно, это звучит разочаровывающе, но в конце следующей главы мы покажем, что при решении задач без таких дополнительных условий квантовые компьютеры не ыогртп дать экспоненциального ускорения по сравнению с классическими; лучшее возможное ускорение полиномиальное. В то же время, это обстоятельство указывает, для задач какого рода квантовые компьютеры могут быть полезны: задним числом оказывается, что задача о скрытой подгруппе — естественный кандидат на применение квантовых вычислений. А какие еще имеются естественные задачи такого рода? Подумайте! Задача 5.1. Постройте квантовую схему, вычисляюшую квантовое преобразование Фурье )я — + — у е 'у ~р!!е), 1 р-е (5.79) 4ра=о где р — простое число.
Задача 5.2 (измеряемое квантовое преобразование Фурье). Предположим, что квантовое преобразование Фурье производится на последнем шаге квантового вычисления, а затем выполняется измерение в вычислительном базисе. Покажите, что эту комбинацию квантового преобразования Фурье н измерения можно реализовать с помощью схемы, состоящей только из однокубитовых элементов н измерителей, с классическими условными операциями. (Используйте результаты обсуждения в равд. 4.4.) 4 Здесь имеются в виду только алгоритмы, применимые к функциям, заданным оракула ми (или черными ящиками) — Прим. ред. 5.4.
Общие приложения квантового преобразования Фурье 307 Задача 5.3 (алгоритм Китаева). Рассмотрим квантовую схему !О) 1и) здесь |и) — собственный вектор оператора У с собственным числом е~"'"'. Покажите, что верхний кубит дает при измерении ~0) с вероятностью р гя сов~(~пр). Поскольку состояние !и) не меняется в результате работы схемы, им можно воспользоваться повторно; покажите, что если заменить У на У~, где Й вЂ” подходящее целое число, то, повторяя это вычисление нужное число раз, можно найти с произвольной точностью р, а значит и ~р. Это — еще один способ определения собственного числа.
Задача 5.4. Приведенная нами оценка 0(ьз) для трудоемкости алгоритма факторизации не является точной. Покажите, что можно осуществить факторизацию за 0(Ь~!об Ь 1об 1об Ь) операций. Задача 5.5 (иеабелева задача о скрытой подгруппе (для исследования). Пусть ) — функция из конечной группы 0 в произвольное конечное множество Х, о которой известно, что она постоянна на левых смежных классах по некоторой подгруппе К С О, причем на разных смежных классах она принимает разные значения.
Начните с состояния (5.80) и покажите, что при тп = 4 1оя ~0~+ 2 подгруппа К может быть однозначно восстановлена с вероятностью, не меныпей 1-1/~0). Обратите внимание на то, что 0 не предполагается абелевой и не имеехся в виду проводить преобразование Фурье. Этот результат показывает, что, используя 0(1оя ~0~) обращений к оракулу, можно получить результат, в котором чистые состояния, соответствующие различным возможным скрытым подгруппам, почти ортогональны. Тем не менее неизвестно, существует ли РОУМ, позволяющий найти скрытую подгруппу эффсатппвно (т. е. за ро1у(1об ~0~) операций) исходя из этого конечного состояния.
Задача 5.6 (сложение с помощью преобразования Фурье). Пусть требуется построить квантовую схему, выполняющую вычисление ~х) -+ ~х+ у пюд 2"), где у — фиксированная константа и 0 < х < 2". Покажите, что при у = 1 это можно эффективно сделать следующим образом: провести квантовое преобразование Фурье, применить однокубитовые сдвиги фазы, а затем выполнить обратное преобразование Фурье.
Для каких еще значений у такой метод эффективен? Сколько при этом требуется операций? 308 Глава 5. Квантовое преобразование Фурье и его приложения Краткое содержание главы ° При М = 2" квантовое преобразование Фурье (5.81) может быть записано в виде (д) + (~0) + еэт10 1„~1)) (~0) + самс ь'-м ~ц) 1 х (10) + еэ"'с Ь~'"'1" (1)) (5.82) и реализовано с помощью 9(п~) элементов. ° Определение собственного числа. Пусть ~и) — собственный вектор оператора ХХ с собственным числом ез~'т.
Процедура определения собственного числа (см. рис. 5.3), начиная с состояния )0)е'(и), может эффективно найти состояние ~ф))н), где ~р с вероятностью не менее (1 — с) аппроксимирует ~о с точностью 2 '+('к (~+ эг)); все это верно в предположении, что возможно эффективно реализовывать оператор Уэ для целых Ь. ° Нахождение порядка. Порядок числа х по модулю Ж вЂ” это наименьшее целое положительное число г, для которого х" шод М = 1.
Это число можно найти за О(Х~) операций с помощью квантовой процедуры определения собственного числа, если х и Ф вЂ” Х битовые целые числа. ° Факторизация: Простые сомножителя Х битового целого числа М могут быть найдены за 0(Х з) операций путем сведении этой задачи к нахождению порядка случайного числа х, взаимно простого с Ф. ° Задача о скрытой подгруппе: Все известные быстрые квантовые алгоритмы можно рассматривать как частные случаи следующей задачи.
Пусть Х вЂ” функция из конечно порожденной группы С в конечное множество Х, обладающая тем свойством, что она постоянна на смежных классах по некоторой подгруппе К с С и принимает разные значения на разных смежных классах. Дан квантовый черный ящик, выполняющий унитарное преобразование У~д))Ь) = ~д)~Ь ® Х(д)), где д е С, Ь е Х. Найдите множество образующих для К. 5.4.
Общие приложения квантового преобразования Фурье 309 История и дополнительная литература Можно дать более общее определение преобразования Фурье, чем то, которым мы пользовались в этой главе. Общее преобразование Фурье определено на множестве последовательностей комплексных чисел (ая), где индекс д пробегает элементы некоторой группы С. В этой главе в качестве С выступала адцитивная группа целых чисел по модулю 2", часто обозначаемая через Еэ . Дойч [117] показал, что на квантовом компьютере можно эффективно реализовать преобразование Фурье на группе Еэ" — это не что иное, как преобразование Адамара.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
