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

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

Об алгоритме


 Значимость алгоритма заключается в том, что с его помощью (при использовании квантового компьютера с несколькими сотнями логических кубитов) становится возможным взлом криптографических систем с открытым ключом. К примеру, RSA использует открытый ключ M,M, являющийся произведением двух больших простых чисел. Один из способов взломать шифр RSA — найти множители M.M. При достаточно большом MM это практически невозможно сделать, используя известные классические алгоритмы. Наилучшие из известных классических детерминированных доказанных алгоритмов факторизации, такие как метод квадратичных форм Шенкса и алгоритм Полларда — Штрассена, требуют времени порядка M1/4.M1/4. Так же метод квадратичных форм Шенкса может работать за время порядка M1/5M1/5 если верна Гипотеза Римана. Среди вероятностных алгоритмов лидером факторизации является специальный метод решета числового поля, который способен с вероятностью 1/2 найти простой делитель за субэкспоненциальное время exp((329logM)1/3(loglogM)2/3).exp((329logM)1/3(loglogM)2/3). Алгоритм Шора, используя возможности квантовых компьютеров, способен произвести факторизацию числа не просто за полиномиальное время, а за время, не намного превосходящее время умножения целых чисел (то есть практически так же быстро, как происходит само шифрование). Таким образом, реализация масштабируемого квантового компьютера поставила бы крест на большей части современной криптографической защиты. (Речь не только о схеме RSA, прямо опирающейся на сложности факторизации, но и о других сходных схемах, которые квантовый компьютер способен взломать аналогичным образом.)
 Алгоритм Шора имеет вероятностный характер. Первый источник случайности встроен в классическое вероятностное сведение разложения на множители к нахождению периода некоторой функции. Второй источник появляется из необходимости наблюдения квантовой памяти, которое также даёт случайные результаты.

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


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

MM — число, которое мы хотим разложить на множители (оно не должно быть целой степенью нечётного числа);
NN — размер регистра памяти, который используется (не считая свалки). Битовый размер этой памяти n=log2Nn=log2N примерно в 2 раза больше размера MM. Точнее, $M^2tt — случайный параметр, такой что $1< t   Отметим, что tt, NN, MM — фиксированы. В алгоритме Шора используется стандартный способ сведения задачи разложения к задаче поиска периода rr функции для случайно подобранного числа tt.

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


 Минимальное rr такое, что tr=1 mod M,tr=1 mod M, — это порядок tt по модулю M.M.
 Порядок rr является периодом функции f(x)=tx mod M,f(x)=tx mod M, где x=0,1,2,...,N1.x=0,1,2,...,N1.
 Если можно эффективно вычислить rr как функцию tt, то можно найти собственный делитель MM за время, ограниченное полиномом от log2Mlog2M с вероятностью 1Mm1Mm для любого фиксированного mm.
 Предположим, что для данного tt период rr чётен (r0 mod 2)(r0 mod 2) и удовлетворяет условию

tr21 mod M.tr2≢1 mod M.
  Тогда

gcd(tr2+1,M)gcd(tr2+1,M) — собственный делитель M.M. Функция gcdgcd вычислима за полиномиальное время.
  Вероятность выполнения этого условия 112k1,112k1, где kk — число различных нечётных простых делителей MM, следовательно, 1212 в данном случае. Поэтому хорошее значение tt с вероятностью 1Mm1Mm найдётся за O(logM)O(logM) попыток. Самое длинное вычисление в одной попытке — вычисление tr2tr2.

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


 Для осуществления квантовой части алгоритма вычислительная схема представляет собой 22 квантовых регистра XX и YY. Первоначально каждый из них состоит из совокупности кубитов в нулевом булевом состоянии |0.|0.
 Регистр XX используется для размещения аргументов xx функции f(x).f(x). Регистр YY (вспомогательный) используется для размещения значений функции f(x)f(x) с периодом rr, подлежащим вычислению.
 Квантовое вычисление состоит из 4 шагов:

  • Первый шаг. На первом шаге с помощью , которая представляет собой преобразование кубита с помощью оператора H=12[1111],H=12[1111], первоначальное состояние |0$регистра|0$регистраXпереводитсявравновероятнуюсуперпозициювсехбулевыхсостоянийпереводитсявравновероятнуюсуперпозициювсехбулевыхсостоянийN.Второйрегистр.ВторойрегистрYостаётсявсостоянииостаётсявсостоянии|0 \rangle .Витогеполучаетсяследующеесостояниедлясистемыдвухрегистров:Витогеполучаетсяследующеесостояниедлясистемыдвухрегистров:\frac{1}{\sqrt{N}}\sum\limits_{x=0}^{N-1}|x,0\rangle.$


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


1NN1x=0|x,0Uf1NN1x=0|x,tx mod M,1Nx=0N1|x,0Uf1Nx=0N1|x,tx mod M, то есть между состояниями обоих регистров образуется определённая связь.

  • Третий шаг. представляет собой унитарное преобразование состояния квантового регистра, описываемого NN-мерным вектором состояния вида N1x=0f(x)|x,x=0N1f(x)|x, в другое состояние N1k=0˜f(k)|k :k=0N1f~(k)|k :


