Алгоритм Шора — квантовый алгоритм факторизации (разложения числа на простые множители)

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

Алгоритм Шора был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами.

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

Алгоритм Шора представляет собой эпохальное достижение в квантовых вычислениях, демонстрируя потенциал квантовых алгоритмов для решения проблем, которые ранее считались неразрешимыми. Его открытие оказало глубокое влияние как на теоретические, так и на практические аспекты квантовых вычислений и криптографии. Алгоритм Шора, используя возможности квантовых компьютеров, способен произвести факторизацию числа не просто за полиномиальное время, а за время, не намного превосходящее время умножения целых чисел (то есть практически так же быстро, как происходит само шифрование). Таким образом, реализация масштабируемого квантового компьютера поставит крест на большей части современной криптографической защиты. Речь не только о схеме RSA, прямо опирающейся на сложности факторизации, но и о других сходных схемах, которые квантовый компьютер способен взломать аналогичным образом.

Источник: vk.com

Комментарии: