Shorův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. června 2021; ověření vyžaduje 1 úpravu .

Shorův algoritmus je algoritmus kvantové faktorizace (rozklad čísla na prvočinitele), který umožňuje rozložit číslo v čase pomocí logických qubitů . $M$ $O(\log ^{3}M)$ $O(\log M)$

Shorův algoritmus byl vyvinut Peterem Shorem v roce 1994 . O sedm let později, v roce 2001 , jeho výkon předvedla skupina specialistů IBM . Číslo 15 bylo faktorizováno 3 a 5 pomocí kvantového počítače se 7 qubity .

O algoritmu

Význam algoritmu spočívá v tom, že s jeho pomocí (při použití kvantového počítače s několika tisíci logickými qubity) je možné prolomit kryptografické systémy s veřejným klíčem . Například RSA používá veřejný klíč , který je součinem dvou velkých prvočísel. Jedním ze způsobů, jak prolomit šifru RSA, je najít faktory. Když jsou dostatečně velké, je to téměř nemožné pomocí známých klasických algoritmů . Nejznámější klasické deterministické osvědčené faktorizační algoritmy, jako je Shanksova metoda kvadratické formy a Pollard-Strassenův algoritmus , vyžadují čas objednávky. Také Shanksova metoda kvadratické formy může běžet v pořadí, pokud je Riemannova hypotéza pravdivá . Mezi pravděpodobnostními algoritmy je lídrem faktorizace speciální metoda číselného pole síta , která je schopna najít prvočíselného dělitele s pravděpodobností 1/2 v subexponenciálním čase. Shorův algoritmus je s využitím schopností kvantových počítačů schopen faktorizovat číslo nejen v polynomiálním čase, ale v době, která není o mnoho větší v čase násobení celých čísel (tedy téměř stejně rychle jako samotné šifrování). Implementace škálovatelného kvantového počítače tak ukončí většinu moderní kryptografické ochrany. Nejde jen o schéma RSA, které přímo spoléhá na složitosti faktorizace, ale také o další podobná schémata, která dokáže kvantový počítač rozlousknout podobným způsobem. $M,$ $M.$ $M$ $M^{1/4}.$ $M^{1/5}$ $\exp \left(\left({\frac {32}{9}}\cdot \log M\right)^{1/3}\cdot (\log \log M)^{2/3} \že jo).$

Shorův algoritmus má pravděpodobnostní charakter. První zdroj náhodnosti je zabudován do klasické pravděpodobnostní redukce faktorizace na nalezení periody nějaké funkce. Druhý zdroj pochází z potřeby pozorování kvantové paměti, která také dává náhodné výsledky [1] .

Jak funguje Shorův algoritmus

Základ Shorova algoritmu: schopnost informačních jednotek kvantových počítačů – qubitů – nabývat několika hodnot současně a být ve stavu „ kvantového zapletení “. Umožňuje tedy provádět výpočty v podmínkách hospodárnosti qubitů. Princip fungování Shorova algoritmu lze rozdělit na 2 části: první je klasická redukce faktorizace na nalezení periody určité funkce, druhou je kvantové zjištění periody této funkce. Nechat:

M

- číslo, které chceme faktorizovat (nemělo by to být celočíselná mocnina lichého čísla);

N

- velikost použitého paměťového registru (nepočítám výpis). Bitová velikost této paměti je asi 2krát větší než velikost . Přesněji, ;

n=\log _{2}N

M

M^{2}<N=2^{n}<2M^{2}

t

je náhodný parametr takový, že a (kde je největší společný dělitel ).

1<t<M

\operatorname {gcd} (t,M)=1

\operatorname {gcd}

Všimněte si, že , , jsou pevné. Shorův algoritmus používá standardní způsob redukce problému rozšíření na problém nalezení periody funkce pro náhodně vybrané číslo [2] . $t$ $N$ $M$ $r$ $t$

Klasická část algoritmu

Minimální takové, že je modulo pořadí $r$ $t^{r}\equiv 1\ {\mbox{mod}}\ M,$ $t$ $M.$

Pořadí je období funkce kde $r$ $f(x)=t^{x}\ {\mbox{mod}}\ M,$ $x=0,1,2,...,N-1.$

Jestliže lze efektivně vypočítat jako funkci , pak lze najít jeho vlastního dělitele v čase ohraničeného polynomem z s pravděpodobností pro jakékoli pevné . $r$ $t$ $M$ $\log _{2}M$ $\geqslant 1-M^{{-m}}$ $m$

Předpokládejme, že za dané období je sudé a splňuje podmínku $t$ $r$ $(r\equiv 0\ {\mbox{mod}}\ 2)$

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

Pak

\operatorname {gcd} (t^{\frac {r}{2}}+1,M)

— vlastní dělitel Funkce je vyčíslitelná v polynomiálním čase.

