Квантовые вычисления и алгоритм Шора: Конец классической криптографии

В отличие от классического бита, который всегда равен строго 0 или 1, квантовый бит (кубит) благодаря явлению квантовой суперпозиции может находиться в состоянии, которое является линейной комбинацией 0 и 1 одновременно. Если вы свяжете вместе (запутаете) 300 кубитов, они смогут одновременно хранить и обрабатывать 2^300 различных состояний — это число больше, чем количество атомов в наблюдаемой Вселенной.

Классический компьютер, чтобы найти множители числа N, должен перебирать варианты один за другим. Алгоритм Шора решает задачу факторизации числа N за полиномиальное время (очень быстро) благодаря гениальному переводу задачи из теории чисел в область частотного анализа.

Математика алгоритма состоит из двух частей: классической и квантовой. Классическая часть (на обычном процессоре) сводит задачу факторизации к задаче поиска периода функции модульного возведения в степень (f(x) = a^x mod N). Квантовая часть делает всю тяжелую работу: она подготавливает суперпозицию всех возможных значений x, вычисляет функцию сразу для всех значений одновременно и затем применяет Квантовое преобразование Фурье (QFT). QFT работает как оптическая линза, которая собирает квантовые вероятности так, что неправильные ответы гасят друг друга (деструктивная интерференция), а правильный ответ (период функции) многократно усиливается. Измерив систему, мы с огромной вероятностью сразу получаем нужный период, из которого классический компьютер за миллисекунды извлекает простые множители.

Создание полноценного квантового компьютера с миллионами кубитов — невероятно сложная инженерная задача из-за проблемы "квантовой декогеренции" (кубиты теряют свое состояние от малейшего изменения температуры или электромагнитного фона). Однако угроза настолько реальна, что математики по всему миру уже сейчас переходят на Постквантовую криптографию. Они разрабатывают новые шифры, основанные на задачах поиска кратчайшего вектора в многомерных решетках (Lattice-based cryptography) или на криптографии с использованием хеш-деревьев, так как математически доказано, что квантовые компьютеры не дают экспоненциального ускорения для этих конкретных задач дискретной математики.