QFTN:N1x=0f(x)|x N1k=0˜f(k)|k ,QFTN:x=0N1f(x)|x k=0N1f~(k)|k , где амплитуда Фурье-преобразования f(x)f(x) имеет вид
˜f(k)=1NN1x=0exp(2π i kx/N)f(x).f~(k)=1Nx=0N1exp(2π i kx/N)f(x).
 В двумерной x,kx,k-плоскости преобразование Фурье соответствует повороту осей координат на 90°, которое приводит к преобразованию шкалы xx в шкалу kk. На третьем шаге над состоянием первого регистра производится преобразование Фурье, и получается

1NN1x=0N1k=0exp(2π i kx/N)|k,tx mod M.1Nx=0N1k=0N1exp(2π i kx/N)|k,tx mod M.


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


|0,0I,|1,1I,,|N1,N1I,|0,0I,|1,1I,,|N1,N1I, где II — тождественный оператор на гильбертовом пространстве второго регистра YY.
  В результате получается |k,tk mod M$свероятностью|k,tk mod M$свероятностью\left | \frac{1}{N}\sum\limits_{x:\ t^x \equiv t^k\ \mbox{mod}\ M}\exp(2\pi\ i\ kx/N) \right |^2.$
  На оставшейся части прогона работает классический компьютер:

  • Находится наилучшее приближение (снизу) к kN$сознаменателемkN$сознаменателемr'|kN dr|<12N.


  • Пробуем r в роли r:
    • Если r0 mod 2, то следует вычислить gcd(tr2±1,M).
    • Если r нечётно или если r чётно, но собственный делитель M не обнаружен, то следует повторить прогон O(loglogM) раз с тем же самым t. В случае отказа изменить t и начать новый прогон алгоритма.

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

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


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

F:|x,0 |x,f(x) f:ZZ2m r<2n.
  Чтобы определить период r, требуются два регистра с размерами 2n и m кубитов, которые должны быть первоначально в состоянии |0,0.
 На первом этапе выполняется односторонняя суперпозиция всех базисных векторов первого регистра с использованием оператора U следующего вида:

U|0,0 =N1i=0ci|i,0$,где|c_i| = \frac{1}{\sqrt{N}}иN=2^{2n}.ЗдесьиспользуетсяпсевдопреобразованиеАдамараH_1 = [2111]
.ПрименяяFктекущемусостоянию,получаем:| \psi \rangle =F H_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
|ψ=[N/r]1j=0cj|rj+s,k, где cj=[Nr]1/2.
  После измерения состояния |ψ первый регистр состоит только из базисных векторов вида |rj+s таких, что f(rj+s)=f(s) для всех j. Поэтому он имеет дискретный однородный спектр. Невозможно прямо получить период r или кратное ему число, измеряя первый регистр, потому что здесь s — случайная величина. Здесь применяется дискретное преобразование Фурье вида

DFT:|x1NN1y=0e2πiNxy|y на регистр, так как вероятность спектра в преобразованном состоянии инвариантна относительно смещения (преобразованию поддаются только фазы, а не абсолютные значения амплитуд).


|ψ=DFT|ψ=N1i=0ci|i,k.
ci=rNp1j=0exp(2πiNi(jr+s))=rNeφip1j=0exp(2πiNijr),
 где φi=2πiisN и p=[Nr].
  Если N=22n кратно r, тогда ci=eφir, если i кратно Nr, и ci=0 в противном случае. Даже если r не является степенью числа 2, то спектр |ψ показывает отдельные пики с периодом Nr, потому что

  \{lim\_\{n \{to \{infty\} \{frac\{1\}\{n\}\{sum\{limits\_\{k=0\}\^\{n-1\}e\^\{2\{pi ik \{alpha\} =
  \{begin\{cases\}
 \texttt   1\{ \{ ,\{alpha \{in Z  \{\{\\\texttt   0\{ \{ ,\{alpha \{notin Z \{\{
 \{end\{cases\}
 Для первого регистра используется 2n кубитов, когда r<2n, потому что это гарантирует по крайней мере 2n элементов в приведённой сумме, и таким образом ширина пиков будет порядка O(1).
 Если теперь вычислить первый регистр, то получится значение c, близкое к λNr, где λZr. Оно может быть записано как cN=c22nλr. Это сводится к нахождению аппроксимации ab, где a,b<2n, для конкретного числа двоичной точки c22n. Для решения этой задачи используются цепные дроби.
 Поскольку форма рационального числа не единственна в своем роде, то λ и r определяются как ab=λr, если gcd(λ,r)=1. Вероятность того, что оба числа λ и r просты, больше чем 1lnr, поэтому, чтобы вероятность успеха была близка к единице, необходимо только O(n) попыток.