М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 74
Текст из файла (страница 74)
Алгоритм: дискретный логарифм Вход: 1) черный ящик, осуществляющий операцию У(х~) 1хг) 1у) = )хг) 1хг) 1у ® Дхмхг)), где Дхмхг) = Ь*'а*', 2) регистр для значений функции, кубиты 5.4. Общие приложения квантового преобразования Фурье 301 которого установлены в состояние (О); 3) два 2 = 0( (1об т ) + 1об(1/с) )-кубитовых регистра, установленных в ~0). Выход: Наименьшее положительное число э, для которого верно равенство а' = 6. Время выполнения: одно обращение к У плюс О((!об т) 2) операций. Вероятность успеха Й(1). Процедура: 1. !О)!О)!О) Начальное состояние 1 2'-1 2'-1 2. —, ~ ~ ~*,)~хг)!0) ,=о ,=о 1 2'-1 2~-1 3. -+ — ~ ~~~ ~х1) ~хг) ~/(х1, хг)) Применить У ,=о ,=о т-1 2'-1 2'-1 = —,' Е Е Е "-Ц"*'"*""~*)~*.И",4.)) 21 /Т Создать суперпозицию г, о,-о., о т-1 2'-1 — е Ц' '*Вдох ~~Х1 — яс,~ г г,=о *,=о Т-1 2'-1 Е 112* >I ~х ) т2=0 ~У(Фгю ~2)) '4.
— + — ~ (ЗЙ2/Т)~К2/Т)~1/(382 42)) г,=с 5. — ~ ( эсг/т, 12/т) Применить обратное преобразование Фурье к двум первым регистрам Измерить два первых регистра Применить обобщенный алгоритм цепных дробей Опять основным является шаг 3, на котором вводится состояние т-1 ~/(1~,12)) = — ~~~ е ' '17"~/(0,у)), (5.70) являющееся преобразованием Фурье от ~/(х1,хг)) (см. упр. 5.22). В этом ра- венстве значения 11 и 12 должны удовлетворять условию Т вЂ” 1 Е ег 1"11'7' 2*17" = о=о (5.71) т-1 Т-1 т-1 (/(р г )) — ~~~ ' '~~ е 2' 1<1 * +12' 2>1'~/(х1,хг)) = — ~е гкт 17 Щ0,1)) ,=о*,=о 1=О (5.72) Иными словами, амплитуда )/(11, 12)) близка к нулю.
Обобщенное разложение в цепную дробь, используемое на последнем шаге для нахождения э, аналогично процедурам из подразд. 5.3.1; его построение оставим читателю в качестве простого упражнения. з'пражнение 5.22. Покажите, что 302 Глава 5. Квантовое преобразование Фурье и его приложения и что зто выражение отлично от нуля только тогда, когда де/г — дг — целое число, делящееся на г.
Упражнение 5.23. Вычислите 1 1-1 х-1 е-~м(е х +е2 д1 /(е е )) г е,=се,=о (5.73) с использованием (5.70) и покажите, что ответ равен /(хп хг). Упражнение 5.24. Разработайте алгоритм обобщенных цепных дробей, используемый на шаге 6 алгоритма дискретного логарифмирования для восстановления г по приближенным значениям длл гег/г и дг/г. Упражнение 5.25. Постройте квантовую схему, реализующую черный ящиК У, используемый в квантовом алгоритме дискретного логарифмирова. ния: этот оператор зависит от параметров а и Ь, и он выполняет унитарное преобразование (хе ) (хг) (у) — ~ )х1 ) (хг) )у Ю Ь*'а*'). Сколько элементарных операций для этого нужно? Пусть / — функция из конечно порожденной группы 0 в конечное множество Х, постоянная на смежных классах по некоторой подгруппе К и принимающая различные значения на разных смежных классах.
Пусть дан квантовый черный ящик, выполняющий унитарное преобразование ЦдЯЬ) = (д) )Ь Ю /(д)), где д б О, Ь Е Н и ®вЂ” некоторая подходящая бинарная операция на Х. Найти множество образующих группы К. Задача нахождения порядка и периода, дискретное логарифмирование и многие другие задачи — частные случаи этой задачи, называемой зада уей о схрье гаой подгруппе; некоторые другие интересные частные случаи представлены на рис. 5.5. Если С вЂ” коночная абглееа группо„то квантовый компьютер может решить задачу о скрытой подгруппе за полиномиальное по 1об ~С) количество операций, воспользовавшись одним обращением к черному ящику, с помощью алгоритма, очень похожего на другие алгоритмы, рассматриваемые в этом разделе.
(На самом деле аналогичный метод работает и для конечно порожденных абелевых групп, но мы ограничимся конечным случаем.) Предложим читателю подробно описать алгоритм в качестве упражнения: после объяснения основной идеи, 5.4.3 Задача о скрытой подгруппе Теперь общий принцип должен быть ясен: если дана периодическая функция (при этом периодичность может быть достаточно сложной), то часто можно воспользоваться квантовым алгоритмом для эффективного нахождения периода. Важно, однако, отметить, что ие все периоды могут быть найдены. Задача, являющаяся широким обобщением всех задач такого рода, может быть коротко сформулирована в терминах теории групп (см. краткий обзор в Приложении 2) следующим образом: 5.4.
Общие приложения квантового преобразования Фурье 303 сделать это будет легкое. Многие детали в нашем алгоритме практически не будут отличаться от предыдущих алгоритмов, поскольку конечные абелевы группы изоморфны произведениям вддитивных групп остатков. Это означает, что определено квантовое преобразование Фурье функции у на группе С (см. равд. А2.3) и это преобразование по-прежнему может быть выполнено эффективно. Первый нетривиальный шаг алгоритма — провести преобразование Фурье (обобщающее операцию Адамара) и создать суперпозицию по элементам группы; затем с помощью черного ящика для у это состояние преобразуется в еле,нующее: — ~ !д)йд)) ~~~!,.а (5.74) Как и раньше, теперь наша цель — переписать |Дд)) в базисе Фурье.
Начнем с того, что напишем формулу ~с!-1 )у(д)) = ~~~ е ' ад ~/у(а)), ~/!С1 ь е (5.75) где ехр( — 2нИд//С!) — значение в точке д Е С представления (см. упр. А2.13) группы С, под номером а (преобразование Фурье переводит функции на группе в функции на множестве ее неприводимых представлений — см.
упр. А2. 23) . Теперь заметим, что это выражение можно упростить, поскольку 7 постоянна на смежных классах и принимает на разных классах разные значения; получим, !де)) = ~~~ е кмедп~/~(д)) /Г~ „ (5.76) имеет амплитуду, близкую к нулю, для всех е, кроме тех, которые удовлетворяют условию -жамма/щ !К! (5.77) век з Читатель должен иметь в виду, что изложение в этом разделе крайне неформально— Прим.
ред. Если можно определить с, то с помощью линейных ограничений, налагаемых этим условием, можно найти элементы группы К, а так как К абелева, зто позволит в конечном счете найти множество образующих для всей скрытой подгруппы, т. е. решить нашу задачу. Жизнь, однако, ие столь проста. Важной причиной того, почему эффективны алгоритмы нахождения порядка и дискретного логарифмирования, является то обстоятельство, что возможно применение цепных дробей для восстановления а из д/!С!. Эти задачи таковы, что с высокой вероятностью а и !С! будут взаимно просты. В общем случае, однако, это не обязано быть верным: )С! может быть составным числом со многими делителями, и у нас нет никакой информации априорй относительно А 304 Глава 5.
Квантовое преобразование Фурье и его приложения К Функция Х Название (О) или (О, 1) (о ц (О, 1), ® Задача Дойча (О, 1)п, цт (О, з) з ~ (О,Ц" Произ- вольное Задача Саймона (О, т,2т,...) Дх+ т) = Дх) т ц 1У Произ- вольное Нахождение периода Е+ конечное множе- ство (О,т,2т„..) у(х) = а* у(х+ т) = у(х) Е,+ Нахождение порядка (ау ) д б Ег (д, -4з) Е, еЕ„ Е„х Е, +(пюс) т) Дискретный логарифм а" =1 (О,т,2т,...) Дх,у) = и (у) г Е Х у(х+т,у) = у(х,у) Ег-, х Ег..
+(пюс)2 ) я = перестановка множества Х (Н,Х) у(дЬ,х) = у(д,у(й,х)) Ддз, х) = у (д, х) Абелев ста- билизатор Произ- вольное конечное множе- группа ство Рис. 5.5. Частные случаи задачи о скрытой подгруппе. Функция У отображает группу б' в конечное множество Х; известно, что она постоянна на смежных классах по подгруппе К С С. В атой таблице Ен обозначает множество (0,1,,1т' — 1), а Š— множество целых чисел. Задача состоит в том, чтобы найти подгруппу К (или ее множество образующих), если задан черный ящик для у.
Порядок переста- новки Скрытая линейная функция Н = про- извольная абелева конечное множе- ство (ау) Я о Ег а' = 1 (з б Н ~ у(з,х) =х, 'тх б Х) К = (О, 1): ()'(х) = 1 К = (0): ' (у(х) = 1 — х ДхЕЭ з) = у(х) ) (х1, хг) = а"*'+*' у(х, +д,х,-Ь) = у(хг,хг) у (хм хг) = я(зхг + хг пюд Л) я = перестановка множества Х 5.4. Общие приложения квантового преобразования Фурье 305 Однако эта проблема разрешима: как отмечалось выше, всякая конечная абелева группа является произведением циклических групп, порядки которых являются степенями простых чисел, т. е.
С = Ер, х Ер, х ... Ер,, где р,— степени простых чисел, а Ер, — группа, состоящая из элементов (О, 1,..., р; — 1) с групповой операцией — сложением по модулю р;. Тогда можно переписать фазу из формулы (5.75) в виде м з~гиддо! П~' з~г11;'д./р< (5.78) где д; е Ер, Определение собственного числа даст 4';, исходя из этого можно найти 4, а тем самым и элемент подгруппы К, как было описано выше, т. е. решить задачу о скрытой подгруппе. д'пражнение 5.26. Пусть К является такой подгруппой в С, для которой разложение С в произведение циклических групп индуцирует аналогичное разложение и для К. С помощью формулы (5.77) покажите, что определив 4;', можно найти элемент из соответствующей циклической подгруппы Кр, С К, д'пражнение 5.27. Конечно, разложение произвольной конечной абелевой группы С на произведение циклических групп, порядки которых равны степеням простых чисел, является трудной задачей (не менее трудной, чем, например, факторизация).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
