М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 70
Текст из файла (страница 70)
5.3. Общая схема процедуры определения собственного числа Верхние 1 кубитов (символ « / » обозначает, как обычно, набор проводов) образуют первый регистр, нижние кубиты (в количестве, необходимом для того, чтобы применить У) — второй регистр (и) — зто собственный вектор оператора У с собственным числом егкаи. Результат измерения — прибли- 11 женное значение для Р с точностью 2 л, где А = с — ~ !ой (2+ — ) ~, и с вероятностью успеха 2е не менее (1 — е). Итак, процедура определения собственного числа позволяет оценить фазу ьг собственного числа унитарного оператора У при условии, что дан соответствующий собственный вектор (и). Существенной частью процедуры является возможность применить обратное преобразование Фурье г'-1 —,~т ~~ Е ' (2)(н) — ((о)!и), у=с (5.22) где )Ф) — состояние, дающее хорошую оценку для ву при измерении.
5.2.1 Оценка скорости работы и вероятности ошибки Приведенный выше анализ относится к идеальному случаю, когда ~р может быть точно записано в виде 1-битовой двоичной дроби. Что будет, если это условие не выполнено? Оказывается, описанная нами процедура с высокой вероятностью даст хорошее приближение для ~р (на что и указывали обозначения в (5.22)). Доказательство этого утверждения требует известной аккуратности. Пусть Ь вЂ” такое целое число из интервала [О; 2' — Ц, что Ь/2' = О.Ь1... Ьз есть 1-битовое приближение для (р снизу.
Это означает, что разность 6 щ ~р — Ь/2' из предыдущего раздела (упр. 5.5), и это достигается за 9(сг) шагов. Третий и заключительный этап — найти состояние первого регистра с помощью измерения в вычислительном базисе. Покажем, что при этом получается очень хорошая оценка для (р. Общая схема процедуры представлена на рис. 5.3. Чтобы понять, почему процедура определения собственного числа работает, предположим, что ~р можно рзочмс записать с использованием 1 битов: 1р = 0.(р1...
ьгм Тогда состояние (5.20), получаемое в конце первого этапа работы процедуры, можно переписать в виде 5.2. Определение собственного числа 283 г'-1 — еет ег 1""(1). 21 Ь,)=о (5.23) Пусть а( — амплитуда )(Ь+ () шоб 2'): г'-1 /г — ( ге(ьг-(Ь+1)/гг)) а(= —,~ ~е а=с (5.24) Это — сумма геометрической прогрессии, так что имеем < гее(гг, -(Ь+1)) ') еге((т-(ь+0/гг) ) ' < гггг(гг6-0 ~ Егег(6-1/г') 1 а( =— 2' (5.25) (5.26) Предположим, что результат заключительного измерения есть т.
Оценим ве- роятность получения такого значения т, что )т-Ь( > е, где е — положительное число, характеризующее допустимую ошибку. Вероятность наблюдения тако- го т равна р((т — ь| > е) = ~~ (а()~+ ~ (а()~. (5.27) -гг-г<1~<-(е+1) е+1<1<г' — г Однако для любого действительного д имеем )1 — ехр(гд) ~ < 2, откуда 2 ! ! ~ 21)1 еге1(6-1/гг))' (5.28) Из элементарной геометрии или анализа следует, что )1 — ехр(18) ) > 2)д)/ я при — я < О < х. Однако при — 2' 1 < ( < 2' 1 имеем -я < 2я(5 — 1/21) < я. Тогда можно записать 1 21+1(5 1(21) ' (5.29) Сопоставив (5.27) и (5.29), получим р((т — Ь) > е) <— 1 — (е+1) 1 1 г'-' Е (1 215)г + Е (1 215)г (5.30) удовлетворяет условию 0 < 5 < 2 '.
Наша цель — показать, что в результате измерения в конце процедуры получится результат, близкий к Ь, что и дает с высокой вероятностью хорошую оценку для гр. Применяя обратное преобразование Фурье к состоянию (5.20), получим со- стояние 284 Глава 5. Квантовое преобразование Фурье и его приложения Поскольку 0 < 2'б < 1, имеем — (е+1) 1 1 зф-1 Е 1з ~Х~, (1 Цз 1 р()гп — Ь! ) е) <— 4 ~ (5.31) г'-'-~ 1 1 < — ~'— 2 (з [=е з$1 < — ! и— 2! ~ (з 1 2(е — 1) (5.32) (5.33) (5.34) Предположим теперь, что надо аппроксимировать у с точностью 2 ", т.
е. что е = 2' " — 1. Если мы будем в процедуре определения собственного числа использовать Ь = и+р кубитов, то из (5.34) сле,эует, что вероятность получения приближения с такой точностью равна как минимум 1 — 1/2(2г — 2). Тогда для того, чтобы с вероятностью не менее 1 — е получить значение ~р с точностью 2 ", выберем 1= и+ 1о8 2+— (5.35) Чтобы можно было воспользоваться процедурой определения собственного числа, необходимо уметь приготавливать состояние ~и) — собственный вектор оператора У.
Как быть, если приготовить такое состояние мы не можем? Предположим, что вместо ~и) мы приготовили какое-то состояние (ф). Разложение ~ф) по собственным векторам оператора У имеет вид ~ф) = ,'> „с„~и). Пусть собственному вектору ~п) соответствует собственное число е~ '~". Интуитивно ясно, что в результате работы процедуры определения собственного числа получится состояние, близкое к 2 „~у„) ~и), где (Д) — хорошее приближенное значение для фазы <р„. Следовательно, можно ожидать, что результат считывания первого регистра даст хорошее приближение к ~р„, где и выбирается случайно с вероятностью ~с„~з.
(Строгое проведение этого рассуждения— предмет упражнения 5.8.) Описанный прием позволяет обойтись без приготовления (возможно, неизвестного) собственного вектора за счет добавления фактора случайности в работу алгоритма. Упражнение 5.8. Пусть процедура определения собственного числа переводит состояние )0))и) в состояние рЬ„)(и), так что )О)( „с„)и)) переводится в ,'> „с„)ф„) (и).
Покажите, что если $ выбрало в соответствии с (5.35), то вероятность измерения у„с точностью 2 " не менее (с„~~(1 — е). Чем интересна процедура определения собственного числа? Она представляет интерес и сама по себе, поскольку решает нетривиальную и физически интересную задачу: как оценить собственное число, соответствующее данному собственному вектору унитарного оператора. Реальная польза от этой процедуры, однако, состоит в том, что другие интересные задачи могут, как мы уви- 5.3. Приложения нахождение порядка и факторизация 285 дим в следующих разделах, быть сведены к определению собственного числа. Запишем еще раз процедуру в целом.
Алгоритм: квантовое определение собственного числа Вход: 1) черный ящик, выполняющий операции «управляемое Уг» для целых г; 2) ~и) — собственный вектор оператора У с собственным числом ег ет"; 3) 1= п+ !о8 2+ — ! кубитов в состоянии )О). 2в) Выход: число у„, являющееся и-битовой аппроксимацией к со„. Время выполнения: 0(г~) операций и одно обращение к черному ящику, выполняющему операцию «управляемое Г' ». Вероятность успеха не менее 1 — в. Процедура: 1. !О)/и) Начальное состояние г'-1 2. -+ — 1, 2 (Я)и) г у=о ге-1 3. -+ -ф ~ Ц)5Гг~и) Обращение к черному ящику г=о г'-1 ег Пт" ~Я~и) Результат работы черного ящика 4.
-» (у„)!и) Быстрое преобразование Фурье 5. -+ гг,, Измерение первого регистра Упражнение 5.9. Пусть П вЂ” унитарное преобразование с собственными числами х1, действующее на состояние )ер). Пользуясь процедурой определения собственного числа, постройте квантовую схему, переводящую ~ер) в одно из двух собственных подпространствг для П и при этом информирующую (классическим образом), в какое из этих надпространств мы попали. Сравните полученный результат с упр. 4.34.
Создание суперпозиции Ссствегсгвуювгих ссбствеииым числам 1 или -1 — Прим иерее 5.3 Приложения: нахождение порядка и факторизация С помощью процедуры определения собственного числа можно решить множество задач. Рассмотрим две наиболее интересные из них: задачу нахождения аорядка и задачу фактпоризации целого числа. На самом деле эти две задачи эквивалентны, так что в подрэзд.
5.3.1 мы приведем квантовый алгоритм, решающий задачу нахождения порядка, а затем в подразд. 5.3.2 объясним, как, умея находить порядок, можно разлагать числа на простые множители. Для понимания квантовых алгоритмов факторизации и нахождения порядка требуются некоторые знания из теории чисел. Весь необходимый материал собран в Приложении 4. Описание алгоритмов в двух следующих подразделах концентрируется на квантовых аспектах задачи, и для его понимания достаточно начальных знаний арифметики остатков по модулю и. Подробные до- 286 Глава 5.
Квантовое преобразование Фурье и его приложения казательства используемых нами теоретико-числовых результатов собраны в Приложении 4. Быстрые квантовые алгоритмы для нахождения порядка и факторизации интересны по меньшей мере по трем причинам. Во-первых (и в главном, по нашему мнению), наличие этих алгоритмов является свидетельством того, что квантовые компьютеры по сути своей более эффективны, чем классические, что ставит под серьезное сомнение усиленный тезис Черча-Тьюринга.
Во-вторых, обе задачи достаточно интересны сами по себе, чтобы любой новый алгоритм для их решения, будь то классический или квантовый, представлял интерес. В-трегьих (и с практической точки зрения это главное), эффективные алгоритмы для нахождения порядка и факторизации могут быть использованы для взлома криптосистемы ВБА с открытым ключом (см. Приложение 5).
5.3.1 Нахождение порядка Упражнение 5.10. Покажите, что порядок числа х = 5 по модулю Ж = 21 равен 6. Упражнение 5.11. Покажите, что порядок числа х удовлетворяет условию г < Ф. Квантовый алгоритм для нахождения порядка представляет собой просто процедуру определения собственного числа, примененную к унитарному опе- ратору У)у) = (ху(шоб Л)), (5.36) где у Е (О, 1)ь. (Отметим, что здесь и ниже мы полагаем, что ху(щи Ф) = у, если Ф < у < 2~ — 1, так что У нетривиально действует только при О < у < М вЂ” 1.) Простое вычисленйе показывает, что состояния, определенные по формулам 1 " ~ — 2хээй1 (и,) и — ~~> ехр ~ ~ (х шоб И) ь о (5.37) Если х и Ж вЂ” взаимно простые целые числа, причем х < М, то порядком з по модулю И называют наименьшее целое положительное число г, обладающее тем свойством, что х' = 1 (шод Ф).
Задача нахождения порядка состоит в том, что требуется определить этот порядок для данных х и И. Считается, что для классического компьютера эта задача трудна в том смысле, что неизвестен решающий ее алгоритм, количество операций которого попиномиально по Ь, где Ь = (1о8 М1 — число битов, необходимое для задания Ж. В этом подразделе мы объясним, как с помощью определения собственного числа построить эффективный квантовый алгоритм для нахождения порядка. 5.3. Приложения: нахождение порядка и факторизация 287 при 0 < э < г — 1, являются собственными для У, так как «-» ~.)- — 'к- ~ ""'~ »- - ) »=с = ехр 2™ )и»).
(5. 38) (5.39) С помощью процедуры определения собственного числа можно найти с высо- кой точностью соответствующие собственные числа ехр(2х»э/г), откуда после небольшой дополнительной работы можно вычислить и г. Упражнение 5.12. Покажите, что оператор У унитарен. (Указание: числа х и Ф взаимно простые, так что у него есть обратный по модулю 57.) Вставка 5.2.
Возведение в степень по модулю М Как можно вычислить последовательность операций «контролируе- мое Пэ' », используемых при определении собственного числа в алгоритме нахождения порядка? Необходимо вычислить преобразование ИЬ>-! >(7*" ' П""Ь> = (х))х*'э х х х" ~ у(шоб я)) = !з>!х'у(шод 57)). (5.40) (5.41) (5.42) Как можно видеть, вычисление этой последовательности операций «управляемое У~» равносильно умножению содержимого второго регистра на степень х' (шос1 1»'), где г — содержимое первого регистра. Эту процедуру легко реализовать, используя обратимые вычисления. Идея состоит в том, чтобы сначала обратимо вычислить х' (шоб Л) в третьем регистре, а затем обратимо умножить содержимое второго регистра на х' (щи Ж), после чего восстановить исходное состояние третьего регистра с Чтобы можно было применить процедуру определения собственного числа, необходимо выполнить два важных требования: в нашем распоряжении должны быть эффективные способы реализации операций «управляемое Уэ' » для произвольного целого 7' и мы должны уметь эффективно приготавливать состояние ~и») с нетривиальным собственным числом или хотя бы суперпозицию таких состояний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
