Алгори́тм Шо́ра — квантовый алгоритмфакторизации (разложения числа на простые множители), позволяющий разложить число за время , используя логических кубитов.
Значимость алгоритма заключается в том, что с его помощью (при использовании квантового компьютера с несколькими тысячами логических кубитов) становится возможным взлом криптографических систем с открытым ключом. К примеру, RSA использует открытый ключ являющийся произведением двух больших простых чисел. Один из способов взломать шифр RSA — найти множители При достаточно большом это практически невозможно сделать, используя известные классические алгоритмы. Наилучшие из известных классических детерминированных доказанных алгоритмов факторизации, такие как метод квадратичных форм Шенкса и алгоритм Полларда — Штрассена, требуют времени порядка Также метод квадратичных форм Шенкса может работать за время порядка , если верна Гипотеза Римана. Среди вероятностных алгоритмов лидером факторизации является специальный метод решета числового поля, который способен с вероятностью 1/2 найти простой делитель за субэкспоненциальное время Алгоритм Шора, используя возможности квантовых компьютеров, способен произвести факторизацию числа не просто за полиномиальное время, а за время, не намного превосходящее время умножения целых чисел (то есть практически так же быстро, как происходит само шифрование). Таким образом, реализация масштабируемого квантового компьютера поставит крест на большей части современной криптографической защиты. Речь не только о схеме RSA, прямо опирающейся на сложности факторизации, но и о других сходных схемах, которые квантовый компьютер способен взломать аналогичным образом.
Алгоритм Шора имеет вероятностный характер. Первый источник случайности встроен в классическое вероятностное сведе́ние разложения на множители к нахождению периода некоторой функции. Второй источник появляется из необходимости наблюдения квантовой памяти, которое также даёт случайные результаты[1].
Основа алгоритма Шора: способность информационных единиц квантовых компьютеров — кубитов — принимать несколько значений одновременно и находиться в состоянии «квантовой запутанности». Поэтому он позволяет проводить вычисления в условиях экономии кубитов. Принцип работы алгоритма Шора можно разделить на 2 части: первая — классическое сведе́ние разложения на множители к нахождению периода некоторой функции, вторая — квантовое нахождение периода этой функции.
Пусть:
— число, которое мы хотим разложить на множители (оно не должно быть целой степенью нечётного числа);
— размер регистра памяти, который используется (не считая свалки). Битовый размер этой памяти примерно в 2 раза больше размера . Точнее, ;
Отметим, что , , — фиксированы.
В алгоритме Шора используется стандартный способ сведения задачи разложения к задаче поиска периода функции для случайно подобранного числа [2].
Если можно эффективно вычислить как функцию , то можно найти собственный делитель за время, ограниченное полиномом от с вероятностью для любого фиксированного .
Предположим, что для данного период чётен и удовлетворяет условию
Тогда
— собственный делитель Функция вычислима за полиномиальное время.
Вероятность выполнения этого условия где — число различных нечётных простых делителей , следовательно, в данном случае. Поэтому хорошее значение с вероятностью найдётся за попыток. Самое длинное вычисление в одной попытке — вычисление [3][4].
Для осуществления квантовой части алгоритма вычислительная схема представляет собой квантовых регистра и . Первоначально каждый из них состоит из совокупности кубитов в нулевом булевом состоянии
Регистр используется для размещения аргументов функции Регистр (вспомогательный) используется для размещения значений функции с периодом , подлежащим вычислению.
Первый шаг. На первом шаге с помощью операции Уолша — Адамара, которая представляет собой преобразование кубита с помощью оператора первоначальное состояние регистра переводится в равновероятную суперпозицию всех булевых состояний . Второй регистр остаётся в состоянии В итоге получается следующее состояние для системы двух регистров:
Второй шаг. Пусть — унитарное преобразование, которое переводит в На втором шаге применяется унитарное преобразование к системе двух регистров. Получается следующее состояние системы:
то есть между состояниями обоих регистров образуется определённая связь.
Третий шаг. Квантовое Фурье-преобразование представляет собой унитарное преобразование состояния квантового регистра, описываемого -мерным вектором состояния вида в другое состояние
где амплитуда Фурье-преобразования имеет вид
В двумерной -плоскости преобразование Фурье соответствует повороту осей координат на 90°, которое приводит к преобразованию шкалы в шкалу . На третьем шаге над состоянием первого регистра производится преобразование Фурье, и получается
Четвёртый шаг. На четвёртом шаге выполняется измерение первого регистра относительно ортогональной проекции вида:
На оставшейся части прогона работает классический компьютер:
Находится наилучшее приближение (снизу) к со знаменателем
Пробуем в роли :
Если , то следует вычислить
Если нечётно или если чётно, но собственный делитель не обнаружен, то следует повторить прогон раз с тем же самым . В случае отказа изменить и начать новый прогон алгоритма[3][4].
В некоторой степени определение периода функции с помощью преобразования Фурье аналогично измерению постоянных решётки кристалла методом рентгеновской или нейтронной дифракции. Чтобы определить период не требуется вычислять все значения В этом смысле задача похожа на задачу Дойча, в которой важно знать не все значения функции, а только некоторые её свойства[6].
Измерение второго регистра с результатом где приводит состояние к
где
После измерения состояния первый регистр состоит только из базисных векторов вида таких, что для всех Поэтому он имеет дискретный однородный спектр. Невозможно прямо получить период или кратное ему число, измеряя первый регистр, потому что здесь — случайная величина. Здесь применяется дискретное преобразование Фурье вида
на регистр, так как вероятность спектра в преобразованном состоянии инвариантна относительно смещения (преобразованию поддаются только фазы, а не абсолютные значения амплитуд).
где и
Если кратно , тогда если кратно и в противном случае. Даже если не является степенью числа 2, то спектр показывает отдельные пики с периодом потому что
Для первого регистра используется кубитов, когда потому что это гарантирует по крайней мере элементов в приведённой сумме, и таким образом ширина пиков будет порядка
Если теперь вычислить первый регистр, то получится значение близкое к где Оно может быть записано как Это сводится к нахождению аппроксимации где для конкретного числа двоичной точки Для решения этой задачи используются цепные дроби.
Поскольку форма рационального числа не единственна в своем роде, то и определяются как если Вероятность того, что оба числа и просты, больше чем поэтому, чтобы вероятность успеха была близка к единице, необходимо только попыток[7][5].
Другая математическая задача, дискретное логарифмирование, часто применяющаяся для создания систем асимметричной криптографии, также является уязвимой для квантового алгоритма, предложенного Шором в той же статье[8].
Shor P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // Foundations of Computer Science : Conference Publications. — 1997. — P. 1484–1509.
Валиев К. А., Кокин А. А. Квантовые компьютеры: надежды и реальность. — Ижевск: РХД, 2004. — 320 с.
Исходные тексты симулятора квантового компьютера на C++ и полной реализации алгоритма Шора, включая схему обратимого модульного возведения в степень, с подробным описанием и схемами квантовых вентилей