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

Алгоритм Шора — квантовий алгоритм факторизації (розкладання числа на прості множники), що дозволяє розкласти число ${\displaystyle M}$ за час ${\displaystyle O(\log ^{3}M)}$, використовуючи ${\displaystyle O(\log M)}$ логічних кубітів.

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

Про алгоритм

Значущість алгоритму полягає в тому, що з його допомогою (при використанні квантового комп'ютера з достатньою кількістю логічних кубітів) стає можливим злом деяких криптографічних систем з відкритим ключем. Наприклад, в RSA частиною відкритого ключа є число ${\displaystyle M}$, яке є добутком двох великих простих чисел. Один із способів зламати шифр RSA — знайти множники ${\displaystyle M}$. При досить великому ${\displaystyle M}$ це практично неможливо зробити використовуючи відомі класичні алгоритми. Найкращі з відомих класичних детермінованих доведених алгоритмів факторизації, такі як метод квадратичних форм Шенкса і алгоритм Полларда — Штрассена^[ru], вимагають часу порядку ${\displaystyle M^{1/4}}$. Також метод квадратичних форм Шенкса може працювати за час порядку ${\displaystyle M^{1/5}}$, якщо вірна Гіпотеза Рімана. Серед імовірнісних алгоритмів лідером факторизації є спеціальний метод решета числового поля^[en], який здатний з ймовірністю 1/2 знайти простий дільник за субекспоненціальний час ${\displaystyle \exp \left(\left({\frac {32}{9}}\cdot \log M\right)^{1/3}\cdot (\log \log M)^{2/3}\right).}$ Алгоритм Шора, використовуючи можливості квантових комп'ютерів, здатний здійснити факторизацію числа не просто за поліноміальний час, а за час, що не набагато перевершує час множення цілих чисел (тобто практично так само швидко, як відбувається саме шифрування). Таким чином, реалізація квантового комп'ютера, що масштабується, поставить хрест на значній частині сучасного криптографічного захисту. (Мова не тільки про схему RSA, що прямо спирається на складність факторизації, а й про інші схеми, які квантовий комп'ютер здатний зламати аналогічним чином.)

Алгоритм Шора має ймовірнісний характер. Перше джерело випадковості вбудоване в класичний вірогіднісне зведення розкладання на множники до знаходження періоду деякої функції. Друге джерело з'являється з необхідності спостереження квантової пам'яті, яке також дає випадкові результати^[1].

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

Основа алгоритму Шора: здатність інформаційних одиниць квантових комп'ютерів — кубітів — приймати кілька значень одночасно і перебувати в стані «квантової заплутаності». Роботу алгоритму Шора можна розділити на 2 частини: перша — класичне зведення розкладання на множники до знаходження періоду деякої функції, друга — квантове знаходження періоду цієї функції. Нехай:

${\displaystyle M}$ — число, яке ми хочемо розкласти на множники (воно не повинно бути цілим степенем простого числа);

${\displaystyle N}$ — розмір регістра пам'яті, який використовується (без врахування додаткової пам'яті). Бітовий розмір цієї пам'яті ${\displaystyle n=\log _{2}N}$ приблизно в 2 рази більше розміру ${\displaystyle M}$. Точніше, ${\displaystyle M^{2}<N=2^{n}<2M^{2}}$;

${\displaystyle t}$ — випадковий параметр такий, що ${\displaystyle 1<t<M}$ і ${\displaystyle \gcd(t,M)=1}$ (де ${\displaystyle \gcd }$ — найбільший спільний дільник).

Відзначимо, що ${\displaystyle t}$, ${\displaystyle N}$, ${\displaystyle M}$ — фіксовані. В алгоритмі Шора використовується стандартний спосіб зведення задачі факторизації до задачі пошуку періоду ${\displaystyle r}$ функції від випадково підібраного числа ${\displaystyle t}$^[2].

Класична частина алгоритму

Мінімальне ${\displaystyle r}$ таке, що ${\displaystyle t^{r}\equiv 1\mod M,}$ — це порядок ${\displaystyle t}$ по модулю ${\displaystyle M.}$

