03.11.2023 08:57
java_prog 6 5000 Источник

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

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

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

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

Разрешите представить Вам этот новый прекрасный квантовый гейт - 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. То есть, если опустить нормировочный коэффициент, мы имеем состояние этого регистра:

|2\rangle +|7\rangle +|12\rangle +\dots +|92\rangle +|97\rangle

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

\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, кроме состояний с периодом r, которые являются равновероятными

|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 (для нашего конкретного случая, заданного на графике):

|0\rangle\otimes|5\rangle+|1\rangle\otimes|3\rangle+...+|99\rangle\otimes|2\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, что можно проделать на классическом компьютере методом, так называемых "цепных дробей". Этот метод также потребует некоторых допущений.

Получив в итоге ответ в виде периода r мы всегда можем в одно-два действия провести проверку на классическом компьютере, действительно ли полученное значение является периодом и соблюдаются ли все допущения. И если нам невероятно не повезло, то мы просто можем запустить еще один раунд квантового алгоритма и получить в итоге правильное значение.

А значит, что мы можем решить задачу нахождения периода, даже в том случае, когда 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 и др. И если бы нам удалось решить задачу факторизации эффективным способом, хотя бы с не экспоненциальной, а полиномиальной сложностью, нашему безопасному интернету, каким мы его знаем сегодня, пришел бы конец.

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

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

  1. Свести задачу факторизации числа N к поиску нетривиальных корней уравнения x^2\mod N = 1

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

  3. Решить задачу нахождения периода на квантовом компьютере.

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. Может ли какое-то из этих чисел (a-1);(a+1) делится и на p и одновременно на q? Нет. От противного, возьмем, к примеру первое число и допустим, что оно делится и на p и одновременно на q.

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

Значит

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

А мы в условии задачи поставили, что a, это нетривиальное решение уравнения, т.е. это не то, где 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 кубитами

Комментарии (6)


  1. dsoastro
    03.11.2023 15:32
    #26122488

    Вот здесь говорят что в 2024 году уже будет 1000 кубитов (https://habr.com/ru/companies/infotecs_official/articles/771480/). Не знаете, это какие-то другие кубиты (компьютер типа D-wave)?


    1. java_prog Автор
      03.11.2023 15:32
      #26122556

      Не, не знаю.


  1. murkin-kot
    03.11.2023 15:32
    #26122732

    Спасибо, интересно!

    Но можно ещё немного понаглеть? Не выложите ссылки на использованную в труде литературу?

    И за одно, сколь глубока связь между рядами Фурье и алгоритмом Шора? Или вообще рядами и периодическими функциями?


    1. java_prog Автор
      03.11.2023 15:32
      #26124132

      Основной литературой у меня с давних пор являлся https://doi.org/10.4213/lkn30

      Но там чтиво тяжеловатое. Как я упомянул в первой статье, моей задачей было изложить самые "интересные" моменты в более понятном виде для программистов-математиков.

      Про глубину связи вопрос не очень понял. Если у нас функция является суперпозицией нескольких периодических функций, то QFT, как и разложение в ряд Фурье выделит спектр этих функций. Но это все мало имеет отношение к квантовым вычислениям, это вам про DFT почитать, к примеру


      1. murkin-kot
        03.11.2023 15:32
        #26126210

        Спасибо за ссылку.

        Про выделение спектра - функция же периодическая, значит в спектре должен быть некий пик, показывающий тот самый период. Я думал как-то так, хотя в теории я пока сам плаваю.


  1. vlad1953
    03.11.2023 15:32
    #26124328
    +1

    В ваших статьях вы достаточно хорошо попытались рассказать про квантовые вычисления непросто общими фразами, а с применением конкретной математики. Очень редко на русском языке, не только в популярных статьях, но и во многих книгах изданных за последние годы, можно найти такую же хорошую попытку как сделали вы объяснить работу квантовых алгоритмов.

    Со своей стороны могу порекомендовать книгу напечатанную издательством "Питер" "Программирование квантовых компьютеров. Базовые алгоритмы и примеры кода". Все примеры, которые есть в этой книге можно непосредственно выполнить в браузере по адресу https://oreilly-qc.github.io/ . Выполнить эти примеры можно именно в браузере и не требуется запускать какие-либо внешние инструменты. При желании можно изменить эти программы и посмотреть, что получится. Хотя в этих примерах ( так как они выполняются интерактивно) используется несколько необычный язык на основе javascript сути это не меняет, так как показан физический смысл выполняемых действий. Но, однако, здесь же рядом для интересующихся приведены соответствующие программы на Qiskit - самом популярном языке для квантовых вычислений.

    Очень полезные материалы можно найти на сайтах Дэвида Кемпа. Например по следующему адресу https://davidbkemp.github.io/QuantumComputingArticle/ . И вообще весь его github https://davidbkemp.github.io/ .

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