М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 72
Текст из файла (страница 72)
Нам может потребоваться не более чем Ъоб г = 0(Ь) итераций, поскольку каждая итерация уменьшает порядок очередного а" по крайней мере вдвое. Третий способ лучше первых двух в том отношении, что в нем используется 0(1) попыток, а не 0(Ь). Необходимо дважды повторить процедуру определения собственного числа с последующим разложением в цепную дробь; обозна. чим найДенные пРи этом числа как т', = г/д( (пеРваЯ попытка) и гз — — т/цз (вторая попытка). Если д', и дз взаимно просты, то т будет равно наименьшему общемУ кРатномУ т', и гз; веРоЯтность же того, что д~ и 9з не взаимно пРосты, равна 1 - ~~ р(9~9()р(49з) ч (5.56) (5.57) Правую часть можно оценить снизу многими разными способами; например простой способ, представленный в упр.
5.16, дает Р(9~%)Р(МЧг) > -> (5.58) так что вероятность нахождения правильного значения г не менее 1/4. 'Упражнение 5.15. Покажите, что наименьшее общее кратное целых положительных чисел х и у равно зу/НОД(з, у) и тем самым может быть вычислено за 0(ЕР) операций, если з и у — 7 битовые числа. Упражнение 5.16. Докажите, что для всех з > 2 имеем 1', 1/уз оу > 2/Зх~. Покажите, что (5.59) т. е. выполнено неравенство (5.58). Сколько ресурсов требуется описанному здесь алгоритму? Для преобразования Адамара необходимо 0(Ь) элементов, а для обратного преобразования Фурье — 0(Ь~). Основные затраты идут на возведение в степень по модулю Ф: для этого нужно 0(Х ~) элементов; для разложения в непрерывную дробь также необходимо 0(ьз) элементов, так что для нахождения т' требуется 0(Ьз) элементов.
Если воспользоваться третьим методом для нахождения т по г', то где сумма берется по всем простым числам д, и р(х~у) — вероятность того, что з делит у. Ясно, что вероятность того,что д делит с'„ не превосходит 1/д, и то же верно для р(д~д~з). Следовательно, вероятность того, что д( и дз взаимно просты, не меньше, чем 5.3. Приложения: нахождение порядка и факторизация 293 всю эту процедуру следует повторить постоянное число рэз, поэтому затра- ты на нахождение т также равны 0(Ь~).
Ниже следует описание алгоритма в целом. Квантовое нахождение порядка Создать суперпозицию Применить обратное преобразование Фурье к первому регистру Измерить первый регистр Применить алгоритм цепных дробей 5.3.2 Факторизация Проблема отличения простпых чисел отп составнь1х и розложения составных чисел на прость1е множители является одной из наиболее ваэтсных и нужных во всей арифметике. [(...)] Дело честпи для ученых — всячески приветствовать и поддерживатпь лтобую помощь в реитении этой красивой и знаменитой проблемы. К.
Фридрих Гаусс (цитируется по Д. Кнуту) Дано составное число 5т; произведением каких простых чисел оно является? Так формулируется задача разложения на множители (задача фактпоризации), и оказывается, что она эквивалентна изученной нами задаче нахождения порядка в том смысле, что быстрый алгоритм длн нахождения порядка легко Вход: 1) черный ящик У,,гт, выполняющий преобразования ]Я]й) ]Я]хдй шот1 5т) для х, являющихся взаимно простыми с 5-битовым целым чис- 11 лом йт; 2) Ф = 2Х+1+ !ой 2+ — ) кубит в состоянии ]О); 3) Ь кубитов в 2е состоянии ]1).
Выход: наименьшее целое число т > О, обладающее тем свойством, что х" = 1 (шод йт). Время выполнения: 0(Ьз) операций; вероятность успеха Й(1). Процедура: 1. ]0)]1) Начальное состояние 1 21 2. — т — ~ ~[Я]1) 1 2$-1 3. -т — ) ]Я[Х1 Шсд 5т) ПрИМЕНИть У,тт Яс у=о -12'-1 сгпту?т]()]ив) 1/ г2' в=о 3=0 с-1 4. — т — ~ ]з/г)]и,) =о 5. -+ з(г 6. — тт 294 Глава 5. Квантовое преобразование Фурье и его приложения р(т четно и х'с ~ — 1(шос1 М)) > 1 — —. 2т' (5.60) Если объединить теоремы 5.2 и 5.3, то получим алгоритм, который с высокой вероятностью выдает нетривиальный делитель любого составного числа с"с'. Все шаги алгоритма могут быть эффективно реализованы на классическом компьютере, за исключением (насколько нам известно в настоящее время) «подпрограммы» для нахождения порядка.
Повторяя эту процедуру, получим разложение числа И. Приведем этот алгоритм. Алгоритм: сведение факторизации к нахождению порядка Вход: составное число гс'. Выход: нетривиальный делитель числа М. Время выполнения: 0((1оя с"7) ) операций; вероятность успеха Й(1). Процедура: 1. Если М четно, выдать делитель 2. 2.
Выяснить, не выполнено ли равенство М = а» для некоторых целых чисел а > 1 и 5 > 2; если да, то выдать делитель а (для выполнения этого шага воспользоваться классическим алгоритмом — см. упр. 5.17). переделать в быстрый алгоритм для факторизации. В этом подразделе мы объясним, как свести факторизацию к нахождению порядка, и приведем простой пример. Сведение факторизации к нахождению порядкапроводится в два шага. На первом шаге показано, что можно найти нетривиальный делитель числа с«', если только можно найти нетривиальное решение х ф х1 (пюс1И) уравнения ха = 1 (тес1с«').На втором шаге доказьвается, что случайно выбранное число у, взаимно простое с ссс, с большой вероятностью будет иметь четный порядок т, причем такой, что у"~~ ф х1 (пюс1 ссс').
Эти два шага оформлены в виде двух теорем, доказательства которых можно найти в разд. А4.3 Приложения 4. Теорема 5.2. Пусть И вЂ” Ь-битовое составное число, а х — решение уравнения хэ = 1 (пюс1 Ж), лежащее в интервале (1; Ж] и удовлетворяющее условию х ф х1 (пюс1 Ж) (мы будем называть такие решения нетривиальными). Тогда хотя бы одно из чисел НОД(х — 1, И) и НОД(х + 1, И) является нетривиальным делителем числа Ас, и этот делитель можно вычислить за 0(1 ~) операций. Теорема 5.3. Пусть М = р~~' ...р — разложение на простые множители нечетного составного целого положительного числа, а х — случайно выбранное целое число, взаимно-простое с Ж и удовлетворяющее условиям 1 (~ х < с"«' — 1 (случайный выбор таков, что все эти числа равновероятны). Тогда 5.3.
Приложения: нахождение порядка и факторизация 295 3. Выбрать случайным образом число х из интервала (1;!У вЂ” 1]. Если НОД(х, Л) > 1, выдать делитель НОД(х, 57). 4. С помощью алгоритма нахождения порядка найти число г, являющееся порядком х по модулю !у.
5. Если т чегно и х"7з ф — 1 (шод !У), вычислить НОД(х"7з — 1,И) и НОд(з"7~ + 1, !у) и проверить, не является ли одно из этих чисел нетривиальным делителем Ь1; если да, выдать его, если нет, то выполнение алгоритма завершается безуспешно. На шагах 1 и 2 либо алгоритм выдает делитель, либо мы убеждаемся, что И вЂ” нечетное число, имеющее более одного простого делителя. Эти два шага можно выполнить за 0(1) и 0(Ь~) операций соответственно.
На шаге 3 алгоритм либо выдает делитель, либо порождает случайный элемент х множества (О, 1, 2,..., 5! — 1). На шаге 4 с помощью алгоритма нахождения порядка отыскивается число г — порядок х по модулю !У. Шаг 5 завершает алгоритм, поскольку теорема 5.3 гарантирует, что с вероятностью не менее 1/2 число г будет четным, и при этом з"7э ф — 1 (шоб М), а в соответствии с теоремой 5.3 либо НОД(х'~з — 1, Ь!), либо НОД(х"7з + 1, !у) будет нетривиальным делителем числа М. Пример, иллюстрирующий работу алгоритма с использованием подпрограммы нахождения порядка, приведен во вставке 5.4. 'Упражнение 5.17. Пусть число М записывается Ь битами.
Цель этого упражнения — найти эффективный классический алгоритм, выясняющий, верно ли, что Ь! = аь для некоторых целых чисел а > 1 и Ь > 2. Это можно сделать следующим образом: 1. Покажите, что Ь < Ь (если Ь существует). 2. Покажите, что не более чем за 0(5э) операций можно вычислить у = !ойз й!, х = р/Ь (где Ь < Х) и найти два целых числа и~ и из, ближайших к 2*.
3. Покажите, что не более чем за 0(Ьз) операций можно вычислить и~~ и и~~ (пользуйтесь возведением в квадрат) и проверить, не равно ли одно яз этих чисел числу М. 4. Обьединяя два предыдущих результата, покажите, что за 0(Лз) операций можно выяснить, верно ли, что й! = а для целых а и Ь. 'Упражнение 5.18 (разложение числа 91). Пусть мы хотим разложить на множители число Ж = 91.
Убедитесь, что на шагах 1 и 2 алгоритм не останавливаегся. На шаге 3 предположим, что мы выбрали х = 4 (это число взаимно просто с 91). Вычислите г — порядок х по модулю !У и покажите, что х"7з(шос191) = 64 ф — 1( (шод 9)1), так что алгоритм успешно завершается и выдает НОД(64 — 1, 19) = 7. 296 Глава 5. Квантовое преобразование Фурье и его приложения Вряд ли зто самый эффективный из известных вем способов разложения числа 91 на множители. И действительно, если выполнять вычисления на классическом компьютере, этот способ ничего не даст, так как неизвестен хороший классический алгоритм нахождения порядка. Вставка 5.4. Квантовомехаиическое разложение числа 15 Использование нахождения порядка, определения собственного числа и разложения в цепную дробь в квантовом алгоритме факторизации можно проиллюстрировать на примере числа А7 = 15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