Порядок ${\displaystyle r}$ є періодом функції ${\displaystyle f(x)=t^{x}\mod M,}$ де ${\displaystyle x=0,1,2,\ldots ,N-1.}$ Якщо можна ефективно обчислити ${\displaystyle r}$ як функцію від ${\displaystyle t}$, то можна знайти власний дільник ${\displaystyle M}$ за час, обмежений поліномом від ${\displaystyle \log _{2}M}$ з ймовірністю ${\displaystyle \geqslant 1-M^{-m}}$ для будь-якого фіксованого ${\displaystyle m}$.

Припустимо, що для даного ${\displaystyle t}$ період ${\displaystyle r}$ парний ${\displaystyle (r\equiv 0\mod 2)}$ і задовольняє умові

${\displaystyle t^{\frac {r}{2}}\not \equiv -1\mod M.}$

Тоді

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

Ймовірність виконання цієї умови ${\displaystyle \geqslant 1-{\frac {1}{2^{k-1}}},}$ де ${\displaystyle k}$ — число різних непарних простих дільників ${\displaystyle M}$, отже, ${\displaystyle \geqslant {\frac {1}{2}}}$ в даному випадку. Тому хороше значення ${\displaystyle t}$ з ймовірністю ${\displaystyle \geqslant 1-M^{-m}}$ знайдеться за ${\displaystyle O(\log M)}$ спроб. Найдовше обчислення в одній спробі — обчислення ${\displaystyle t^{\frac {r}{2}}}$^[3][4].

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

Для здійснення квантової частини алгоритму необхідна обчислювальна схема, що складається з ${\displaystyle 2}$-х квантових регістрів ${\displaystyle X}$ і ${\displaystyle Y}$. Спочатку, кожен з них складається із сукупності кубітів в нульовому булевому стані ${\displaystyle |0\rangle .}$

Регістр ${\displaystyle X}$ використовується для розміщення аргументів ${\displaystyle x}$ функції ${\displaystyle f(x).}$ Регістр ${\displaystyle Y}$ (допоміжний) використовується для розміщення значень функції ${\displaystyle f(x)}$ з періодом ${\displaystyle r}$, що підлягають обчисленню.

Квантове обчислення складається з 4 кроків^[5]:

• Перший крок. На першому кроці за допомогою операції Уолша - Адамара, яка здійснює перетворення кубіта за допомогою оператора ${\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}},}$ первісний стан ${\displaystyle |0\rangle \ }$ регістра ${\displaystyle X}$ перекладається в рівноймовірнісну суперпозицію всіх булевих станів ${\displaystyle X}$. Другий регістр ${\displaystyle Y}$ залишається в стані ${\displaystyle |0\rangle .}$ В результаті виходить наступний стан для системи двох регістрів:

  ${\displaystyle {\frac {1}{\sqrt {N}}}\sum \limits _{x=0}^{N-1}|x,0\rangle .}$

• Другий крок. Нехай ${\displaystyle U_{f}}$ — унітарне перетворення, яке переводить ${\displaystyle |x,0\rangle }$ в ${\displaystyle |x,f(x)\rangle .}$ На другому кроці застосовується унітарне перетворення до системи двох регістрів. Виходить наступний стан системи:

${\displaystyle {\frac {1}{\sqrt {N}}}\sum \limits _{x=0}^{N-1}|x,0\rangle \quad {\xrightarrow {U_{f}}}\quad {\frac {1}{\sqrt {N}}}\sum \limits _{x=0}^{N-1}|x,t^{x}\ {\mbox{mod}}\ M\rangle ,}$ тобто між станами обох регістрів утворюється певний зв'язок.

• Третій крок. Квантове Фур'є-перетворення^[en] є унітарним перетворенням стану квантового регістра, що описується ${\displaystyle N}$-мірним вектором стану виду ${\displaystyle \sum \limits _{x=0}^{N-1}f(x)|x\rangle ,}$ в інший стан ${\displaystyle \sum \limits _{k=0}^{N-1}{\tilde {f}}(k)|k\rangle }$:

${\displaystyle \mathrm {QFT} _{N}:\sum \limits _{x=0}^{N-1}f(x)|x\rangle \ \Rightarrow \sum \limits _{k=0}^{N-1}{\tilde {f}}(k)|k\rangle \ ,}$ де амплітуда перетворення Фур'є ${\displaystyle f(x)}$ має вигляд

${\displaystyle {\tilde {f}}(k)={\frac {1}{N}}\sum \limits _{x=0}^{N-1}\exp(2\pi \ i\ kx/N)f(x).}$

У двовимірній ${\displaystyle x,k}$-площині перетворення Фур'є відповідає повороту осей координат на 90°, яке веде до перетворення шкали ${\displaystyle x}$ в шкалу ${\displaystyle k}$. На третьому кроці над станом першого регістра здійснюється перетворення Фур'є, і виходить

${\displaystyle {\frac {1}{N}}\sum \limits _{x=0}^{N-1}\sum \limits _{k=0}^{N-1}\exp(2\pi \ i\ kx/N)|k,t^{x}{\bmod {\ }}M\rangle .}$

• Четвертий крок. На четвертому кроці виконується вимірювання першого регістра ${\displaystyle X}$ щодо ортогональної проєкції^[ru] виду:

${\displaystyle |0,0\rangle \otimes I,\quad |1,1\rangle \otimes I,\quad \dots ,\quad |N-1,N-1\rangle \otimes I,}$ де ${\displaystyle I}$ — тотожний оператор на гільбертовому просторі другого регістра ${\displaystyle Y}$.

В результаті виходить ${\displaystyle |k,t^{k}{\bmod {M}}\rangle }$ з ймовірністю^[2]

${\displaystyle \left|{\frac {1}{N}}\sum \limits _{x:\ t^{x}\equiv t^{k}{\bmod {M}}}\exp(2\pi \ i\ kx/N)\right|^{2}.}$

На тій частині прогону, що залишилась, працює класичний комп'ютер:

• Знаходиться найкраще наближення (знизу) до ${\displaystyle {\frac {k}{N}}}$ зі знаменником ${\displaystyle r'<M<{\sqrt {N}}:}$

  ${\displaystyle \left|{\frac {k}{N}}\ -{\frac {d'}{r'}}\right|<{\frac {1}{2N}}.}$

• Пробуємо ${\displaystyle r'}$ в ролі ${\displaystyle r}$:
  • Якщо ${\displaystyle r'\equiv 0\mod 2}$, то слід обчислити ${\displaystyle \gcd(t^{\frac {r'}{2}}\pm 1,M).}$
  • Якщо ${\displaystyle r'}$ непарне, або якщо ${\displaystyle r'}$ парне, але власний дільник ${\displaystyle M}$ невиявлений, то слід повторити прогін ${\displaystyle O(\log \log M)}$ раз з тим же самим ${\displaystyle t}$. У разі невдачі, необхідно змінити ${\displaystyle t}$ і почати новий прогін алгоритму^[3][4].

Деякою мірою визначення періоду функції за допомогою перетворення Фур'є аналогічне вимірюванню періоду кристалічної ґратки методом рентгенівської або нейтронної дифракції. Щоб визначити період ${\displaystyle r,}$ не потрібно обчислювати всі значення ${\displaystyle f\left(x\right).}$ У цьому сенсі задача близька до алгоритму Дойча — Йожи, в якому важливо знати не всі значення функції, а тільки деякі її властивості^[2].

Знаходження періоду функції в алгоритмі

Нехай ${\displaystyle F}$ — функція з невідомим періодом ${\displaystyle r:}$

${\displaystyle F:|x,0\rangle \ \rightarrow |x,f(x)\rangle \ f:Z\rightarrow Z_{2^{m}}\ r<2^{n}.}$

Щоб визначити період ${\displaystyle r,}$ потрібні два регістра з розмірами ${\displaystyle 2n}$ і ${\displaystyle m}$ кубітів, які спочатку повинні бути в стані ${\displaystyle |0,0\rangle .}$

На першому етапі виконується одностороння суперпозиція всіх базисних векторів першого регістра з використанням оператора ${\displaystyle U}$ наступного вигляду:

