Алгоритм Шора является одним из наиболее распространенных алгоритмов и направлен на решение задачи факторизации. Факторизация – это разложение чисел на множители. Факторизация широко применяется в современной теории чисел и криптоанализа. Следует отметить, что эта задача весьма сложная, так как трудоемкость классических алгоритмов растет экспоненциально с увеличением размера факторизуемых чисел. Так, при фактризации числа N путем простого перебора необходимо будет перебрать все варианты от 2 до √N, а это весьма сложно если мы имеем дело с очень большими числами.
Пример использования факторизации – это алгоритмы шифрования с открытым ключом (RSA, El Gamal и т.д.). В данном случае ключ представляет собой пару больших чисел, а взлом шифра, который заключается в нахождении по открытому ключу приватного и наоборот, требует решения задачи факторизации.
Алгоритм Шора позволяет выполнить решение задачи факторизации за полиномиальное время. Это осуществляется за счет использования свойства квантового параллелизма и сведения задачи к поиску периода функции.
Допустим нам необходимо разложить на множители некоторое число N. Изначально выберем произвольное число a < N и рассматриваем функцию fa(x) = axmodN.
Функция fa(x) является периодической с периодом r. Период r является порядком числа a: ar = 1 mod N и ∀r1 < r → ari ≠ 1 mod N. Если число Nпростое, то период r будет равно N - 1. Этот случай весьма простой и легко реализуется проверкой на простоту классическими методами. В общем случае fa(x + r) = fa(x). Если период rизвестен, то разложение на множители числа N легко можно определить классическими методами. В частности, если период r является четным числом, то из соотношения ar - 1 = 0 mod N можно записать:
(ar/2- 1)(ar/2+ 1) = 0 mod N
Так как (ar/2- 1)(ar/2+ 1) делится на N, то оба сомножителя имеют общие с Nделители. Эти делители можно определить классическим алгоритмом Евклида по поиску наибольшего общего делителя. Если же период r является нечетным или (ar/2- 1)(ar/2+ 1) вырождается в ноль, то следует выбрать другое число a. Для больших чисел N это случается редко.
Квантовый алгоритм Шора предназначен для быстрого поиска периода r. Для реализации алгоритма необходимо использовать квантовый компьютер с двумя квантовыми регистрами размера n. Причем размер должен быть таким, что M = 2n > N, M ≈ N2. Алгоритм определения периода r будет следующим:
1. На первом этапе необходимо приготовить два входных регистра в состоянии |0〉.
2. Далее воздействием на каждый кубит входного регистра преобразованием Адамара:
3. Применим к обоим регистрам квантовую схему, реализующую функцию fa(x). Теперь регистры перейдут в состояние:
Таким образом, в выходном регистре будет суперпозиция всех возможных значений функции fa(x).
4. Далее производится измерение выходного регистра. В результате измерений мы получим
После измерения мы получим значение функции fa(k)при некотором случайном значении k, а выходной регистр перейдет в состояние |fa(k)〉. Измеренное значение выходного регистра нас не интересует, но важно, что состояние входного регистра редуцируется до комбинации только тех состояний, которые совместимы с измеренным на выходе значением: fa(x) = fa(k), x = k, x = k + r, x = k + 2r и т.д.
5. Для извлечения периодичности в выходном регистре необходимо выполнить квантовое преобразование Фурье и измерение результата преобразования.
При преобразовании Фурье период r будет преобразован в M / r и измерение приведет к тому, что с высокой долей вероятности мы получим jM/r для j = 1, 2, ... Далее, применив классический алгоритм разложения в непрерывную дробь (алгоритм Евклида) можно извлечь из полученного результата период r.
На рис. 1 представлена структурная схема алгоритма Шора.
Приведем классический пример реализации алгоритма Шора.
Пример 3.1: Допустим нам необходимо выполнить факторизацию числа N = pq = 3·5 = 15. Используя функцию Эйлера можно определить функцию fa(x):
Ф(N) = (q - 1)(p - 1) = (5 - 1)(3 - 1) = 8 → a = 7 → fa(x) = 7x mod15.
Функцию fa(x) можно записать в следующем виде:
fa(x) = (78)x3 · (74)x2 · (72)x1 · (71)x0 mod15
Поскольку (78)x3mod15 = 1, (74)x2mod15 = 1 и (72)x1mod15 = (4)x1mod15 то можно переопределить функцию как:
fa(x) = (4)x1 · (7)x0mod15
На рис. 2 представлена квантовая схема, реализующая алгоритм Шора для данного примера.
Рис. 2. Квантовая схема алгоритма Шора для N = 15
На рис. 2 блок под номером 1 реализует умножение регистра |y〉 на 7, а блок под номером 2 – умножение на 4. Далее выполняется квантовое преобразование Фурье (блок QFT) и измерение результата преобразования.
Выполним моделирование данной схемы в системе IBM Quantum Experience. Результаты серии измерений представлены на рис. 3.
Рис. 3. Результаты симуляции алгоритма Шора для N = 15
Из рис. 3 видно, что в результате измерений мы получили 0, 4, 8 и 12. Отбросив нулевой результат и вспомнив, что преобразование Фурье приведут к тому, что с высокой долей вероятности мы получим jM/rдля j = 1, 2, ... можно вычислить период r:
Таким образом, мы определили период r = 4. Зная период, мы можем определить числа p и q:
НОД(7r/2 + 1,15) = НОД(50,15) = 5,
НОД(7r/2 - 1,15) = НОД(49,15) = 3.