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

Шоров алгоритам, назван по математичару Питеру Шору (енгл. Peter Shor), је квантни алгоритам (алгоритам који функционоше на квантном рачунару) за разлагање целих бројева на просте чиниоце формулисан 1994. У суштини он решава следећи проблем: За дати цео број N, налази његове просте чиниоце.

На квантном рачунару, да би свео број N на просте чиниоце, Shor-ов алгоритам ради у полиномијалном времену (време потребно за извршавање алгоритма је полином у log N, што је величина улаза). Прецизно, потребно му је време O((log N)³), показујући да се проблем растављања броја на просте чиниоце може ефикасно решити на квантном рачунару и да се налази у класи сложености BQP (квантно полиномијално време са ограниченом грешком) проблема. Ово је знатно брже од већине познатих алгоритама за растављање на просте чиниоце, изузетак је алгоритам сита поља општег броја који ради у под-експоненционалном времену — отприлике O(e^{1.9 (log N)1/3 (log log N)2/3}). Ефикасност Шоровог алгоритма је у ефикасности квантних Фуријеових трансформација, и модуларном степеноваљу помоћу квадрата броја.

Ако би квантни рачунар са довољним бројем квантних бита могао да ради без утицаја шумова и осталих квантних сметњи, Шоров алгоритам би се могао користити за разбијање шема криптографије јавног-кључа као што су веома познате RSA (РСА) шема. RSA се заснива на претпоставци да је растављање великих бројева на просте чиниоце рачунарски неизводљиво. За сада колико је познато, ова претпоставка важи за класичне (не-квантне) рачунаре; не зна се ни за један класичан алгоритам који може да раставља на просте чиниоце у полиномијалном времену. Међутим, Шоров алгоритам показује да је растављање на просте чиниоце ефикасно на идеалном квантном рачунару, тако да је могуће да се победи RSA конструкцијом великог квантног рачунара. То је такође била велика мотивација за дизајнирање и конструкцију квантних рачунара и за учење нових алгоритама за квантне рачунаре. У исто време отпочело је истраживање нових криптосистема који су били сигурни од квантних рачунара, целокупно названи пост-квантна криптографија.

2001., Шоров алгоритам је демонстрирала група са IBM-а, која је раставила 15 на 3 × 5, користећи NMR (Нуклеарну магнетну ресонансу) имплементацију квантног рачунара са 7 квантних битова. Ипак, јавиле су се неке сумње око тога да ли је IBM-ов експеримент био права демонстрација квантног рачунара, пошто никакво квантно уплитање није виђено. Од IBM-ове имплементације, неколико других група је имплементирало Шоров алгоритам користећи фотонске квантне битове, наглашавајући да је уплитање виђено. 2012., растављање броја 15 је поновљено. Такође 2012., растављање броја 21 је постигнуто, постављајући тако рекорд за највећи број растављен на просте чиниоце са квантним рачунаром.

Поступак

Проблем који покушавамо да решимо је: за дат непаран сложен број $N$, наћи цео број $d$, строго између $1$ и $N$, који дели $N$. Нас занимају непарне вредности броја $N$ јер парне вредности броја $N$ имају број $2$ као прост чинилац. Можемо да искористимо алгоритам за тестирање да ли је број прост да будемо сигурни да је број $N$ стварно сложен.

Штавише, да би алгоритам радио, потребно је да $N$ не буде степен чиниоца. Ovо се може тестирати налажењем квадратног, кубног, ..., $k$-ог корена од $N$, за $k\leq \log _{2}(N)$, и проверавањем да ни једна од ових вредности није цео број. (Ово заправо искључује да је $N=M^{k}$ за неке целе бројеве $M$ и $k>1$.)

Пошто $N$ није степен чиниоца, он је производ два узајамно проста броја већа од $1$. Као последица кинеске теореме остатка, број $1$ има бар четири различита корена модула $N$, два су $1$ и $-1$. Циљ алгоритма је да нађе корен $b$ од један, осим $1$ и $-1$; такав $b$ ће довести до растављања броја $N$, као и у другим алгоритмима за растављање броја на чиниоце као квадратно сито.

Заузврат, проналажење таквог $b$ је сведено на проналажење броја $a$ парног редоследа са одређеном додатном особином (као што је објашњено доле, неопходно је да услов Корака 6 класичног дела не буде испуњен). Квантни алгоритам се користи за налажење редоследа насумично одабраног елемента $a$, јер је налажење правог редоследа тежак проблем на класичном рачунару.

Шоров алгоритам се састоји из два дела:

1. Смањења, које се може извести на класичном рачунару, проблема растављања на просте чиниоце на проблем налажења правог редоследа.
2. Квантног алгоритма да реши проблем редоследа.