M.

\operatorname {gcd}

Pravděpodobnost splnění této podmínky kde je počet různých lichých prvočíselných dělitelů , tedy v tomto případě. Proto je pravděpodobné, že v pokusech bude nalezena dobrá hodnota. Nejdelší výpočet na jeden pokus je výpočet [3] [4] . $\geqslant 1-{\frac {1}{2^{k-1))},$ $k$ $M$ $\geqslant {\frac {1}{2}}$ $t$ $\geqslant 1-M^{{-m}}$ $O(\log M)$ $t^{\frac {r}{2}}$

Kvantová část algoritmu

Pro implementaci kvantové části algoritmu je výpočetním obvodem kvantový registr a . Zpočátku se každý z nich skládá ze sady qubitů v nulovém booleovském stavu $2$ $X$ $Y$ $|0\rangle .$

Registr se používá k umístění argumentů funkce Registr (pomocný) se používá k umístění hodnot funkce s periodou , která se má vypočítat. $X$ $X$ $f(x).$ $Y$ $f(x)$ $r$

Kvantové počítání se skládá ze 4 kroků [5] :

První krok . V prvním kroku pomocí operace Walsh-Hadamard, což je transformace qubitu pomocí operátoru, je počáteční stav registru převeden na ekvipravděpodobnou superpozici všech booleovských stavů . Druhý registr zůstává ve stavu V důsledku toho je pro systém dvou registrů získán tento stav: $H={\frac {1}{\sqrt {2))}{\begin{bmatrix}1&1\\1&-1\end{bmatrix)),$ $|0\rozsah \$ $X$ $N$ $Y$ $|0\rangle .$ ${\frac {1}{\sqrt {N}}}\sum \limits _{x=0}^{N-1}|x,0\rangle .$

Druhý krok . Nechť je unitární transformace , která se převede do Ve druhém kroku je na systém dvou registrů aplikována unitární transformace. Výsledkem je následující stav systému: $U_{f}$ $|x,0\úhelník$ $|x,f(x)\rangle .$

{\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 ,

to znamená, že mezi stavy obou registrů vzniká určitý vztah.

Třetí krok . Kvantová Fourierova transformace je unitární transformace stavu kvantového registru popsaného -rozměrným stavovým vektorem formy do jiného stavu . $N$ $\sum \limits _{x=0}^{N-1}f(x)|x\rangle ,$ $\sum \limits _{k=0}^{N-1}{\tilde {f}}(k)|k\rangle \ :$

\mathrm {QFT} _{N}:\součet \limits _{x=0}^{N-1}f(x)|x\rangle \ \Šipka doprava \součet \limits _{k=0} ^{N-1}{\tilde {f}}(k)|k\rangle \ ,

kde amplituda Fourierovy transformace má tvar

f(x)

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

Ve dvourozměrné rovině odpovídá Fourierova transformace otočení souřadnicových os o 90°, což vede k transformaci měřítka na měřítko . Ve třetím kroku se provede Fourierova transformace na stavu prvního registru a ukáže se

x,k

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}\ {\mbox{mod}}\ M\rangle .

Čtvrtý krok . Ve čtvrtém kroku se první registr změří vzhledem k ortogonální projekci pohledu: $X$

|0,0\rangle \otimes I,\quad |1,1\rangle \otimes I,\quad \dots ,\quad |N-1,N-1\rangle \otimes I,

kde je operátor identity na Hilbertově prostoru druhého registru .

já

Y

V důsledku toho se ukazuje s pravděpodobností [6] $|k,t^{k}\ {\mbox{mod}}\ M\rangle \$

\left|{\frac {1}{N}}\sum \limits _{x:\ t^{x}\equiv t^{k}\ {\mbox{mod}}\ M}\exp (2\pi \ i\ kx/N)\vpravo|^{2}.

Zbytek běhu běží na klasickém počítači:

Najděte nejlepší přiblížení (zdola) k se jmenovatelem ${\frac {k}{N}}\$ $r'<M<{\sqrt {N}}:$ $\left|{\frac {k}{N}}\ -{\frac {d'}{r'}}\right|<{\frac {1}{2N}}.$

Zkusme v roli : $r'$ $r$
- Pokud , pak by se mělo počítat $r'\equiv 0\ {\mbox{mod}}\ 2$ $\operatorname {gcd} (t^{\frac {r'}{2}}\pm 1,M).$
- Pokud je lichá nebo sudá, ale nebyl nalezen žádný vlastní dělitel , měli byste běh opakovat znovu se stejným . V případě selhání změňte a spusťte nový běh algoritmu [3] [4] . $r'$ $r'$ $M$ $O(\log \log M)$ $t$ $t$

