Физика квантовой информации - Бауместер Д.
ISBN 5-94057-017-8
Скачать (прямая ссылка):
158 Концепция квантовых вычислений
стые множители) [36, 144, 146]. В ней надо для заданного числа N найти число к (не равное 1 и N), на которое N делится без остатка. В этом разделе мы кратко опишем, как можно свести эту задачу к задаче нахождения периода некоторой периодической функции / Тогда квантовый алгоритм, описанный в предыдущем разделе, решит задачу факторизации числа N за poly(log N) шагов, то есть, за время, полиномиальное по числу цифр в числе N.
Для начала, отметим, что пока не найден такой классический алгоритм, который бы факторизовал N за время, полиномиальное по числу цифр в N. Например, самый наивный возможный алгоритм основан на пробном делении N по очереди на все числа между 1 n\fN (так как любое составное N должно разлагаться на множители из этого диапазона). На это требуется, по крайней мере, 'Jn шагов (по крайней мере, один шаг на каждое деление), а л/N =21/21°влг экспоненциально велико по log N. При всех достижениях современной математики, самому быстрому известному нам алгоритму требуется время порядка exp((log N)m (log log// )2/3).
Чтобы свести задачу факторизации к задаче нахождения периода, нам понадобятся некоторые основные результаты из теории чисел. Более углубленно они описаны в приложении работы [144], а полное их объяснение можно найти в самых стандартных текстах по теории чисел [142, 143]. Мы начнем с того, что выберем случайным образом число а < N. С помощью алгоритма Евклида вычислим, за время poly(log N), наибольший общий делитель a wN. Если он оказался больше единицы, то, значит, мы нашли делитель N, и алгоритм завершен! Однако, с подавляющей вероятностью, выбранное наугад число а окажется взаимно простым с N. Из теоремы о простом числе (о ней упоминалось в предыдущем разделе) следует, что эта вероятность превышает 1/log N при больших N. Если а взаимно просто с N, то, согласно теореме Эйлера из теории чисел, существует такая степень а, которая делится на N с остатком 1. Пусть г обозначает наименьшую такую степень:
аТ = 1 mod N и г - наименьшая такая степень. (4.27)
(Если а не взаимно просто с N, то такой степени не существует). Число г называется порядком а по модулю N. Далее мы покажем, что информация об г может дать нам делитель N.
Предположим, что мы знаем, как определить г (см. ниже) и, кроме того, предположим, что число г оказалось четным. Тогда можно переписать (4.27) в виде ar - I = О mod N, и разложить левую часть этого выражения как разность квадратов:
(аг/2 -1 ){агП +1) = 0 mod N . (4 28)
Квантовые алгоритмы 159
Пусть а = агП-1 и /? = ar/2 +1. Тогда произведение а/5 делится на N. Если ни а,,ни р по отдельности не делятся на N, то у каждого из них есть с N общие множители. В этом случае, вычислив наибольший общий делитель N с а и fi (снова с помощью алгоритма Евклида) мы найдем нетривиальный делитель числа N.
В качестве примера, возьмем N = 15, и выберем взаимно простое с ним число о = 7. Вычисляя степени 7 по модулю 15, найдем, что, 74 = 1 mod 15, то есть, что порядок 7 по модулю 15 равен 4. Значит, число 15 должно без остатка делить произведение (74/2 - 1)(74/2 + 1) = (48)(50). Вычисляя наибольшие общие делители 15 и 50 и 48, находим, что они равны, соответственно, 5 и 3 - то есть, двум нетривиальным делителям числа 15.
Наш метод даст делитель N при условии, что г окажется простым числом, и что ни одно из чисел (агП± 1) не делится на N без остатка. Чтобы гарантировать, что эти два условия выполняются достаточно часто (для случайно выбранных чисел а), воспользуемся
Теоремой: Пусть N - нечетное число, и предположим, что а < N взаимно просто с N выбрано случайным образом. Пусть г - порядок а по модулю N. Тогда вероятность того, что число г - четное, и что (o'72 ± 1) , не делятся на N без остатка, всегда >1/2. ?
Доказательство (довольно длинное) этой теоремы можно найти в приложении В к работе [144], к которой мы отсылаем читателя за деталями.
В целом, наш метод позволит найти делитель N с вероятностью, по крайней мере, 50% в каждом случае. Эту вероятность успешного вычисления можно сделать насколько угодно близкой к единице, поскольку после К повторений всей процедуры (с константой К не зависящей от АО число N окажется факторизовано с вероятностью, превышающей 1 - 1/2*.
Все шаги в этой процедуре - например, применение алгоритма Евклида или арифметические операции с числами, - можно проделать за время poly(log АО. Единственный спорный элемент алгоритма
- это способ найти г за время poly(log АО. Рассмотрим экспоненциальную функцию
f(x) = ax mod N . (4.29)
Теперь (4.27) утверждает, в точности, что функция /- периодическая с периодом г, то есть, что/(х+г) =/(х). Значит, можно использовать квантовый алгоритм для определения периода, описанный в предыдущем разделе, чтобы найти г. Чтобы применить этот алгоритм, нам надо ограничить диапазон значений х в (4.29) конечной областью
О < х < q для некоторого q. Если q не делится на (неизвестное) число
160 Концепция квантовых вычислений
г, то есть, q = Ar+t для некоторого 0 < t < г, то получившаяся функция не будет в точности периодической - один последний период, состоящий из t значений, будет неполным. Однако если будет выбрано достаточно большое q, содержащее большое количество периодов функции/ то влияние последнего неполного периода на преобразование Фурье размера q xq будет пренебрежимо мало. Это интуитивно ясно. На самом деле, можно показать, что, если выбрать q порядка 0(N2), то можно определить г достаточно точно. Более подробный анализ этой неполной периодичности (включающий теорию непрерывных дробей) читатель сможет найти в [36, 144]. В качестве числа q обычно выбирается некоторая степень двойки, что особенно хорошо согласуется с формализмом быстрого преобразования Фурье (см. [134, 145]).
