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

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

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

Об алгоритме

Значимость алгоритма заключается в том, что с его помощью (при использовании квантового компьютера с несколькими тысячами логических кубитов) становится возможным взлом криптографических систем с открытым ключом. К примеру, RSA использует открытый ключ $M$, являющийся произведением двух больших простых чисел. Один из способов взломать шифр RSA — найти множители $M$. При достаточно большом $M$ это практически невозможно сделать, используя известные классические алгоритмы. Наилучшие из известных классических детерминированных доказанных алгоритмов факторизации, такие как метод квадратичных форм Шенкса и алгоритм Полларда — Штрассена, требуют времени порядка $M^{1/4}$. Также метод квадратичных форм Шенкса может работать за время порядка $M^{1/5}$, если верна Гипотеза Римана. Среди вероятностных алгоритмов лидером факторизации является специальный метод решета числового поля, который способен с вероятностью 1/2 найти простой делитель за субэкспоненциальное время $\exp \left(\left({\frac {32}{9}}\cdot \log M\right)^{1/3}\cdot (\log \log M)^{2/3}\right)$. Алгоритм Шора, используя возможности квантовых компьютеров, способен произвести факторизацию числа не просто за полиномиальное время, а за время, не намного превосходящее время умножения целых чисел (то есть практически так же быстро, как происходит само шифрование). Таким образом, реализация масштабируемого квантового компьютера поставит крест на большей части современной криптографической защиты. Речь не только о схеме RSA, прямо опирающейся на сложности факторизации, но и о других сходных схемах, которые квантовый компьютер способен взломать аналогичным образом.

Алгоритм Шора имеет вероятностный характер. Первый источник случайности встроен в классическое вероятностное сведе́ние разложения на множители к нахождению периода некоторой функции. Второй источник появляется из необходимости наблюдения квантовой памяти, которое также даёт случайные результаты.

Улучшение алгоритма

Основная статья: Алгоритм Регева

В 2023 году Одед Регев опубликовал новый квантовый алгоритм по факторизации чисел, превосходящий по эффективности Алгоритм Шора. Регев разработал свой новый алгоритм, дополнив алгоритм Шора методами из раздела криптографии, занимающегося многомерной геометрией. Ему удалось обобщить алгоритм на произвольное количество измерений, а не только на два, в результате чего для факторизации чисел квантовому компьютеру требуется гораздо меньше логических шагов. Специалисты по квантовыми вычислениями отмечают, что удивительно и неожиданно, что спустя 30 лет кто-то смог качественно улучшить алгоритм Шора.

Принцип работы алгоритма Шора

Основа алгоритма Шора: способность информационных единиц квантовых компьютеров — кубитов — принимать несколько значений одновременно и находиться в состоянии «квантовой запутанности». Поэтому он позволяет проводить вычисления в условиях экономии кубитов. Принцип работы алгоритма Шора можно разделить на 2 части: первая — классическое сведе́ние разложения на множители к нахождению периода некоторой функции, вторая — квантовое нахождение периода этой функции. Пусть:

$M$ — число, которое мы хотим разложить на множители (оно не должно быть целой степенью нечётного числа);

$N$ — размер регистра памяти, который используется (не считая свалки). Битовый размер этой памяти $n=\log _{2}N$ примерно в 2 раза больше размера $M$. Точнее, $M^{2}<N=2^{n}<2M^{2}$;

$t$ — случайный параметр, такой что $1<t<M$ и $\operatorname {gcd} (t,M)=1$ (где $\operatorname {gcd}$ — наибольший общий делитель).

Отметим, что $t$, $N$, $M$ — фиксированы. В алгоритме Шора используется стандартный способ сведения задачи разложения к задаче поиска периода $r$ функции для случайно подобранного числа $t$.

Классическая часть алгоритма

Минимальное $r$ такое, что $t^{r}\equiv 1\ {\mbox{mod}}\ M$, — это порядок $t$ по модулю $M$.

Порядок $r$ является периодом функции $f(x)=t^{x}\ {\mbox{mod}}\ M$, где $x=0,1,2,\dots ,N-1$.

Если можно эффективно вычислить $r$ как функцию $t$, то можно найти собственный делитель $M$ за время, ограниченное полиномом от $\log _{2}M$ с вероятностью $\geqslant 1-M^{-m}$ для любого фиксированного $m$.

