Квантовые компьютеры. С точки зрения традиционного программиста-математика. Часть 7 — Заключительная03.11.2023 12:00

Ссылка на предыдущую шестую часть

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

В заключительной части попробуем разобраться в этом замечательном алгоритме, который в скором будущем погубит нашу цивилизацию, лишь только появятся мощности с достаточным количеством кубит для практической реализации алгоритма. Я попытаюсь упростить изложение и опустить некоторые выкладки, но сама суть алгоритма должна сохраниться через эти упрощения. Разобьем изложение на несколько этапов. Ну, начнем.

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

Разрешите представить Вам этот новый прекрасный квантовый гейт — QFT. Этот гейт преобразует n-кубитный регистр и обладает рядом замечательных свойств, с которыми мы сейчас разберемся.
Вы еще не забыли, что квантовые операции можно задавать матрицами?

$\left( \begin{array}{cccc} \omega_{00} & \omega_{01} & \cdots & \omega_{0\,n-1}\\ \omega_{10} & \omega_{11} & \cdots & \omega_{1\,n-1}\\ \vdots &\vdots & \ddots &\vdots\\ \omega_{n-1\,0} &\omega_{n-1\,1} & \cdots & \omega_{n-1\,n-1} \end{array} \right)$

Если у нас есть регистр в некотором произвольном квантовом состоянии:

$a_0|0\rangle+a_1|1\rangle+\cdots+a_{n-1}|n-1\rangle$

То мы можем записать действие квантовой операции, как умножение матрицы этой операции на вектор, соответствующий этой операции.

$\left(\begin{array}{cccc} b_0\\ b_1\\ \vdots \\ b_{n-1}\end{array} \right)=\left( \begin{array}{cccc} \omega_{00} & \omega_{01} & \cdots & \omega_{0\,n-1}\\ \omega_{10} & \omega_{11} & \cdots & \omega_{1\,n-1}\\ \vdots &\vdots & \ddots &\vdots\\ \omega_{n-1\,0} &\omega_{n-1\,1} & \cdots & \omega_{n-1\,n-1} \end{array} \right)\left( \begin{array}{cccc} a_0\\ a_1\\ \vdots \\ a_{n-1}\end{array} \right)$

И получим новое состояние квантового регистра

$b_0|0\rangle+b_1|1\rangle+\cdots +b_{n-1}|n-1\rangle$

Надеюсь, умножать матрицу на вектор вы еще не разучились. Если разучились, то напомню формулу

$b_k=\sum_{m=0}^{n-1}\omega _{km}a_m$

Нам это стало неудобно делать, так как матрицы разрастались экспоненциально от размера квантового регистра. Но теперь как раз тот самый удобный случай, когда лучше всего описать наш гейт матрицей.
Построить матрицу QFT не сложно. Допустим нам нужно построить матрицу QFT размера $n\times n$ . Будем такой квантовый оператор обозначать QFT_n
Сначала мы берём комплексную константу

$\omega=e^{\frac{2\pi}{n}i}$

И строим матрицу QFT_n вот таким незатейливым способом

$\frac{1}{\sqrt{n}}\left( \begin{array}{cccc} 1 & 1 & 1 & 1 & \cdots & 1\\ 1 & \omega & \omega^2 & \omega^3 & \cdots & \omega^{n-1}\\ 1 & \omega^2 & \omega^4 & \omega^6 & \cdots & \omega^{2 ( n-1 )}\\ 1 & \omega^3 & \omega^6 & \omega^9 & \cdots & \omega^{3 ( n-1 )}\\ \vdots &\vdots &\vdots &\vdots & \ddots &\vdots\\ 1 & \omega^{n-1} & \omega^{2 ( n-1 )} & \omega^{3( n-1 )} & \cdots & \omega^{(n-1)(n-1)} \end{array} \right)$

Действительно, не сложно. Получается, что каждый элемент этой матрицы вычисляется по формуле

$\omega _{km}=\omega^{k\times m}$

Ну что же, давайте вычислим матрицу для квантовой операции QFT_2
Сначала найдем $\omega$ для n=2

