Алгоритм Шора

Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число N за время ${\textstyle{O(\log^2 N \log^3(\log N))}}$, используя O(log N) логических кубитов.

Значимость алгоритма заключается в том, что при использовании квантового компьютера с несколькими сотнями логических кубитов, он сделает возможным взлом криптографических систем с открытым ключом. К примеру, RSA использует открытый ключ N, являющийся произведением двух больших простых чисел. Один из способов взломать шифр RSA — найти множители N. При достаточно большом N это практически невозможно сделать, используя известные классические алгоритмы. Наилучший из известных классических алгоритмов факторизации требует времени порядка $N^{1/3}$. Так как алгоритм Шора работает только на квантовом компьютере, в настоящее время не существует технических средств, позволяющих за полиномиальное время от длины числа разложить достаточно большое число на множители. Алгоритм Шора в свою очередь, используя возможности квантовых компьютеров, способен произвести факторизацию числа не просто за полиномиальное время, а за время, не намного превосходящее время умножения целых чисел (то есть практически так же быстро, как происходит само шифрование). Таким образом, реализация масштабируемого квантового компьютера в случае ее успеха поставила бы крест на большей части современной криптографической защиты. (Речь не только о схеме RSA, прямо опирающейся на сложности факторизации, но и о других сходных схемах, которые квантовый компьютер способен взломать аналогичным образом).

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

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

Квантовое преобразование Фурье

Основным достижением П. Шора является реализация им дискретной версии преобразования Фурье на квантовом компьютере — так называемое квантовое преобразование Фурье (QFT — Quantum Fourier Transform). Ключевая роль преобразования Фурье для проблемы факторизации была известна до Шора. С другой стороны, реализованное Шором QFT имеет многочисленные применения и помимо факторизации.

Квантовое преобразование Фурье действует на базисных векторах $|a\rangle ,\ a=0,1,\ldots,N-1$ согласно формуле

$QFT:\ |a \rangle \longrightarrow \frac{1}{\sqrt{N}}\sum\limits_{c=0}^{N-1}\exp(-2\pi\ i\ ac/N)|c \rangle .$

QFT продолжается по линейности на все гильбертово пространство состояний $H$. QFT является унитарным оператором в $H$, обратное к нему задается аналогичной формулой, только без знака «−» в экспоненте.

Обратный к QFT оператор может быть задан квантовой схемой из вентилей (quantum gate array) следующего вида. (не закончено)

Основные идеи алгоритма Шора

Алгоритм Шора основан на возможности быстро вычислить собственные значения унитарного оператора с высокой точностью, если можно эффективно вычислять любые его степени. Взяв в качестве такого оператора умножение на $x$ по модулю $N$ (этот оператор действует в $2^n$ мерном пространстве, где $2^{n-1}< N\le 2^n$, преобразуя базисный вектор, соответствующий числу $a$, в базисный вектор, соответствующий числу $xa(mod N)$), мы сможем вычислить такое $n$, что $x^n=1(mod N)$, что позволяет (с высокой вероятностью) разложить $N$ на множители на обычном компьютере.

См. также

• Квантовый компьютер
• Алгоритм Гровера
• Алгоритм Дойча — Джоза

Ссылки

• Курс «Современные задачи теоретической информатики» (лекции по квантовым вычислениям: введение, суперплотное кодирование, квантовая телепортация, алгоритмы Саймона и Шора)
• Документ pdf «Алгоритм Шора»
• Исходные тексты симулятора квантового компьютера на C++ и полной реализации алгоритма Шора, включая схему обратимого модульного возведения в степень