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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Питер Шор - автор алгоритма

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

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

Об алгоритме[править | править исходный текст]

Значимость алгоритма заключается в том, что с его помощью (при использовании квантового компьютера с несколькими сотнями логических кубитов) становится возможным взлом криптографических систем с открытым ключом. К примеру, RSA использует открытый ключ M, являющийся произведением двух больших простых чисел. Один из способов взломать шифр RSA — найти множители M. При достаточно большом M это практически невозможно сделать, используя известные классические алгоритмы. Наилучший из известных классических алгоритмов факторизации требует времени порядка M^{1/3}. Алгоритм Шора, используя возможности квантовых компьютеров, способен произвести факторизацию числа не просто за полиномиальное время, а за время, не намного превосходящее время умножения целых чисел (то есть практически так же быстро, как происходит само шифрование). Таким образом, реализация масштабируемого квантового компьютера поставила бы крест на большей части современной криптографической защиты. (Речь не только о схеме RSA, прямо опирающейся на сложности факторизации, но и о других сходных схемах, которые квантовый компьютер способен взломать аналогичным образом).

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

Принцип работы алгоритма Шора[править | править исходный текст]

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

M — число, не являющееся корнем нечётного числа, которое хотим разложить на множители
N — размер регистра памяти, который используется (не считая свалки)

Битовый размер этой памяти n примерно в 2 раза больше размера M.

Точнее,

M^2<N=2^n<2M^2

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

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

Классический алгоритм[править | править исходный текст]

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

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

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


Предположим, что для данного t период r удовлетворяет

r\equiv 0\ mod\ 2, t^{\frac{r}{2}}\ne -1\ mod\ M.

Тогда

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

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

Квантовый алгоритм[править | править исходный текст]

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

Регистр X используется для размещения аргументов x функции f(x)

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

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

  • Первый шаг. На первом шаге с помощью операции Уолша-Адамара первоначальное состояние |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. На втором шаге применяется унитарное преобразование к системе двух регистров. Получается следующее состояние системы:
|x,0 \rangle \frac{1}{\sqrt{N}} \sum\limits_{x=0}^{N-1} \xrightarrow{U_f} \frac{1}{\sqrt{N}} \sum\limits_{x=0}^{N-1} |x,t^x\ 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\ :
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^\circ, которое приводит к преобразованию шкалы 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\ mod\ M\rangle .
  • Четвёртый шаг. На четвёртом шаге выполняется измерение первого регистра X относительно ортогональной проекции вида:
|0, 0\rangle \otimes I, |1, 1\rangle \otimes I, |1, 1\rangle \otimes I, … ,|N-1, N-1\rangle \otimes I, где I — тождественный оператор на Гильбертовом пространстве второго регистра Y.

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

\left | \frac{1}{N}\sum\limits_{x:\ t^x \equiv t^k\ mod\ M}\exp(2\pi\ i\ kx/N)  \right |^2[6]


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

  • Находится наилучшее приближение (снизу) к \frac{k}{N}\ со знаменателем r'<M<\sqrt{N}:
    \left | \frac{k}{N}\ - \frac{d'}{r'}\right | < \frac{1}{2N}
  • Пробуем r' в роли r:
    • Если r'\equiv 0\ mod\ 2 , то следует вычислить gcd (t^\frac{r'}{2} \pm1, M).
    • Если r' нечетно или если r' четно, но собственный делитель M не обнаружен, то следует повторить прогон O(\lg \lg M) раз с тем же самым t. В случае отказа изменить t и начать новый прогон алгоритма[3][4].

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

Нахождение периода функции в алгоритме[править | править исходный текст]

Пусть 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. Применяя F к текущему состоянию получается:

| \psi \rangle =F H |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 где c_j'=\left [ \frac{N}{r} \right ]^{-1/2}

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

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 = 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^{\phi_i}\sum\limits_{j=0}^{p-1}exp \left ( \frac{2\pi i}{N}ijr \right )
где \phi_i = 2\pi i \frac{is}{N} и p=\left [ \frac{N}{r} \right ]

Если N = 2^{2n} кратно r, тогда c_i''= \frac{e^{\phi_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}, если gcd(\lambda,r) = 1 Вероятность того, что \lambda и r просты, больше чем \frac{1}{\ln r}, таким образом только O (n) попыток необходимо, чтобы вероятность успеха как можно ближе была к 1[7][5].

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

Литература[править | править исходный текст]

  • Beckman D.,Chari A. N.,Devabhaktuni Sr.,Preskill J. Efficient networks for quantum factoring (англ.) // Physical Review A. — 1996. — Vol. 54. — P. 1034-1063.
  • Валиев К. А., Кокин А. А. Квантовые компьютеры: надежды и реальность. — Ижевск: РХД, 2004. — 320 с.
  • Feynman R. Quantum Mechanical Computer (англ.) // Foundations of Physics. — 1986. — Vol. 16. — P. 507-531.
  • Feynman R. Simulating Physics with Computers (англ.) // International Journal of Theoretical Physics. — 1982. — Vol. 21. — P. 467–488. — DOI:10.1007/BF02650179
  • Shor P. W. Algorithms for quantum computation: discrete logarithms and factoring // Foundations of Computer Science : Conference Publications. — 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.

Ссылки[править | править исходный текст]