$\omega=e^{\frac{2\pi}{n}i}=e^{\frac{2\pi}{2}i}=-1$

Значит

$\omega _{km}=\omega^{k\times m}= -1^{k\times m}$

И матрица получится

$\frac{1}{\sqrt {2}}\left( \begin{array}{cccc} 1 & 1\\ 1 & -1\end{array} \right)$

Это было слишком просто. Заметим, что эта матрица такая же какая была у однокубитной операции Адамара, мы эту матрицу рассматривали во второй части.
Ну, а давайте построим QFT_4
Сначала найдем $\omega$ для n=4

$\omega=e^{\frac{2\pi}{n}i}=e^{\frac{2\pi}{4}i}=i$

Значит

$\omega _{km}=\omega^{k\times m}= i^{k\times m}$

И матрица получится

$\frac{1}{2}\left( \begin{array}{cccc} 1 & 1 & 1 & 1\\ 1 & i & -1 & -i\\ 1 & -1 & 1 & -1\\ 1 & -i & -1 & i\end{array} \right)$

Так как это не просто матрица, а матрица квантового оператора, то для такого оператора, в силу свойства обратимости, обязан существовать обратный оператор. Он тоже выглядит несложно, это та же самая матрица, только построенная с другой константой $\omega$ , обозначим ее как $\omega^{\dagger}$ вычисляется по формуле

$\omega^{\dagger }=e^{-\frac{2\pi}{n}i}=\omega^*=\omega^{-1}$

То есть это просто комплексно-сопряженное число по отношению к начальной $\omega$ и одновременно это еще и обратное число $\frac{1}{\omega}$
Ну, а значит элементы матрицы обратного оператора вычисляются так:

$\omega^{\dagger}_{km}=(\omega^{\dagger})^{ k\times m}=\omega^{ -k\times m}$

Вам наверняка уже не терпится проверить, действительно ли эта обратная матрица будет обратной?
Проверить легко умножим матрицу QFT на обратную $QFT^{\dagger}$
Если вы забыли формулу умножения матриц, то вот она: элементы $c_{kl}$ матрицы С произведения двух матриц $С=A\times B$ вычисляются по формуле

$c_{kl}=\sum_{j=0}^{n-1}a_{kj}b_{jl}$

Подставляем наши омеги от прямой и обратной матрицы:

$c_{kl}=\sum_{j=0}^{n-1}\omega^{k\times j}\omega^{-j\times l}=\sum_{j=0}^{n-1}\omega^{( k-l )\times j}$

И получается, если k=l то под суммой будут простые единицы, суммируем их и получаем n $c_{ll}=n$
А если $k\neq l$ то у нас в результате такой суммы выйдет ноль. Почему? Визуально эти комплексные числа торчат из начала координат комплексной плоскости в разные стороны, как ровные спицы колеса, с одинаковым интервалом.

Они полностью уравновешивают друг друга, и сумма их равнодействия будет в итоге нулевая. Интуитивно понятно, но если хотите более математического обоснования, то оно следующее: Пусть, $m<n,\quad и\quad \sum_{j=0}^{n-1}\omega^{m \cdot j}=C$ для нашего $\omega=e^{\frac{2\pi}{n}i}$ Для такого числа легко непосредственно проверить, что $\omega^m\neq1$ , $\omega^n=1$ Умножим эту сумму на $\omega^m$ , тогда

$\omega^mC=\sum_{j=0}^{n-1}\omega^{m \cdot (j+1)}=\sum_{j=1}^{n}\omega^ { m \cdot j } =\omega^n+\sum_{j=1}^{n-1}\omega^{m \cdot j}=1+\sum_{j=1}^{n-1}\omega^{m \cdot j}=\sum_{j=0}^{n-1}\omega^{m \cdot j}=C$

Так, как $\omega^m\neq1$ , значит такое равенство возможно только, если C=0

Получаем, что наша матрица C имеет только диагональные элементы равные n. Но это же не единичная матрица, где по диагонали должны стоять единицы. Где же обратимость? А дело в том, что мы забыли про нормировочный коэффициент $\frac{1}{\sqrt { n }}$ который стоял перед каждой матрицей. Вот и вышла единичная матрица в результате произведения. Обратимость проверили.