Stanovení periody funkce pomocí Fourierovy transformace je do jisté míry podobné měření konstant krystalové mřížky pomocí rentgenové nebo neutronové difrakce. Pro určení periody není nutné počítat všechny hodnoty. V tomto smyslu je problém podobný německému problému , ve kterém je důležité znát ne všechny hodnoty funkce, ale pouze některé její vlastnosti [6] . $r,$ $f\left(x\right).$

Nalezení periody funkce v algoritmu

Nechť je funkce s neznámou periodou $F$ $r:$

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

Pro určení periody jsou zapotřebí dva registry s velikostmi a qubity, které musí být zpočátku ve stavu $r,$ $2n$ $m$ $|0,0\rangle .$

V první fázi se provede jednostranná superpozice všech bázových vektorů prvního registru pomocí operátoru v následujícím tvaru: $U$

U|0,0\rangle \ =\součet \limits _{i=0}^{N-1}c_{i}|i,0\rangle \

, kde a

|c_{i}|={\frac {1}{\sqrt {N))}

N=2^{2n}.

Zde je použita Hadamardova pseudo- transformace . Aplikováním na aktuální stav dostaneme: $H_{1}={\begin{bmatrix}2&1\\1&1\end{bmatrix}}$ $F$

|\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 .

Měření druhého registru s výsledkem , kam vede stát $k=f(s),$ $s<r,$

|\psi '\rangle =\sum \limits _{j=0}^{[N/r]-1}c_{j}'|rj+s,k\rangle ,\qquad

kde

c_{j}'=\left[{\frac {N}{r}}\right]^{-1/2}.

Po změření stavu se první registr skládá pouze z bázových vektorů takové formy , že pro všechny má tedy diskrétní homogenní spektrum. Je nemožné přímo získat periodu nebo její násobek měřením prvního registru, protože zde je náhodná veličina. Zde použijeme diskrétní Fourierovu transformaci formuláře $|\psi '\rangle$ $|rj+s\rangle$ $f(rj+s)=f(s)$ $j.$ $r$ $s$

\mathrm {DFT:} |x\rangle \rightarrow {\frac {1}{\sqrt {N))}\sum \limits _{y=0}^{N-1}e^{{\ frac {2\pi i}{N}}xy}|y\rangle

na registru, protože pravděpodobnost spektra v transformovaném stavu je neměnná s ohledem na posun (lze transformovat pouze fáze, nikoli absolutní hodnoty amplitud).

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

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),

kde a

\varphi _{i}=2\pi i{\frac {is}{N}}\quad

\quad p=\left[{\frac {N}{r}}\right].

If je násobkem , pak if je násobkem a jinak. I když to není mocnina 2, spektrum ukazuje jednotlivé vrcholy s tečkou, protože $N=2^{2n}$ $r$ $c_{i}''={\frac {e^{\varphi _{i))}{\sqrt {r))},$ $i$ ${\frac {N}{r)),$ $c_{i}''=0$ $r$ $|\psi ''\rangle$ ${\frac {N}{r)),$

\lim _{n\to \infty }{\frac {1}{n}}\součet \limits _{k=0}^{n-1}e^{2\pi ik\alpha }={\begin {cases}1\ \ ,\alpha \in Z\\0\ \ ,\alpha \notin Z\\\end{cases}}

Pro první registr se qubity používají, protože to zaručuje alespoň prvků v daném součtu, a tedy šířka píků bude řádově $2n$ $r<2^{n},$ $2^{n}$ $O(1).$

Pokud nyní vypočítáme první registr, dostaneme hodnotu blízkou tomu, kde to může být zapsáno jako Toto se scvrkává na nalezení aproximace kde pro konkrétní číslo binárního bodu .K vyřešení tohoto problému se používají pokračující zlomky. $c,$ ${\frac {\lambda N}{r)),$ $\lambda \in Z_{r}.$ ${\frac {c}{N}}=c\cdot 2^{-2n}\cca {\frac {\lambda }{r)).$ ${\frac {a}{b)),$ $a,b<2^{n},$ $c\cdot 2^{-2n}.$

Vzhledem k tomu, že tvar racionálního čísla není jednoznačný, pak u jsou definovány tak, jako kdyby pravděpodobnost, že obě čísla a jsou prvočísla, je větší než proto, aby se pravděpodobnost úspěchu blížila jedné, stačí pouze pokusy [7] [5] . $\lambda$ $r$ ${\frac {a}{b}}={\frac {\lambda }{r)),$ $\operatorname {gcd} (\lambda ,r)=1.$ $\lambda$ $r$ ${\frac {1}{\ln r)),$ $Na)$

Diskrétní logaritmus

Další matematický problém, diskrétní logaritmus , často používaný k vytvoření asymetrických kryptografických systémů, je také zranitelný vůči kvantovému algoritmu navrženému Shorem ve stejném článku [8] .

Viz také