Класичан део

1. Одабрати насумичан број a < N
2. Налажење НЗД(a, N). Ово се може урадити користећи Еуклидов алгоритам.
3. Ако је НЗД(a, N) ≠ 1, онда постоји не-тривијалан чинилац од N, тако да смо завршили.
4. У супротном, искористити под-рутину за налажење редоследа (испод) да би се нашло r, редослед следеће функције:

   $f(x)=a^{x}\ {\mbox{mod}}\ N$,

   редослед $r$ од $a$ у $(\mathbb {Z} _{N})^{\times }$, који је најмањи позитиван цео број r за који важи $f(x+r)=f(x)$ or $f(x+r)=a^{x+r}\ {\mbox{mod}}\ N=a^{x}\ {\mbox{mod}}\ N$
5. Ако је r непаран, иде се назад на Корак 1.
6. Ако је a ^{r /2} ≡ −1 mod N), иди назад на Корак 1.
7. НЗД(a^r/2 ± 1, N) је не-тривијални чинилац N. Завршили смо.

На пример: $N=15,a=2,r=4$, gcd(4 ± 1, N)

Квантни део: Под-рутина за налажење редоследа

Квантна кола коришћена за овај алгоритам су посебно направљена за сваки избор N и насумично a коришћено у f(x) = a^x mod N. За дато N, наћи Q = 2^q тако да $N^{2}\leq Q<2N^{2}$, из чега следи $Q/r>N$. Улазни и излазни квантни бит регистри морају да задрже вредности супер-позиција од 0 до Q − 1, и тако имамо q квантних бита појединачно. Коришћењем дупло више квантних битова него што се чини потребним осигуравамо да има барем N различитих x који дају исто f(x), иако се редослед r приближава N/2.

Поступамо на следећи начин:

1. Поставити регистре на

   $Q^{-1/2}\sum _{x=0}^{Q-1}\left|x\right\rangle \left|0\right\rangle$

   где x иде од 0 до Q − 1. Ово почетно стање је суперпозиција Q стања.
2. Направити f(x) као квантну функцију и применити је на горње стање, да би се добило

   $Q^{-1/2}\sum _{x}\left|x\right\rangle \left|f(x)\right\rangle .$

   Ово је и даље суперпозиција Q стања.
3. Применити квантне Фуријеове трансформације на улазни регистар. Ова трансформација (радићи на суперпозицији степена двојке Q = 2^q states) користи Q^ти јединични корен као што је $\omega =e^{2\pi i/Q}$ да распореди амплитуду било ког датог $\left|x\right\rangle$ стања једнаког међу свим Q $\left|y\right\rangle$ стања, и да уради то на другачији начин за свако различито x:

   $U_{QFT}\left|x\right\rangle =Q^{-1/2}\sum _{y}\omega ^{xy}\left|y\right\rangle .$

   Ово води до последњег стања

   $Q^{-1}\sum _{x}\sum _{y}\omega ^{xy}\left|y\right\rangle \left|f(x)\right\rangle .$

   Ово је суперпозиција од много више Q стања, али много мање Q² стања. Иако постоје Q² изрази у суми, стање $\left|y\right\rangle \left|f(x_{0})\right\rangle$ се може занемарити кад год x₀ и x дају исту вредност. Нека је
   • $\omega =e^{2\pi i/Q}$ Q^ти јединични корен,
   • r редослед f,
   • x₀ најмањи од скупа x који дају исто задато f(x) (имамо x₀ < r), и
   • b које иде од 0 до $\lfloor (Q-x_{0}-1)/r\rfloor$ тако да $x_{0}+rb<Q.$
   Онда је $\omega ^{ry}$ јединични вектор у сложеној равни ($\omega$ је јединични корен а r и y су цели бројеви), и коефицијент $Q^{-1}\left|y\right\rangle \left|f(x_{0})\right\rangle$ у последњем стању је

   $\sum _{x:\,f(x)=f(x_{0})}\omega ^{xy}=\sum _{b}\omega ^{(x_{0}+rb)y}=\omega ^{x_{0}y}\sum _{b}\omega ^{rby}.$

   Сваки израз у овој суми представља различит пут до истог резултата, и долази до квантне сметње—када јединични вектори $\omega ^{ryb}$показују у скоро истом смеру на сложеној равни, што захтева да $\omega ^{ry}$ показују уз дуж позитивне реалне осе.