Резюме: В нашем арсенале появился новый квантовый гейт QFT_n . Он задается матрицей, элементы которой вычисляются по формуле

$\omega _{km}=\frac{1}{\sqrt { n }}\omega^{k\times m} ,\quad где\quad \omega =e^{\frac{2\pi}{n}i}$

Для этого гейта существует обратный гейт $QFT_n^{\dagger}$
Он задается матрицей, элементы которой вычисляются по формуле

$\omega _{km}=\frac{1}{\sqrt { n }}\omega^{-k\times m}$

Нахождение периода функции

Разберем сначала конкретный пример, а потом попробуем сформулировать общий подход.
Возьмем квантовый регистр, который может иметь сто возможных состояний. Допустим амплитуды всех состояний равны 0, кроме состояний $|2\rangle ,|7\rangle ,|12\rangle ,\dots ,|92\rangle ,|97\rangle$ которые имеют одинаковые амплитуды, то есть равновероятны. Эти состояния идут с периодом 5 и с началом в 2. То есть, если опустить нормировочный коэффициент, мы имеем состояние этого регистра:

Ну, или перепишем это состояние в виде такой суммы:

$\sum_{j=0}^{19}|2+5j\rangle$

Подадим это состояние в гейт $QFT_{100 }$ для этого воспользуемся формулой умножения матрицы на вектор:

$b_k=\sum_{m=0}^{n-1}\omega _{km}a_m$

Здесь, в нашем частном случае a_m=1 , если m=2+5j , где j- натуральное число от 0 до 19. Для остальных m a_m=0
$\omega _{km}=\omega^{k\times m}$ по определению матрицы $QFT_{100 }$ , где $\omega=e^{\frac{2\pi}{100 }i}$
Подставляем все это в формулу умножения матрицы на вектор:

$b_k=\sum_{m=0}^{99}e^{\frac{2\pi}{100 } i\cdot k\cdot m}a_m= \sum_{j=0}^{19}e^{\frac{2\pi}{100 } i\cdot k\cdot (2+5j)}= e^{\frac{2\pi}{100 }i\cdot k\cdot 2}\sum_{j=0}^{19}e^{\frac{2\pi}{100 } i\cdot k\cdot 5j}\quad\quad(1)$

Ну и видим опять знакомую сумму. Сразу замечаем, что если $5\cdot k$ кратно 100, то есть $5\cdot k=100, 200, 300...$ то выражение под суммой сократится и все это выражение будет равно единице

$e^{\frac{2\pi}{100 } i\cdot k\cdot 5j}=1,\,k\cdot 5=\{100,200,300,\dots\}$

Но если $5\cdot k$ не кратно 100, то мы опять получаем «спицы колеса» на комплексной плоскости, которые в сумме уравновешивают друг друга и дают 0. Поэтому в итоге, после действия операции $QFT_{100 }$ мы получим состояние, где $b_k=e^{\frac{2\pi}{100 }i\cdot k\cdot 2}$ если $k\cdot 5=\{100,200,300,\dots\}$ и амплитуда будет 0 в остальных случаях.
То есть итоговое состояние системы после операции $QFT_{100 }$ будет

$|2\rangle +|7\rangle +|12\rangle +\dots +|92\rangle +|97\rangle \xrightarrow{QFT_{100 }}$ $|0\rangle+e^{\frac{2\pi}{100 }i\cdot 40}|20\rangle+e^{\frac{2\pi}{100 }i\cdot 80}|40\rangle+e^{\frac{2\pi}{120 }i\cdot 120}|60\rangle+e^{\frac{2\pi}{100 }i\cdot 160}|80\rangle$

Что будет, если после этой операции мы измерим результат. С какой вероятностью мы получим, к примеру $|60 \rangle$ ? Как всегда, вероятность равна квадрату амплитуды, правда мы опустили нормировочный коэффициент, но это не так важно, нам главное увидеть как соотносятся вероятности. И какой у нас квадрат амплитуды?

$|e^{\frac{2\pi}{100 }i\cdot k\cdot 2}|^2=1$