Предположим, что для данного $t$ период $r$ чётен $(r\equiv 0\ {\mbox{mod}}\ 2)$ и удовлетворяет условию

$t^{\frac {r}{2}}\not \equiv -1\ {\mbox{mod}}\ M$.

Тогда

$\operatorname {gcd} (t^{\frac {r}{2}}+1,M)$ — собственный делитель $M$. Функция $\operatorname {gcd}$ вычислима за полиномиальное время.

Вероятность выполнения этого условия $\geqslant 1-{\frac {1}{2^{k-1}}}$, где $k$ — число различных нечётных простых делителей $M$, следовательно, $\geqslant {\frac {1}{2}}$ в данном случае. Поэтому хорошее значение $t$ с вероятностью $\geqslant 1-M^{-m}$ найдётся за $O(\log M)$ попыток. Самое длинное вычисление в одной попытке — вычисление $t^{\frac {r}{2}}$.

Квантовая часть алгоритма

Для осуществления квантовой части алгоритма вычислительная схема представляет собой $2$ квантовых регистра $X$ и $Y$. Первоначально каждый из них состоит из совокупности кубитов в нулевом булевом состоянии $|0\rangle$.

Регистр $X$ используется для размещения аргументов $x$ функции $f(x)$. Регистр $Y$ (вспомогательный) используется для размещения значений функции $f(x)$ с периодом $r$, подлежащим вычислению.

Квантовое вычисление состоит из 4 шагов:

• Первый шаг. На первом шаге с помощью операции Уолша — Адамара, которая представляет собой преобразование кубита с помощью оператора $H={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}$, первоначальное состояние $|0\rangle \$ регистра $X$ переводится в равновероятную суперпозицию всех булевых состояний $N$. Второй регистр $Y$ остаётся в состоянии $|0\rangle$. В итоге получается следующее состояние для системы двух регистров:

  ${\frac {1}{\sqrt {N}}}\sum \limits _{x=0}^{N-1}|x,0\rangle .$

• Второй шаг. Пусть $U_{f}$ — унитарное преобразование, которое переводит $|x,0\rangle$ в $|x,f(x)\rangle$. На втором шаге применяется унитарное преобразование к системе двух регистров. Получается следующее состояние системы:

${\frac {1}{\sqrt {N}}}\sum \limits _{x=0}^{N-1}|x,0\rangle \quad \xrightarrow {U_{f}} \quad {\frac {1}{\sqrt {N}}}\sum \limits _{x=0}^{N-1}|x,t^{x}\ {\mbox{mod}}\ M\rangle$, то есть между состояниями обоих регистров образуется определённая связь.

• Третий шаг. Квантовое Фурье-преобразование представляет собой унитарное преобразование состояния квантового регистра, описываемого $N$-мерным вектором состояния вида $\sum \limits _{x=0}^{N-1}f(x)|x\rangle$, в другое состояние $\sum \limits _{k=0}^{N-1}{\tilde {f}}(k)|k\rangle$:

$\mathrm {QFT} _{N}:\sum \limits _{x=0}^{N-1}f(x)|x\rangle \ \Rightarrow \sum \limits _{k=0}^{N-1}{\tilde {f}}(k)|k\rangle$, где амплитуда фурье-преобразования $f(x)$ имеет вид

${\tilde {f}}(k)={\frac {1}{N}}\sum \limits _{x=0}^{N-1}\exp(2\pi \ i\ kx/N)f(x)$.

В двумерной $x,k$-плоскости преобразование Фурье соответствует повороту осей координат на 90°, которое приводит к преобразованию шкалы $x$ в шкалу $k$. На третьем шаге над состоянием первого регистра производится преобразование Фурье, и получается

${\frac {1}{N}}\sum \limits _{x=0}^{N-1}\sum \limits _{k=0}^{N-1}\exp(2\pi \ i\ kx/N)|k,t^{x}\ {\mbox{mod}}\ M\rangle$.

• Четвёртый шаг. На четвёртом шаге выполняется измерение первого регистра $X$ относительно ортогональной проекции вида:

$|0,0\rangle \otimes I,\quad |1,1\rangle \otimes I,\quad \dots ,\quad |N-1,N-1\rangle \otimes I$, где $I$ — тождественный оператор на гильбертовом пространстве второго регистра $Y$.

В результате получается $|k,t^{k}\ {\mbox{mod}}\ M\rangle \$ с вероятностью

$\left|{\frac {1}{N}}\sum \limits _{x:\ t^{x}\equiv t^{k}\ {\mbox{mod}}\ M}\exp(2\pi \ i\ kx/N)\right|^{2}$.

На оставшейся части прогона работает классический компьютер:

• Находится наилучшее приближение (снизу) к ${\frac {k}{N}}\$ со знаменателем $r'<M<{\sqrt {N}}:$

  $\left|{\frac {k}{N}}\ -{\frac {d'}{r'}}\right|<{\frac {1}{2N}}$.

• Пробуем $r'$ в роли $r$:
  • Если $r'\equiv 0\ {\mbox{mod}}\ 2$, то следует вычислить $\operatorname {gcd} (t^{\frac {r'}{2}}\pm 1,M)$.
  • Если $r'$ нечётно или если $r'$ чётно, но собственный делитель $M$ не обнаружен, то следует повторить прогон $O(\log \log M)$ раз с тем же самым $t$. В случае отказа изменить $t$ и начать новый прогон алгоритма.

В некоторой степени определение периода функции с помощью преобразования Фурье аналогично измерению постоянных решётки кристалла методом рентгеновской или нейтронной дифракции. Чтобы определить период $r$, не требуется вычислять все значения $f\left(x\right)$. В этом смысле задача похожа на задачу Дойча, в которой важно знать не все значения функции, а только некоторые её свойства.

Нахождение периода функции в алгоритме

Пусть $F$ — функция с неизвестным периодом $r:$

$F:|x,0\rangle \ \rightarrow |x,f(x)\rangle \ f:Z\rightarrow Z_{2^{m}}\ r<2^{n}$.

Чтобы определить период $r$, требуются два регистра с размерами $2n$ и $m$ кубитов, которые должны быть первоначально в состоянии $|0,0\rangle$.

На первом этапе выполняется односторонняя суперпозиция всех базисных векторов первого регистра с использованием оператора $U$ следующего вида:

$U|0,0\rangle \ =\sum \limits _{i=0}^{N-1}c_{i}|i,0\rangle \$, где $|c_{i}|={\frac {1}{\sqrt {N}}}$ и $N=2^{2n}$.

Здесь используется псевдопреобразование Адамара $H_{1}={\begin{bmatrix}2&1\\1&1\end{bmatrix}}$. Применяя $F$ к текущему состоянию, получаем:

$|\psi \rangle =FH_{1}|0,0\rangle =F{\frac {1}{2^{n}}}\sum \limits _{i=0}^{N-1}|i,0\rangle ={\frac {1}{2^{n}}}\sum \limits _{i=0}^{N-1}|i,f(i)\rangle$.

Измерение второго регистра с результатом $k=f(s)$, где $s<r$, приводит состояние к:

$|\psi '\rangle =\sum \limits _{j=0}^{[N/r]-1}c_{j}'|rj+s,k\rangle ,\qquad$ где $c_{j}'=\left[{\frac {N}{r}}\right]^{-1/2}$.

После измерения состояния $|\psi '\rangle$ первый регистр состоит только из базисных векторов вида $|rj+s\rangle$ таких, что $f(rj+s)=f(s)$ для всех $j$. Поэтому он имеет дискретный однородный спектр. Невозможно прямо получить период $r$ или кратное ему число, измеряя первый регистр, потому что здесь $s$ — случайная величина. Здесь применяется дискретное преобразование Фурье вида

$\mathrm {DFT:} |x\rangle \rightarrow {\frac {1}{\sqrt {N}}}\sum \limits _{y=0}^{N-1}e^{{\frac {2\pi i}{N}}xy}|y\rangle$ на регистр, так как вероятность спектра в преобразованном состоянии инвариантна относительно смещения (преобразованию поддаются только фазы, а не абсолютные значения амплитуд).

$|\psi ''\rangle =\mathrm {DFT} |\psi '\rangle =\sum \limits _{i=0}^{N-1}c_{i}''|i,k\rangle$.

$c_{i}''={\frac {\sqrt {r}}{N}}\sum \limits _{j=0}^{p-1}\exp \left({\frac {2\pi i}{N}}i(jr+s)\right)={\frac {\sqrt {r}}{N}}e^{\varphi _{i}}\sum \limits _{j=0}^{p-1}\exp \left({\frac {2\pi i}{N}}ijr\right)$,

где $\varphi _{i}=2\pi i{\frac {is}{N}}\quad$ и $\quad p=\left[{\frac {N}{r}}\right]$.

Если $N=2^{2n}$ кратно $r$, тогда $c_{i}''={\frac {e^{\varphi _{i}}}{\sqrt {r}}}$, если $i$ кратно ${\frac {N}{r}}$, и $c_{i}''=0$ в противном случае. Даже если $r$ не является степенью числа 2, то спектр $|\psi ''\rangle$ показывает отдельные пики с периодом ${\frac {N}{r}}$, потому что

$\lim _{n\to \infty }{\frac {1}{n}}\sum \limits _{k=0}^{n-1}e^{2\pi ik\alpha }={\begin{cases}1\ \ ,\alpha \in Z\\0\ \ ,\alpha \notin Z\\\end{cases}}$

Для первого регистра используется $2n$ кубитов, когда $r<2^{n}$, потому что это гарантирует по крайней мере $2^{n}$ элементов в приведённой сумме, и таким образом ширина пиков будет порядка $O(1)$.

Если теперь вычислить первый регистр, то получится значение $c$, близкое к ${\frac {\lambda N}{r}}$, где $\lambda \in Z_{r}$. Оно может быть записано как ${\frac {c}{N}}=c\cdot 2^{-2n}\approx {\frac {\lambda }{r}}$. Это сводится к нахождению аппроксимации ${\frac {a}{b}}$, где $a,b<2^{n}$, для конкретного числа двоичной точки $c\cdot 2^{-2n}$. Для решения этой задачи используются цепные дроби.

Поскольку форма рационального числа не единственна в своём роде, то $\lambda$ и $r$ определяются как ${\frac {a}{b}}={\frac {\lambda }{r}}$, если $\operatorname {gcd} (\lambda ,r)=1$. Вероятность того, что оба числа $\lambda$ и $r$ просты, больше чем ${\frac {1}{\ln r}}$, поэтому, чтобы вероятность успеха была близка к единице, необходимо только $O(n)$ попыток.

Дискретное логарифмирование

Другая математическая задача, дискретное логарифмирование, часто применяющаяся для создания систем асимметричной криптографии, также является уязвимой для квантового алгоритма, предложенного Шором в той же статье.

Литература

• Feynman R. Simulating Physics with Computers (англ.) // International Journal of Theoretical Physics — Springer Science+Business Media, 1982. — Vol. 21, Iss. 6 / 7. — P. 467–488. — ISSN 0020-7748; 1572-9575 — doi:10.1007/BF02650179
• Feynman R. Quantum mechanical computers (англ.) // Foundations of Physics / Gerard 't Hooft — Springer Science+Business Media, 1986. — Vol. 16, Iss. 6. — P. 507–531. — ISSN 0015-9018; 1572-9516 — doi:10.1007/BF01886518
• D B., AN C., S D., J P., Beckman D., Chari A. N., Devabhaktuni S., Preskill J. Efficient networks for quantum factoring (англ.) // Physical Review A: covering atomic, molecular, and optical physics and quantum information — College Park: American Physical Society, 1996. — Vol. 54, Iss. 2. — P. 1034—1063. — ISSN 2469-9926; 2469-9934; 2469-9942 — doi:10.1103/PHYSREVA.54.1034 — PMID:9913575 — arXiv:quant-ph/9602016
• Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring (англ.) // Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on — IEEE, 1994. — P. 124–134. — ISBN 0-8186-6580-7 — doi:10.1109/SFCS.1994.365700
• 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 с.
• Федотов И. Е. Модели параллельного программирования. — М.: Солон-пресс, 2012. — 384 с.

Ссылки

• Shor P. W. Algorithms for quantum computation: discrete logarithms and factoring // Foundations of Computer Science : Conference Publications. — 1994. — С. 124–134. — ISBN 0-8186-6580-7. — doi:10.1109/SFCS.1994.365700.
• Shor P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // Foundations of Computer Science : Conference Publications. — 1997. — С. 1484–1509.