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

Алгоритм Шора — квантовый алгоритм факторизации (разложениячисла на простые множители), позволяющий разложить число 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 части: первая — классическоесведение разложения на множители к нахождению периода некоторой функции,вторая — квантовое нахождение периода этой функции. Пусть:

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

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


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

tr21 mod M.
 Тогда

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

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


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

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


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


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

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


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

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


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


|0,0I,|1,1I,,|N1,N1I,где I — тождественный оператор на гильбертовом пространстве второгорегистра Y.
 В результате получается |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$сознаменателем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\{piik \{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)попыток.