То есть несмотря на разные амплитуды, квадраты их одинаковые, и, значит, после измерения регистра, мы можем с равной вероятностью получить 0, 20, 40, 60 или 80.
А теперь сформулируем общий случай. Допустим у нас есть регистр, который может принимать n состояний. В примере выше n был равен 100.
Регистр имеет состояние, где все амплитуды равны 0, кроме состояний с периодом , которые являются равновероятными

$|c\rangle +|c+r\rangle +|c+2r\rangle +\dots +|c+(n/r-2)r\rangle +|c+(n/r-1)r\rangle =\sum_{j=0}^{n/r-1}|c+r\cdot j\rangle$

где с — это смещение от 0 до r-1, в примере выше смещение было 2. В этом случае, после подачи такого состояния в QFT_n мы получим новое состояние

$|0\rangle +\phi\cdot |n/r\rangle +\phi^2\cdot |2n/r\rangle +\dots +\phi^{r-1}|(r-1)n/r\rangle =\sum_{j=0}^{r-1}\phi^j\cdot |j \cdot n/r\rangle$

Где $\phi$ — это какая-то фаза, связанная с начальным смещением c, она нам не особо интересна, так как $|\phi|^2=1$ и эта фаза не влияет на итоговые вероятности после измерения состояния.
И после измерения итогового состояния регистра, мы можем с равной вероятностью получить следующие значения регистра

$0;\,n/r;\,2n/r\dots$

Теперь, приступим к самой задаче. Допустим у нас есть произвольная периодическая функция, заданная для аргументов от 0 до 99

f(x)=f(x+r) , для всех x. При этом важно также допустить, что внутри периода, все значения уникальны. Задача, найти этот период r. Визуально выглядит просто. Мы видим повторяющуюся фигуру и интуитивно можем определить, что r=5 . Но если у нас отрезок не от 0 до 99, а от 0 до $10^{100}-1$ . Да и значение периода также не такое уж маленькое, порядка $10^{50}$ . Единственная надежда наивного классического алгоритма, если нам ничего не известно о природе функции, это перебирать по порядку все значения функции, пока не наткнемся на повторяющееся значение. И сколько нам придется перебрать? Если период порядка $10^{50}$ , то примерно столько перебрать значений и придется. Для каждого вычислять значение функции и надеяться на совпадение. Есть также вероятностный алгоритм, где, благодаря парадоксу дней рождений можно снизить количество перебираемых значений до $10^{25}$ , но по-прежнему это очень большое число. То есть, если разрядность функции это N, то сложность классического алгоритма для решения этой задачи является экспоненциальной O(2^N) . Что может дать нам квантовый алгоритм? Как обычно, мы можем гейтом Адамара получить равновероятную суперпозицию всех аргументов x.

$|0\rangle+|1\rangle+...+|99\rangle$

Далее мы эти аргументы подаем в черный ящик, который реализует нашу периодическую функцию f (x) и получим состояние, представляющее суперпозицию $|x\rangle \otimes |f(x)\rangle$ (для нашего конкретного случая, заданного на графике):

Ну, а теперь напрашивается дальнейшим действием измерить ту часть регистра, где результат f(x) . Действительно, какое бы мы не получили при этом значение, спутанные с этим значением состояния, будут аргументами функции, дающие этот результат. А так как внутри периода значение функции уникально, то мы получим суперпозицию аргументов идущие через равный период.

Например, мы получили в результате измерения f(x)=3 . Значит, у нас будет на выходе x, равновероятная суперпозиция из значений: 1, 6, 11, …, 96.

$|1\rangle+|6\rangle+...+|96\rangle$

И мы свели эту задачу к прошлой. Ведь мы получили равновероятные состояние, идущие через равный период. Теперь мы можем подать это состояние в QFT_n , измерить результат и получить случайным образом какое-то из чисел $k\cdot\frac{n}{r}=k\cdot\frac{100}{5}=k\cdot 20$
То есть числа: 0, 20, 40, 60, 80.
Проведя несколько итераций, у нас будет достаточно таких значений, чтобы вычислить на обычном классическом компьютере наибольший делитель этих полученных значений 20.
А имея это число, мы можем вычислить период функции, разделив 100 на 20 и получить ответ 5.
Теперь приведем полную квантовую цепь, с участием также классического компьютера, для нахождения неизвестного периода неизвестной периодической функции