kvantový počítač

Poznámky

↑ Beckman, Chari, Devabhaktuni a kol., 1996 .
↑ Valijev, 2004 , str. 86-92.
↑ 12 Feynman , 1986 .
↑ 12 Feynman , 1982 .
↑ 12 Shor , 1997 .
↑ 1 2 Valijev, 2004 , str. 81-92.
↑ Shor, 1994 .
↑ Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring // Základy počítačové vědy, sborník z roku 1994. , 35. výroční sympozium o - IEEE , 1994. - S. 124–134. - ISBN 0-8186-6580-7 - doi:10.1109/SFCS.1994.365700

Literatura

Feynman R. Simulating Physics with Computers (anglicky) // International Journal of Theoretical Physics - Springer Science + Business Media , 1982. - Vol. 21, Iss. 6 / 7. - S. 467-488. — ISSN 0020-7748 ; 1572-9575 – doi:10.1007/BF02650179
Feynman R. Kvantové mechanické počítače (anglicky) // Základy fyziky / Gerard 't Hooft - Springer Science + Business Media , 1986. - Vol. 16, Iss. 6. - S. 507-531. — ISSN 0015-9018 ; 1572-9516 – doi:10.1007/BF01886518
D B., AN C., S D., J P., Beckman D. , Chari A. N. , Devabhaktuni S. , Preskill J. Efficient networks for quantum factoring // Phys . Rev. A - College Park, MD : American Physical Society , 1996. - Vol. 54, Iss. 2. - S. 1034-1063. — ISSN 2469-9926 ; 2469-9934 ; 2469-9942 - doi:10.1103/PHYSREVA.54.1034 - PMID:9913575 - arXiv:quant-ph/9602016
Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring (anglicky) // Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on - IEEE , 1994. - S. 124–134. - ISBN 0-8186-6580-7 - doi:10.1109/SFCS.1994.365700
Shor PW Polynomiální-časové algoritmy pro primární faktorizaci a diskrétní logaritmy na kvantovém počítači // Základy informatiky : Publikace z konference. - 1997. - S. 1484-1509.
Valijev K. A. , Kokin A. A. Kvantové počítače: naděje a realita. - Iževsk: RHD, 2004. - 320 s.

Odkazy

Shor PW Algoritmy pro kvantové výpočty: diskrétní logaritmy a faktoring // Základy informatiky : Publikace z konference. - 1994. - S. 124-134 . - ISBN 0-8186-6580-7 . - doi : 10.1109/SFCS.1994.365700 .

Shor PW Polynomiální-časové algoritmy pro primární faktorizaci a diskrétní logaritmy na kvantovém počítači // Základy informatiky : Publikace z konference. - 1997. - S. 1484-1509 .

Zdrojový kód pro simulátor kvantového počítače v C++ a kompletní implementace Shorova algoritmu, včetně reverzibilního modulárního schématu umocňování, s podrobným popisem a schématy kvantových bran

Kvantové algoritmy
Shorův algoritmus Groverův algoritmus Deutsch-Yozhi algoritmus Feynmanův problém Algoritmus Zalka-Wiesner kvantové žíhání

kvantová informatika

Obecné pojmy

kvantové komunikace

kvantový kanál
- kvantová síť
kvantová kryptografie
- Kvantová distribuce klíčů
Teleportace kvantové energie
kvantová teleportace
Kvantové ultra-husté kódování
LOCC
kvantová destilace

Kvantové algoritmy

kvantový simulátor
Deutsch-Yozhi algoritmus
Bernstein-Waziraniho algoritmus
Groverův algoritmus
Kvantová Fourierova transformace
Shorův algoritmus
Simonův problém
Algoritmus kvantového odhadu fáze
Kvantový výpočetní algoritmus
kvantové žíhání
Algoritmické chlazení
Kvantový algoritmus pro řešení soustavy lineárních rovnic
Amplitudový zisk

Kvantová teorie složitosti

Kvantové výpočetní modely

kvantový obvod
- kvantová brána
Jednostranný kvantový počítač
- shluk
Adiabatické kvantové výpočty
Topologický kvantový počítač

Prevence dekoherence

Oprava kvantových chyb
Stabilizační kódy
Stabilizační formalismus
Kvantový konvoluční kód

Fyzické implementace

kvantová optika	Kavitační kvantová elektrodynamika Konturová kvantová elektrodynamika Kvantové výpočty založené na lineární optice protokol KLM Bosonické vzorkování
superchladné atomy	Kvantový počítač s absorbovanými ionty Optická mřížka
zpět založené	Kvantový počítač založený na nukleární magnetické rezonanci Kaneův kvantový počítač Ztrátový kvantový počítač - DiVincenzo NV centrum
Supravodivé kvantové počítače	nabít qubit streamovací qubit Fázový qubit Transmon