4. Извршити мерење. Долазимо до неког исхода y на улазном регистру и $f(x_{0})$ на излазном регистру. Пошто је f периодично, вероватноћа мерења неког пара y и $f(x_{0})$ је дата помоћу

   $\left|Q^{-1}\sum _{x:\,f(x)=f(x_{0})}\omega ^{xy}\right|^{2}=Q^{-2}\left|\sum _{b}\omega ^{(x_{0}+rb)y}\right|^{2}=Q^{-2}\left|\sum _{b}\omega ^{bry}\right|^{2}.$

   Анализе данас показују да је ова вероватноћа већа, што је јединични вектор $\omega ^{ry}$ позитивној реалној оси, или је yr/Q ближе целом броју. Уколико р није степен 2, он неће бити чинилац Q.
5. Користећи Верижни разломак на y/Q да би направили његову апроксимацију, и направимо c/r′ од њега тако да задовољава два услова:
   • A: r′<N
   • B: |y/Q - c/r′| < 1/2Q.
   Уколико смо задовољили ова два услова, r′ би био прави редослед r са великом вероватноћом тачности.
6. Проверити да ли је f(x) = f(x + r′) $\Leftrightarrow$ $a^{r}\equiv 1{\pmod {N}}$ Ако јесте, завршили смо.
7. У супротном, узети још кандидата за r користећи вредности близу y, или мултипликаторе r′. Ако било који кандидат задовољава услове, завршили смо.
8. У супротном, врати се назад на Корак 1 под-рутине.

Објашњење алгоритма

Алгоритам се састоји из два дела. Први део алгоритма своди проблем растављања броја на просте чиниоце на проблем налажења редоследа функције, и може се имплементирати класично. Други део налази редослед коришћењем квантних Фуријеових трансформација, и одговоран је за квантно убрзање алгоритма.

Налажење чинилаца из редоследа

Бројеви мањи од N и узајамно прости са N формирају коначну Абелову групу $G$ са множењем по modulo N. Величина је дата помоћу Ојлерове фи функције $\phi (N)$. До краја Корака 3, имамо цео број a у овој групи. Пошто је група коначна, a мора имати коначан поредак r, најмањи позитиван цео број такав да

$a^{r}\equiv 1\ {\mbox{mod}}\ N.\,$

Стога, N се дели (пише се и | ) a ^r − 1. Претпоставимо да можемо добити r, и да је паран. (Ако је r непаран, погледајте Корак 5.) Сада је $b\equiv a^{r/2}{\pmod {N}}$ квадратни корен 1 modulo $N$, различит од 1. Ово је јер је $r$ редослед од $a$ modulo $N$, тако да $a^{r/2}\not \equiv 1{\pmod {N}}$, иначе би редослед $a$ у овој групи био $r/2$. Ако је $a^{r/2}\equiv -1{\pmod {N}}$, до Корака 6 бисмо морали да поновимо алгоритам са другим произвољним бројем $a$.

Најзад, морали бисмо да погодимо $a$, редоследа $r$ у $G$, такав да је $b\equiv a^{r/2}\not \equiv 1,-1{\pmod {N}}$. То је зато што је $b$ квадратни корен 1 modulo $N$, осим 1 и $-1$, чије постојање гарантује кинеска теорија остатка, пошто $N$ није степен чиниоца.

Ми тврдимо да је $d=\operatorname {gcd} (b-1,N)$ прави чинилац од $N$, за, $d\neq 1,N$. У ствари ако је $d=N$, онда се $N$ дели на $b-1$, тако да $b\equiv 1{\pmod {N}}$, против настанка $b$. Ако са друге стране $d=\operatorname {gcd} (b-1,N)=1$, онда помоћу Безуовог става постоје цели бројеви $u,v$ такви да

$(b-1)u+Nv=1$.

Множењем обе стране са $b+1$ добијамо

$(b^{2}-1)u+N(b+1)v=b+1$.

Пошто $N$ дели $b^{2}-1\equiv a^{r}-1{\pmod {N}}$, добијамо да $N$ дели $b+1$, тако да $b\equiv -1{\pmod {N}}$, поново контрадиктујући настанку $b$.

Тако да је $d$ потребни прави чинилац $N$.

Проналажење периоде

Шоров алгоритам проналажења периоде се углавном ослања на способност квантног рачунара да се налази у више стања истовремено. Физичари називају ово понашање „суперпозиција“ стања. Да би израчунали периоду функције f, ми оцењујемо функцију у свим тачкама истовремено.

Квантна физика нам ипак не дозвољава приступ свим овим информацијама директно. Мерење ће дати само једно од свих могућих вредности, уништавајући сва остала. Да није теореме о не-клонирању, могли бисмо прво да измеримо f(x) без мерења самог x, и онда направили пар копија резултујућег стања (што је суперпозиција свих стања које имају исто f(x)). Мерењем x-а у овим стањима бисмо добили различите x вредности које дају исто f(x), што нас води до периоде. Пошто не можемо направити тачне копије квантног стања, овај метод не функционише. Стога морамо пажљиво трансформисати суперпозицију у друго стање које ће вратити тачан одговор са највећом вероватноћом. Ово се постиже квантним Фуријеовим трансформацијама.

