5 кубита
Алгоритм Шора
Факторизация больших чисел — угроза RSA-криптографии.
История
Открыт Питером Шором в 1994 году.
Задача
Разложить составное число N на множители.
Математика
QFT + поиск периода функции f(x) = a^x mod N.
Сложность
O((log N)³) vs субэкспоненциально классически
vs Классика
Экспоненциальное ускорение — революция в криптографии.