Как алгоритм Шора использует квантовую Фурье-трансформацию для эффективной факторизации больших простых чисел?
Алгоритм Шора — это квантовый алгоритм, предназначенный для факторизации больших целых чисел за полиномиальное время, что невозможно для классических алгоритмов при больших размерах чисел. Ключевым компонентом этого алгоритма является квантовое преобразование Фурье (Quantum Fourier Transform, QFT), которое позволяет эффективно находить период некоторой функции, связанной с факторизуемым числом.
### Основная идея
Алгоритм Шора сводит задачу факторизации целого числа \( N \) к задаче нахождения периода \( r \) функции:
\[
f(x) = a^x \bmod N,
\]
где \( a \) — случайно выбранное целое число, взаимно простое с \( N \). Если удаётся найти наименьший период \( r \), такой что \( a^r \equiv 1 \pmod{N} \), то можно использовать его для вычисления нетривиальных делителей \( N \) (при условии, что \( r \) чётно и \( a^{r/2} \not\equiv -1 \pmod{N} \)).
### Роль квантового преобразования Фурье
Именно здесь вступает в игру квантовое преобразование Фурье. В классическом случае поиск периода требует экспоненциального времени, но в квантовом алгоритме:
1. Используется квантовый параллелизм, чтобы одновременно вычислить значения \( f(x) \) для всех \( x \) в суперпозиции.
2. Затем применяется квантовое преобразование Фурье к регистру, содержащему значения \( x \). Это преобразование выделяет частотные компоненты, соответствующие периоду \( r \), и концентрирует амплитуды вблизи кратных \( \frac{Q}{r} \), где \( Q \) — размер регистра.
3. Измерение после QFT с высокой вероятностью даёт значение, близкое к \( \frac{kQ}{r} \) для некоторого целого \( k \). Используя классический алгоритм (цепные дроби), можно восстановить \( r \) из этого результата.
Таким образом, QFT позволяет эффективно определить период функции, что и даёт экспоненциальное ускорение по сравнению с классическими методами факторизации .
Эта эффективность делает алгоритм Шора теоретической угрозой для криптосистем, основанных на сложности факторизации (например, RSA), если будут построены достаточно мощные квантовые компьютеры .