Шор је стога морао решити три „имплементациона“ проблема. Сви су морали бити имплементирани „брзо“, што значи да могу бити имплементирани са бројем квантних улаза који је полиномијалан у $\log N$.

1. Направити суперпозицију стања. Ово се може постићи применом Hadamard кола на све квантне битове у улазном регистру. Још један начин би био да се искористе квантне Фуријеове трансформације (погледати испод).
2. Имплементирати функцију f као квантну трансформацију. Да би ово постигао, Шор је користио поновљено квадрирање за његову модуларну експоненцијалну трансформацију. Битно је нагласити да је овај корак теже имплементирати него квантне Фуријеове трахцформације, јер оно захтева помоћне квантне битове и знатно више улаза да би се извршило.
3. Извести квантне Фуријеове трансформације. Користећи улазе са контролом ротације и Hadamard улазе, Шор је дизајнирао коло за квантне Фуријеове трансформације (са Q = 2^q) само $q(q-1)/2=O((\log Q)^{2})$ улаза.

После свих ових трансформација мера ће дати апроксимацију периоде r. Због једноставности претпоставимо да постоји y такво да је yr/Q цео број. Онда је вероватноћа да измеримо y 1. Тада примећујемо да важи

$e^{-2\pi ibyr/Q}=1\,$

за све целе бројеве b. Стога ће сума чији нам квадрат даје вероватноћу да измеримо y бити Q/r пошто b захтева отприлике Q/r вредности и тако је вероватноћа $1/r^{2}$. Постоје r y такви да је yr/Q цео број и уједно r могућности за $f(x_{0})$, тако да се могућности сумирају на 1.

Белешка: још један начин да се објасни Шоров алгоритам јесте да се примети да је он маскирани алгоритам процене квантне фазе.

Уско грло

Дужина трајања уског грла Шоровог алгоритма је квантно модуларно степеновање, што је знатно спорије од квантних Фуријеових трансформација и класичног pre-/post-процесирања. Постоји неколико приступа да се направе и оптимизују кола за модуларно степеновање. Најлакши и (тренутно) најпрактичнији приступ јесте да се опонашају конвенционална аритметичка кола са променљивим улазима, почевши са сабирачима са преносом таласа. Знање базе и модула степеновања олакшава даљу оптимизацију. Променљива кола типично користе око $n^{3}$ улаза за $n$ квантних битова. Алтернативне технике асимптотски побољшавају број улаза користећи квантне Фуријеове трансформације, али нису конкурентни са мање од 600 квантних битова због великих константи.

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

Претпоставимо да знамо да је $x=g^{r}{\pmod {p}}$, за неко r, и да желиом да израчунамо r, које је дискретни логаритам: $r=\log _{g}x{\pmod {p}}$. Размотримо Абелову групу $\left(\mathbb {Z} _{p}\right)^{\times }\times \left(\mathbb {Z} _{p}\right)^{\times }$ где сваки фактор одговара модуларном множењу не-нула вредности, претпостављајући да је p главни. Сада, размотримо функцију

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

Ово нам даје проблем скривених Абелових подгрупа, где f одговара групном хомоморфизму. Језгро одговара модуларном мултипликатору (r,1). Тако да ако нађемо језгро, ми можемо да нађемо и r.

Литература

• Nielsen, Michael A. & Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge University Press .
• Phillip Kaye; Raymond Laflamme; Michele Mosca (2007). An introduction to quantum computing. Oxford University Press. ISBN 978-0-19-857049-3. 
• "Explanation for the man in the street" by Scott Aaronson, "approved" by Peter Shor. (Shor wrote "Great article, Scott! That’s the best job of explaining quantum computing to the man on the street that I’ve seen."). An alternate metaphor for the QFT was presented in one of the comments. Scott Aaronson suggests the following 12 references as further reading (out of "the 10¹⁰⁵⁰⁰⁰ quantum algorithm tutorials that are already on the web.")
• Shor, Peter W. (1997), „Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM J. Comput., 26 (5): 1484—1509, Bibcode:1999SIAMR..41..303S, arXiv:quant-ph/9508027v2 , doi:10.1137/S0036144598347011 . Revised version of the original paper by Peter Shor ("28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994. Minor revisions made January, 1996").
• Quantum Computing and Shor's Algorithm, Matthew Hayward, 2005-02-17, imsa.edu, LaTeX2HTML version of the original 2750 line LaTeX document, also available as a 61 page PDF or postscript document.
• Quantum Computation and Shor's Factoring Algorithm, Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.