Почти все процессы в интернете, требующие шифрования полагаются на криптографический алгоритм RSA. Стойкость RSA основана на простой идее: классические компьютеры быстро умеют перемножать простые числа, а вот разложить числа на простые множители задача для компьютера очень сложная.
В 1994 году математик из MIT Питер Шор предложил квантовый алгоритм, который полностью изменил правила игры. Его идея заключалась в том, чтобы свести задачу разложени на простые множители к нахождению периода некоторой функции — а эту задачу квантовый компьютер может решить экспоненциально быстрее классического. Используя суперпозицию, кубиты могут одновременно «попробовать» все возможные значения, а затем с помощью квантового преобразования Фурье извлечь нужную информацию о периоде за полиномиальное время.
300-значное число, на факторизацию которого классическому компьютеру потребовались бы миллиарды лет, квантовый компьютер с несколькими тысячами логических кубитов смог бы взломать за часы или минуты.
Алгоритм Шора открыл новую область криптографии — постквантовую криптографию, которая занимается разработкой шифров, устойчивых как к классическим, так и к квантовым взломщикам. Банки, правительства и технологические корпорации по всему миру начали переходить на квантово-безопасные алгоритмы шифрования.
Для взлома RSA-2048 потребуется около 20 миллионов физических кубитов с учётом коррекции ошибок — на несколько порядков больше, чем могут предоставить современные устройства. Кроме того, алгоритм требует больших времён когерентности, что придаёт некую отдалённость практической реализации алгоритма.
Алгоритм Шора — это концептуальный прорыв, показавший, что квантовые компьютеры могут решать задачи, недоступные классике. Его нельзя применить прямо сейчас для реального взлома, но можно использовать как мощнейший аргумент для постквантовой криптографии.