Ну и небольшое замечание. Наверняка внимательные читатели заметили некоторое лукавство. Мы взяли регистр, который может принимать n различных состояний и, вдруг, случайно так получилось, что этот n делится на неизвестный период r. В формуле (1) мы этим даже воспользовались. Да, в реальности мы так угадать не сможем. А значит наши «спицы колеса» в суммах не сойдутся в целый круг и не занулятся в своей сумме, что в формуле (1). Вторая проблема, что в формуле (1) не получаться такие «диагональные» состояния, где $r\cdot k$ будет кратно n. В итоге мы получим приблизительный ответ, но это хороший вариант. Можно увидеть, что амплитуды перекрестных состояний будут довольно малы, в сравнении с амплитудами диагональных состояний, а при достаточно больших n стремятся к нулю. Мы можем взять $n\gg r^2$ . Если значение n превышает $r^{2}$ , то мы действительно имеем ненулевую вероятность получить неверный результат. Но это событие при нескольких порядках этой разницы переходит в разряд невероятных. Итак, делаем допущение, что $n\gg r^2$ А теперь, как же быть с алгоритмом? В самом алгоритме не изменится ничего. Если ранее алгоритм выдавал нам некоторое целые числа $k\cdot\frac{n}{r}$ с которыми мы могли иметь дело и искать их НОД. То теперь алгоритм выдает некоторое число L, которое приблизительно равно $k\cdot\frac{n}{r}$ , а это значит

$\frac{L}{n}\sim\frac{k}{r}$

Левая часть нам известна, ведь L мы получили в результате работы алгоритма, а n задали с самого начала. И далее задача сводится к аппроксимации левой дроби такой дробью, чтобы r^2<n , что можно проделать на классическом компьютере методом, так называемых «цепных дробей». Этот метод также потребует некоторых допущений.
Получив в итоге ответ в виде периода мы всегда можем в одно-два действия провести проверку на классическом компьютере, действительно ли полученное значение является периодом и соблюдаются ли все допущения. И если нам невероятно не повезло, то мы просто можем запустить еще один раунд квантового алгоритма и получить в итоге правильное значение.
А значит, что мы можем решить задачу нахождения периода, даже в том случае, когда n не делится нацело на период r

Факторизация числа

Теперь, собственно, к задаче, которую должен решить алгоритм Шора. У нас есть неизвестное целое число $N=p\cdot q$ это число имеет размер n бит. p и q это неизвестные простые числа и наша задача их найти. Пример: N=77. Перебирая все возможные делители по порядку, мы обнаружим, что число N делится на 7, что позволяет нам установить второй делитель 11. Казалось бы, задача несложная. Но что, если N имеет размер n=1024 бита? В этом случае делители будут иметь оценочно длину 512 бит. И нам, чтобы попробовать их простым перебором, надо совершить $2^{512}$ операций, что у современного суперкомпьютера займет времени больше, чем возраст нашей вселенной. То есть операция факторизации имеет экспоненциальную сложность O(2^n) Но если наоборот, мы знаем, чему равны делители p и q, то мы легко можем установить число N, перемножив их «столбиком» за время не более чем O(n^2) , а на самом деле существуют и еще более эффективные алгоритмы умножения больших чисел. На этой сильно несимметричности сложностей прямой и обратной задачи факторизации основан метод шифрования RSA лежащий в основе протоколов SSL, TLS и др. И если бы нам удалось решить задачу факторизации эффективным способом, хотя бы с не экспоненциальной, а полиномиальной сложностью, нашему безопасному интернету, каким мы его знаем сегодня, пришел бы конец.

Сразу предупреждаю, в математических выкладках ниже я пожертвовал строгостью. Это не математические выкладки, а просто ход мыслей, который иллюстрируется формулами. Это позволяет несколько упростить повествование, но при этом передать суть.