${\displaystyle U|0,0\rangle \ =\sum \limits _{i=0}^{N-1}c_{i}|i,0\rangle \ }$, де ${\displaystyle |c_{i}|={\frac {1}{\sqrt {N}}}}$ і ${\displaystyle N=2^{2n}.}$

Тут використовується псевдоперетворення Адамара^[ru] ${\displaystyle H_{1}={\begin{bmatrix}2&1\\1&1\end{bmatrix}}}$. Застосувавши ${\displaystyle F}$ до поточного стану, отримуємо:

${\displaystyle |\psi \rangle =FH_{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 .}$

Вимірювання другого регістра з результатом ${\displaystyle k=f(s),}$ де ${\displaystyle s<r,}$ призводить стан до

${\displaystyle |\psi '\rangle =\sum \limits _{j=0}^{[N/r]-1}c_{j}'|rj+s,k\rangle ,\qquad }$ де ${\displaystyle c_{j}'=\left[{\frac {N}{r}}\right]^{-1/2}.}$

Після вимірювання стану ${\displaystyle |\psi '\rangle }$ перший регістр складається тільки з базисних векторів виду ${\displaystyle |rj+s\rangle }$ таких, що ${\displaystyle f(rj+s)=f(s)}$ для всіх ${\displaystyle j.}$ Тому він має дискретний однорідний спектр. Неможливо прямо отримати період ${\displaystyle r}$ або кратне йому число, вимірюючи перший регістр, тому що тут ${\displaystyle s}$ — випадкова величина. Тут застосовується дискретне перетворення Фур'є виду

${\displaystyle \mathrm {DFT:} |x\rangle \rightarrow {\frac {1}{\sqrt {N}}}\sum \limits _{y=0}^{N-1}e^{{\frac {2\pi i}{N}}xy}|y\rangle }$ на регістр, так як ймовірність спектра в перетвореному стані інваріантна щодо зміщення (перетворюються тільки фази, а не абсолютні значення амплітуд).

${\displaystyle |\psi ''\rangle =\mathrm {DFT} |\psi '\rangle =\sum \limits _{i=0}^{N-1}c_{i}''|i,k\rangle .}$

${\displaystyle 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^{\varphi _{i}}\sum \limits _{j=0}^{p-1}\exp \left({\frac {2\pi i}{N}}ijr\right),}$

де ${\displaystyle \varphi _{i}=2\pi i{\frac {is}{N}}\quad }$ і ${\displaystyle \quad p=\left[{\frac {N}{r}}\right].}$

Якщо ${\displaystyle N=2^{2n}}$ кратне ${\displaystyle r}$, тоді ${\displaystyle c_{i}''={\frac {e^{\varphi _{i}}}{\sqrt {r}}},}$ якщо ${\displaystyle i}$ кратне ${\displaystyle {\frac {N}{r}},}$ і ${\displaystyle c_{i}''=0}$ в іншому випадку. Навіть якщо ${\displaystyle r}$ не є ступенем числа ${\displaystyle 2}$, то спектр ${\displaystyle |\psi ''\rangle }$ показує окремі піки з періодом ${\displaystyle {\frac {N}{r}},}$ бо

${\displaystyle \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}}}$

Для першого регістра використовується ${\displaystyle 2n}$ кубітів, коли ${\displaystyle r<2^{n},}$ бо це гарантує принаймні ${\displaystyle 2^{n}}$ елементів в наведеній сумі, і таким чином ширина піків буде порядку ${\displaystyle O(1).}$

Якщо тепер обчислити перший регістр, то вийде значення ${\displaystyle c,}$ близьке до ${\displaystyle {\frac {\lambda N}{r}},}$ де ${\displaystyle \lambda \in Z_{r}.}$ Воно може бути записано як ${\displaystyle {\frac {c}{N}}=c\cdot 2^{-2n}\approx {\frac {\lambda }{r}}.}$ Це зводиться до знаходження апроксимації ${\displaystyle {\frac {a}{b}},}$ де ${\displaystyle a,b<2^{n},}$ для конкретного числа двійкової крапки ${\displaystyle c\cdot 2^{-2n}.}$ Для вирішення цієї задачі використовуються ланцюгові дроби.

Оскільки форма раціонального числа не єдина в своєму роді, то ${\displaystyle \lambda }$ і ${\displaystyle r}$ визначаються як ${\displaystyle {\frac {a}{b}}={\frac {\lambda }{r}},}$ якщо ${\displaystyle \operatorname {gcd} (\lambda ,r)=1.}$ Імовірність того, що обидва числа ${\displaystyle \lambda }$ і ${\displaystyle r}$ прості, більше ніж ${\displaystyle {\frac {1}{\ln r}},}$ тому, щоб ймовірність успіху була близька до одиниці, необхідно лише ${\displaystyle O(n)}$ спроб^[6][5].

Дискретні логарифми

Нехай дано просте ${\displaystyle p}$ з твірним ${\displaystyle g}$, де ${\displaystyle 1<g<p-1}$, припустимо, що ${\displaystyle x=g^{r}{\pmod {p}}}$, для деякого r, і ми хочемо обчислити r, тобто дискретний логарифм: ${\displaystyle r=\log _{g}x{\pmod {p-1}}}$. Розглянемо абелеву групу ${\displaystyle \left(\mathbb {Z} _{p}\right)^{\times }\times \left(\mathbb {Z} _{p}\right)^{\times }}$, де кожен множник відповідає множенню по модулю ненульових значень, припускаючи що ${\displaystyle p}$ є простим. Тепер розглянемо функцію

${\displaystyle f(a,b)=g^{a}x^{-b}{\pmod {p}}.}$

Це дає нам абелеву проблему прихованої підгрупи, бо f відповідає гомоморфізму груп. Ядро відповідає дільникам (r, 1). Отже, якщо ми можемо знайти ядро, ми можемо знайти r.

У популярній культурі

В телесеріалі Зоряна брама: Всесвіт, провідний вчений, доктор Ніколас Раш, сподівався використати алгоритм Шора щоб зламати мастеркод корабля Доля. Він викладав курс квантової криптографії в Університет Каліфорнії, Берклі, в якому вивчався алгоритм Шора.

У анімаційному фільмі Літні війни^[en], персонаж Кендзі Коїсо читає статтю під назвою «Алгоритм факторизації Шора» під час подорожі в поїзді, передбачаючи його здатність розуміти та обчислювати складні рівняння.

У телесеріалі Теорія великого вибуху це було згадано в змаганні за Кубок з фізики в 1-му сезоні, 13-й серії.

Див. також

• 2017 року Даніель Джуліус Бернстайн запропонував алгоритм факторизації, відомий як GEECM, який вважається "в багатьох випадках набагато швидшим, ніж алгоритм Шора^[7].
• Квантовий комп'ютер

Примітки

1. Beckman, Chari, Devabhaktuni et al., 1996.
2. Валієв, 2004.
3. Feynman, 1986.
4. Feynman, 1982.
5. Shor, 1997.
6. Shor, 1994.
7. Bernstein, Daniel J.; Heninger, Nadia; Lou, Paul; Valenta, Luke (2017). Post-quantum RSA (PDF). International Workshop on Post-Quantum Cryptography. Springer: 311—329. Архів (PDF) оригіналу за 20 квітня 2017. Процитовано 29 січня 2018.

Література

• Feynman R. Simulating Physics with Computers // International Journal of Theoretical Physics. — 1982. — С. 467–488.
• Feynman R. Quantum mechanical computers // Foundations of Physics. — 1986. — С. 507–531.
• Beckman D., Chari A. N., Devabhaktuni S. et al. Efficient networks for quantum factoring // Physical Review A: Atomic, Molecular and Optical Physics. — 1996. — С. 1034–1063.
• Shor P. W. Algorithms for Quantum Computation: Discrete Logarithms and Factoring // Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on. — 1994. — С. 124–134.
• Shor P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // Foundations of Computer Science : conference Publications. — 1997. — С. 1484–1509.
• Валиев К. А., Кокин А. А. Квантовые компьютеры: надежды и реальность. — Ижевск : РХД, 2004. — 320 с.