Как будем решать. Очевидно, что нам бы найти хотя бы один делитель, тогда вычислить второй делитель уже сложности не составит.
План решения будет следующий:

Свести задачу факторизации числа N к поиску нетривиальных корней уравнения $x^2\mod N = 1$
Свести задачу поиска нетривиальных корней уравнения $x^2\mod N = 1$ к задаче нахождения периода функции $f(x)=b^x\mod N$
Решить задачу нахождения периода на квантовом компьютере.

1-я часть плана

Допустим, у нас есть число a и мы, возводя его в квадрат, вдруг обнаружили, что для нашего числа N, которое нам надо факторизовать.

$a^2\mod N = 1$

mod это операция по модулю. Если вы помните эту алгебру по модулю, то также помните, что возводить числа по модулю даже в очень большие степени довольно легко.

У этого уравнения есть тривиальные решения. Например, a=1 . Такое число a при возведении в квадрат будет удовлетворять уравнению.
Второе тривиальное решение, это a=-1 , ну, или учитывая, что мы работаем по модулю N, это a=N-1 . Такое число a при возведении в четную степень также будет удовлетворять уравнению.
Остальные решения называем нетривиальными.
Например, для нашего числа 77, мы обнаружили, что

$43^2=1849=77\cdot 24+1=1\mod 77$

То есть a=43 является нетривиальным корнем уравнения.
Что это нам даёт?

$a^2-1\mod N=0$

Это значит, что мы можем переписать выражение в виде

$(a-1)(a+1)\mod N=0$ $(a-1)(a+1)= N\cdot k$

Где k- какое-то целое число.
Но мы помним, что $N=p\cdot q$ , а значит

$(a-1)(a+1)= p\cdot q\cdot k$

Выражение справа делится и на p и на q. И так как p, q это по условию задачи простые числа, то одно из двух чисел (a-1);(a+1) делится на p, а другое делится на q. Может ли какое-то из этих чисел делится и на p и одновременно на q? Нет. От противного, возьмем, к примеру первое число и допустим, что оно делится и на p и одновременно на q.

$(a-1)=p\cdot q\cdot k=N\cdot k$

Значит

$a=N\cdot k+1$ $a=1\mod N$

А мы в условии задачи поставили, что , это нетривиальное решение уравнения, т.е. это не то, где $a=\mp 1\mod N$
Значит одно из этих чисел делится на p, пусть это будет число a-1
А другое число a+1 делится на q.
А значит у этих чисел и числа N существуют наибольшие общие делители, не равные единице
$НОД(a-1, N)=p;\,НОД(a+1, N)=q$
У нас есть эффективные алгоритмы для вычисления НОД, например алгоритм Евклида, который работает за полиномиальное время. Это даже забавно: мы не можем эффективно решить задачу поиска делителей числа, но очень легко можем находить наибольший общий делитель у двух разных чисел. И мы воспользуемся этой парадоксальной ситуацией. Нам известны a и N. Значит мы легко и эффективно найдем и p и q, то есть решим исходную задачу факторизации.
Но это все были общие формулы, а что с нашим конкретным примером?
Мы установили, что a=43 является нетривиальным решением уравнения:

$a^2\mod N = 1$

Для N=77, тогда

$(a-1)(a+1)=(43-1)(43+1)=42\cdot 44$

И нам надо найти НОД (42,77) и НОД (44,77)
И мы легко это сделаем тем же алгоритмом Евклида
НОД (42,77)=7; НОД (44,77)=11
И вот мы и разложили число 77 на простые множители $77=11\cdot 7$

Итак, первым шагом мы свели задачу факторизации числа $N=p\cdot q$ к задаче нахождения такого целого числа a, что является нетривиальным решением уравнения

$a^2\mod N = 1\quad\quad(2)$

и далее будем решать эту задачу.

2-я часть плана

Рассмотрим метод поиска таких чисел, которые являются нетривиальными корнями уравнения (2). Возьмем просто любое целое число b, начнем возводить его в разные степени x и будем вычислять $b^x\mod N$
Во первых, очевидно, что область значений функции $f(x)=b^x\mod N$ это числа от 0 до N-1. А так как область определения этой функции это все целые числа, то просто обязаны существовать два различных значения x_1,x_2 такие, что f(x_1)=f(x_2)
Но для таких значений получается, что и

$f(x_1+1)=bb^{x_1}\mod N=bf(x_1)=bf(x_2)=f(x_2+1)$

И далее легко видеть, что f(x_1+2)=f(x_2+2) и далее. То есть функция f (x) является периодической.
А далее имеем еще более интересное утверждение. Если f (0)=1 и при этом наша функция периодическая, значит ровно через один период T, мы придем к такой ситуации, что f (T)=1. А значит, для такого T $f(T)=b^T\mod N=1$
Допустим, нам повезло и T оказалось чётным числом. Тогда задача поиска будет решена, ведь

$f(T)=(b^{T/2})^2\mod N=1$

А мы, напомню, ищем такое число a, что удовлетворяет условию (2). То есть решением будет $a=b^{T/2}$
А если нам не повезёт и T окажется нечётным числом? Ничего страшного, просто меняем b и начинаем сначала. Алгебра утверждает, что период будет четным для половины целых чисел, так что вероятность угадать число с четным периодом резко возрастает с числом попыток.
Попробуем наш метод на практике с нашим примером — числом 77. Возьмем любое число b, например, для удобства возведения в степень, пусть это будет число 2.
И начнем вычислять нашу функцию $f(x)=2^x\mod 77$ пока не получим 1

Итак, период функции равен 30. он чётный и нам «повезло». Значит надо взять

$a=2^{30/2}=2^{15}=32768$

Заметим, что если

$a^2\mod N = 1,\quadто\quad(a\mod N)^2\mod N = 1$

А значит, мы можем взять в работу число:

$32768\mod 77=43$

Заметьте, что работая по модулю и получив четный период функции, мы просто можем взять в качестве a значение этой функции в точке T/2. Посмотрите на таблицу выше: f(30/2)=f(15)=43 .
А 43, это именно то число, что мы уже использовали выше, когда искали наибольшие общие делители НОД (77,44), НОД (77,42)

Итак, вторым шагом мы свели задачу факторизации числа $N=p\cdot q$ к задаче нахождения периода периодической функции $f(x)=b^x\mod N$ для произвольно взятого числа b, такого, чтобы этот период получился четным целым числом.
На самом деле я немного упростил изложение. b не совсем произвольное, требуется, чтобы НОД (b, N)=1. Без этого требования выкладки выше не работают, мы просто жертвуя строгостью выкладок опустили этот момент. Но если бы у нас даже вышло НОД (b, N)>1 то мы бы сорвали джек-пот, ведь получившийся делитель является одним из делителей числа N и мы разом решаем исходную задачу факторизации.

3-я часть плана

Ну, вы уже наверняка догадались, к чему мы ведём. Ведь мы уже научились находить период функции в первом разделе этой статьи. Нам нужно собрать квантовую схему, которая будет генерировать результат функции $f(x)=b^x\mod N$ , что не представляет труда сделать на элементарных логических квантовых цепях. И далее вычисляем период этой функции по алгоритму выше.
Если период получился четным, а точнее, когда, после нескольких попыток, мы, наконец, получим четный период, то на классическом компьютере вычисляем a=f(T/2)
После этого вычисляем делители числа N на классическом компьютере алгоритмом Евклида.

p=НОД(a-1,N) q=НОД(a+1,N)

И исходная задача факторизации решена.
Приведем полную схему алгоритма.

Алгоритм Шора пока ещё не осуществим с какими-то практическими целями. С 2015 года NIST рекомендует минимум 2048-битные ключи для RSA для криптографии. Это значит, что для взлома такого ключа потребуется минимум 4096 кубитный компьютер: 2048 кубит для аргумента, 2048 кубит для результата функции. А самые мощные сегодня квантовые компьютеры, это 76-кубитный квантовый компьютер Jiuzhang и 54-кубитный Sycamore. В России самый мощный квантовый компьютер имеет разрядность в 16 кубит. Но до конца 2024-го года обещают догнать 100 кубит. На практике в 2001 году, работоспособность алгоритма Шора была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами