Shorsův algoritmus - Shors algorithm - Wikipedia

Shorův algoritmus je polynomiální čas kvantový počítačový algoritmus pro celočíselná faktorizace.^[1] Neformálně řeší následující problém: Dáno celé číslo ${ displaystyle N}$, najít jeho hlavní faktory. To bylo vynalezeno v roce 1994 americkým matematikem Peter Shor.

Na kvantovém počítači započítat celé číslo ${ displaystyle N}$, Shorův algoritmus běží v polynomiálním čase (čas je polynomiální v ${ displaystyle log N}$, velikost celého čísla zadaného jako vstup).^[2] Konkrétně to trvá kvantové brány řádu ${ displaystyle O ! left (( log N) ^ {2} ( log log N) ( log log log N) right)}$ pomocí rychlého množení,^[3] což ukazuje, že problém celočíselné faktorizace lze efektivně vyřešit na kvantovém počítači a je tedy v třída složitosti BQP. To je téměř exponenciálně rychlejší než nejúčinnější známý klasický factoringový algoritmus, síto obecného čísla, který pracuje v subexponenciální čas: ${ displaystyle O ! left (e ^ {1,9 ( log N) ^ {1/3} ( log log N) ^ {2/3}} right)}$.^[4] Účinnost Shorova algoritmu je dána účinností kvantová Fourierova transformace, a modulární umocňování podle opakované kvadratury.^[5]

Pokud kvantový počítač s dostatečným počtem qubits mohl fungovat, aniž by podlehl kvantový šum a další kvantová dekoherence je možné použít Shorův algoritmus k prolomení kryptografie veřejného klíče schémata, jako jsou široce používané RSA systém. RSA je založen na předpokladu, že factoring velkých celých čísel je výpočetně neřešitelný. Pokud je známo, je tento předpoklad platný pro klasické (nekvantové) počítače; není znám žádný klasický algoritmus, který dokáže v polynomiálním čase ovlivnit celá čísla. Shorův algoritmus však ukazuje, že factoringová celá čísla jsou na ideálním kvantovém počítači efektivní, takže může být možné porazit RSA konstrukcí velkého kvantového počítače. Byl to také silný motivátor pro návrh a konstrukci kvantových počítačů a pro studium nových kvantově-počítačových algoritmů. Rovněž usnadnil výzkum nových kryptosystémů, které jsou zabezpečeny před kvantovými počítači, souhrnně nazývanými postkvantová kryptografie.

V roce 2001 Shorův algoritmus demonstrovala skupina v IBM, kteří započítali ${ displaystyle 15}$ do ${ displaystyle 3 krát 5}$pomocí Implementace NMR kvantového počítače s ${ displaystyle 7}$ qubits.^[6] Po implementaci IBM implementovaly Shorův algoritmus dvě nezávislé skupiny fotonický qubits, s důrazem na multi-qubit zapletení byl pozorován při běhu Shorových algoritmických obvodů.^[7][8] V roce 2012 byla provedena faktorizace ${ displaystyle 15}$ bylo provedeno pomocí polovodičových qubitů.^[9] Také v roce 2012 byla provedena faktorizace ${ displaystyle 21}$ bylo dosaženo, čímž se vytvořil rekord pro největší celé číslo zohledněné Shorovým algoritmem.^[10] Mnohem větší počty byly započítány kvantovými počítači pomocí jiných algoritmů, konkrétně kvantového žíhání.

Postup

Problém, který se snažíme vyřešit, je, vzhledem k složené číslo ${ displaystyle N}$, najít netriviální dělitel z ${ displaystyle N}$ (dělitel přísně mezi ${ displaystyle 1}$ a ${ displaystyle N}$). Než se pokusíte najít takového dělitele, můžete jej použít relativně rychle testování primality algoritmy k ověření toho ${ displaystyle N}$ je skutečně složený.

Potřebujeme ${ displaystyle N}$ být lichý (jinak ${ displaystyle 2}$ je dělitel) a nebýt mocninou prvočísla (jinak je prvočíslo dělitelem), takže musíme zkontrolovat, zda neexistují žádné celočíselné kořeny ${ displaystyle { sqrt [{k}] {N}}}$ pro ${ displaystyle 2 leq k leq { log _ {3}} (N)}$.

Proto to můžeme předpokládat ${ displaystyle N}$ je produktem dvou coprime celá čísla větší než ${ displaystyle 2}$. Vyplývá to z Čínská věta o zbytku že existují nejméně čtyři odlišné druhé odmocniny ${ displaystyle 1}$ modulo ${ displaystyle N}$ (protože pro každou modulární rovnici existují dva kořeny). Cílem algoritmu je najít druhou odmocninu ${ displaystyle b}$ z ${ displaystyle 1}$ modulo ${ displaystyle N}$ to se liší od ${ displaystyle 1}$ a ${ displaystyle -1}$, protože pak

${ displaystyle b ^ {2} -1 = (b + 1) (b-1) = mN}$

pro nenulové celé číslo ${ displaystyle m}$ což nám dává netriviální dělitele ${ displaystyle gcd (N, b + 1)}$ a ${ displaystyle gcd (N, b-1)}$ z ${ displaystyle N}$.Tato myšlenka je podobná jiné factoringové algoritmy, tak jako kvadratické síto.

Na druhé straně hledání takové ${ displaystyle b}$ se redukuje na nalezení prvku ${ displaystyle a}$ sudého období s určitou další vlastností (jak je vysvětleno níže, je nutné, aby podmínka kroku 6 klasické části neplatila). Kvantový algoritmus se používá k nalezení období náhodně vybraných prvků ${ displaystyle a}$, protože to je obtížný problém na klasickém počítači.

Shorův algoritmus se skládá ze dvou částí:

1. Redukce faktoringového problému na problém, kterou lze provést na klasickém počítači objednat -nález.
2. Kvantový algoritmus k vyřešení problému s hledáním řádu.

Klasická část

Například: Dáno ${ displaystyle N = 15}$, ${ displaystyle a = 7}$, a ${ displaystyle r = 4}$, my máme ${ displaystyle gcd (7 ^ {2} pm 1,15) = gcd (49 pm 1,15)}$, kde ${ displaystyle gcd (48,15) = 3}$ a ${ displaystyle gcd (50,15) = 5}$. Pro ${ displaystyle N}$ to je produkt dvou odlišných prvočísel, ${ displaystyle p}$ a ${ displaystyle q}$, hodnota ${ displaystyle varphi (N)}$ je jen ${ displaystyle N-p-q + 1}$, který pro ${ displaystyle N = 15}$ je ${ displaystyle 8}$, a ${ displaystyle r}$ rozděluje ${ displaystyle 8}$.

Kvantová část: podprogram pro zjišťování období

Tato sekce může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (únor 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Kvantový podprogram v Shorově algoritmu

Kvantové obvody použité pro tento algoritmus jsou navrženy na míru pro každou volbu ${ displaystyle N}$ a každá volba náhodného ${ displaystyle a}$ použito v ${ displaystyle f (x) = a ^ {x} { bmod {N}}}$. Dáno ${ displaystyle N}$, najít ${ displaystyle Q = 2 ^ {q}}$ takhle ${ displaystyle N ^ {2} leq Q <2N ^ {2}}$, což z toho vyplývá ${ displaystyle { dfrac {Q} {r}}> N}$. Vstup a výstup qubit registry musí obsahovat superpozice hodnot z ${ displaystyle 0}$ na ${ displaystyle Q-1}$a také ${ displaystyle q}$ každý qubits. Použití toho, co by se mohlo zdát dvakrát tolik qubitů, než je nutné, zaručuje, že jich alespoň je ${ displaystyle N}$ různé hodnoty ${ displaystyle x}$ které produkují to samé ${ displaystyle f (x)}$, dokonce jako období ${ displaystyle r}$ přístupy ${ displaystyle { dfrac {N} {2}}}$.

Postupujte následovně:

Vysvětlení algoritmu

Algoritmus se skládá ze dvou částí. První část algoritmu mění faktoringový problém na problém nalezení periody funkce a může být implementován klasicky. Druhá část najde období pomocí kvantové Fourierovy transformace a je zodpovědná za kvantové zrychlení.

Získávání faktorů z období

Celá čísla menší než ${ displaystyle N}$ a coprime s ${ displaystyle N}$ tvoří multiplikativní skupina celých čísel modulo ${ displaystyle N}$, což je konečný abelian skupina ${ displaystyle G}$. Velikost této skupiny je dána vztahem ${ displaystyle varphi (N)}$. Na konci kroku 3 máme celé číslo ${ displaystyle a}$ v této skupině. Protože skupina je konečná, ${ displaystyle a}$ musí mít konečnou objednávku ${ displaystyle r}$, což je nejmenší kladné celé číslo

${ displaystyle a ^ {r} equiv 1 { bmod {N}}.}$

Proto, ${ displaystyle N}$ rozděluje ${ displaystyle a ^ {r} -1}$ (také psáno ${ displaystyle N mid a ^ {r} -1}$). Předpokládejme, že jsme schopni získat ${ displaystyle r}$ a že je to dokonce. (Li ${ displaystyle r}$ je liché, pak v kroku 5 musíme restartovat algoritmus s jiným náhodným číslem ${ displaystyle a}$) Nyní ${ displaystyle b equiv a ^ {r / 2} { bmod {N}}}$ je druhá odmocnina z ${ displaystyle 1}$ modulo ${ displaystyle N}$ to se liší od ${ displaystyle 1}$. To je proto, že ${ displaystyle r}$ je řád ${ displaystyle a}$ modulo ${ displaystyle N}$, tak ${ displaystyle a ^ {r / 2} not equiv 1 { bmod {N}}}$nebo jinak v pořadí ${ displaystyle a}$ v této skupině by bylo ${ displaystyle { dfrac {r} {2}}}$. Li ${ displaystyle a ^ {r / 2} equiv -1 { bmod {N}}}$, pak v kroku 6 musíme restartovat algoritmus s jiným náhodným číslem ${ displaystyle a}$.

Nakonec musíme zasáhnout ${ displaystyle a}$ řádu ${ displaystyle r}$ v ${ displaystyle G}$ takhle ${ displaystyle b equiv a ^ {r / 2} not equiv 1, -1 { bmod {N}}}$. Je to proto, že takový ${ displaystyle b}$ je druhá odmocnina z ${ displaystyle 1}$ modulo ${ displaystyle N}$ jiný než ${ displaystyle 1}$ a ${ displaystyle -1}$, jehož existenci zaručuje čínská věta o zbytku, as ${ displaystyle N}$ není hlavní síla.

Tvrdíme to ${ displaystyle d = gcd (b-1, N)}$ je správný faktor ${ displaystyle N}$, tj., ${ displaystyle d neq 1, N}$. Ve skutečnosti, pokud ${ displaystyle d = N}$, pak ${ displaystyle N}$ rozděluje ${ displaystyle b-1}$, aby ${ displaystyle b equiv 1 { bmod {N}}}$, který jde proti výstavbě ${ displaystyle b}$. Pokud na druhou stranu ${ displaystyle d = gcd (b-1, N) = 1}$, poté Bézoutova identita, existují celá čísla ${ displaystyle u, v}$ takhle

${ displaystyle (b-1) u + Nv = 1.}$

Vynásobením obou stran ${ displaystyle b + 1}$, získáváme

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

Tak jako ${ displaystyle N}$ rozděluje ${ displaystyle b ^ {2} -1 equiv a ^ {r} -1 { bmod {N}}}$, zjistíme, že ${ displaystyle N}$ rozděluje ${ displaystyle b + 1}$, aby ${ displaystyle b equiv -1 { bmod {N}}}$, opět v rozporu s konstrukcí ${ displaystyle b}$.

Proto, ${ displaystyle d}$ je požadovaný správný faktor ${ displaystyle N}$.

Nalezení období

Shorův algoritmus pro zjišťování období do značné míry závisí na schopnosti a kvantový počítač být v mnoha státech současně.

Fyzici nazývají toto chování „superpozice "stavů. Vypočítat periodu funkce ${ displaystyle f}$, hodnotíme funkci ve všech bodech současně.

Kvantová fyzika nám však neumožňuje přímý přístup ke všem těmto informacím. A měření přinese pouze jednu ze všech možných hodnot a zničí všechny ostatní. Pokud ne pro žádná klonovací věta, mohli bychom nejprve měřit ${ displaystyle f (x)}$ bez měření ${ displaystyle x}$, a poté vytvořte několik kopií výsledného stavu (což je superpozice stavů, které mají všechny stejné ${ displaystyle f (x)}$). Měření ${ displaystyle x}$ na tyto státy by poskytovaly jiné ${ displaystyle x}$ hodnoty, které dávají to samé ${ displaystyle f (x)}$, což vede k období. Protože nemůžeme vytvářet přesné kopie kvantového stavu, tato metoda nefunguje. Proto musíme pečlivě transformovat superpozici do jiného stavu, který s vysokou pravděpodobností vrátí správnou odpověď. Toho je dosaženo kvantová Fourierova transformace.

Shor tak musel vyřešit tři „implementační“ problémy. Všechny musely být implementovány „rychle“, což znamená, že je lze implementovat s řadou kvantové brány to je polynomiální v ${ displaystyle log N}$.

1. Vytvořte superpozici stavů. Toho lze dosáhnout aplikací Hadamard brány ke všem qubitům ve vstupním registru. Dalším přístupem by bylo použití kvantové Fourierovy transformace (viz níže).
2. Implementujte funkci ${ displaystyle f}$ jako kvantová transformace. K dosažení tohoto cíle použil Shor opakované kvadratury pro jeho modulární exponenciační transformaci. Je důležité si uvědomit, že tento krok je obtížněji proveditelný než kvantová Fourierova transformace, protože k tomu vyžaduje pomocné qubity a podstatně více bran.
3. Proveďte kvantovou Fourierovu transformaci. Použitím bran s řízenou rotací a Hadamardových bran navrhl Shor obvod pro kvantovou Fourierovu transformaci (s ${ displaystyle Q = 2 ^ {q}}$), který používá jen ${ displaystyle { dfrac {q (q-1)} {2}} = O ! left (( log Q) ^ {2} right)}$ brány.^[12]

Po všech těchto transformacích získá měření aproximaci období ${ displaystyle r}$. Pro jednoduchost předpokládejme, že existuje ${ displaystyle y}$ takhle ${ displaystyle { dfrac {yr} {Q}}}$ je celé číslo. Pak pravděpodobnost měření ${ displaystyle y}$ je ${ displaystyle 1}$. Abychom to viděli, všimli jsme si toho

${ displaystyle e ^ {- { frac {2 pi ibyr} {Q}}} = 1}$

pro všechna celá čísla ${ displaystyle b}$. Součet, jehož čtverec nám dává pravděpodobnost měření ${ displaystyle y}$ bude ${ displaystyle { dfrac {Q} {r}}}$, tak jako ${ displaystyle b}$ trvá zhruba ${ displaystyle { dfrac {Q} {r}}}$ hodnoty a tedy pravděpodobnost ${ displaystyle { dfrac {1} {r ^ {2}}}}$. Existují ${ displaystyle r}$ možné hodnoty ${ displaystyle y}$ takhle ${ displaystyle { dfrac {yr} {Q}}}$ je celé číslo a také ${ displaystyle r}$ možnosti pro ${ displaystyle f (x_ {0})}$, takže součty pravděpodobností jsou ${ displaystyle 1}$.

Poznámka: Dalším způsobem, jak vysvětlit Shorův algoritmus, je poznamenat, že jde pouze o algoritmus odhadu kvantové fáze v přestrojení.

Úzké místo

Runtime úzké místo Shorova algoritmu je kvantové modulární umocňování, který je mnohem pomalejší než kvantová Fourierova transformace a klasické předběžné / následné zpracování. Existuje několik přístupů ke konstrukci a optimalizaci obvodů pro modulární umocňování. Nejjednodušší a (v současné době) nejpraktičtější přístup je napodobit konvenční aritmetické obvody pomocí vratné brány, začínání s zvlněné nosiče. Znalost základny a modulu umocňování usnadňuje další optimalizace.^[13][14] Reverzibilní obvody se obvykle používají v řádu ${ displaystyle n ^ {3}}$ brány pro ${ displaystyle n}$ qubits. Alternativní techniky asymptoticky zvyšují počet bran pomocí použití kvantové Fourierovy transformace, ale nejsou konkurenceschopní s méně než 600 qubitů kvůli vysokým konstantám.

Diskrétní logaritmy

Vzhledem ke skupině ${ displaystyle G}$ s objednávkou ${ displaystyle p}$ a generátor ${ displaystyle g v G}$, předpokládejme, že to víme ${ displaystyle x = g ^ {r} v G}$, pro některé ${ displaystyle r in mathbb {Z} _ {p}}$, a chceme počítat ${ displaystyle r}$, který je diskrétní logaritmus: ${ displaystyle r = { log _ {g}} (x)}$. Zvažte abelianskou skupinu ${ displaystyle mathbb {Z} _ {p} krát mathbb {Z} _ {p}}$, kde každý faktor odpovídá modulárnímu sčítání hodnot. Nyní zvažte funkci

${ displaystyle f colon mathbb {Z} _ {p} times mathbb {Z} _ {p} to G ;; ; f (a, b) = g ^ {a} x ^ {- b}.}$

To nám dává abelian skrytý problém s podskupinou, tak jako ${ displaystyle f}$ odpovídá a skupinový homomorfismus. Jádro odpovídá násobkům ${ displaystyle (r, 1)}$. Takže pokud najdeme jádro, můžeme najít ${ displaystyle r}$.

Viz také

• GEECM, faktorizační algoritmus byl „často mnohem rychlejší než Shorův“.^[15]
• Groverův algoritmus

Reference

Další čtení

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Září 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

• Nielsen, Michael A. & Chuang, Isaac L. (2010), Kvantové výpočty a kvantové informace, vydání k 10. výročí, Cambridge University Press, ISBN  9781107002173.
• Phillip Kaye, Raymond Laflamme, Michele Mosca, Úvod do kvantové práce na počítači, Oxford University Press, 2007, ISBN  0-19-857049-X
• „Vysvětlení pro muže na ulici“ podle Scott Aaronson, "schválený „Peter Shor. (Shor napsal:„ Skvělý článek, Scotte! To je ta nejlepší práce, jak vysvětlit kvantové výpočty muži na ulici, jaké jsem viděl. “). Alternativní metafora pro QFT byla představena v jeden z komentářů. Scott Aaronson navrhuje následujících 12 odkazů jako další čtení (z „10¹⁰⁵⁰⁰⁰ výukové programy kvantového algoritmu, které jsou již na webu. "):
• Shor, Peter W. (1997), „Algoritmy polynomiálního času pro Prime Factorization a diskrétní logaritmy na kvantovém počítači“, SIAM J. Comput., 26 (5): 1484–1509, arXiv:quant-ph / 9508027v2, Bibcode:1999SIAMR..41..303S, doi:10.1137 / S0036144598347011. Revidovaná verze původního příspěvku Petera Shora („28 stran, LaTeX. Toto je rozšířená verze příspěvku, který vyšel ve sborníku z 35. ročníku sympozia o základech informatiky, Santa Fe, NM, 20. listopadu - 22, 1994. Drobné revize provedené v lednu 1996 “).
• Kvantové výpočty a Shorův algoritmus, Matthew Hayward Stránka Kvantové algoritmy, 2005-02-17, imsa.edu, LaTeX2HTML verze originálu Dokument LaTeX, k dispozici také jako PDF nebo postscript dokument.
• Kvantový výpočet a Shorův faktoringový algoritmus Ronald de Wolf, CWI a University of Amsterdam, 12. ledna 1999, 9stránkový postscriptový dokument.
• Shorův faktoringový algoritmus Poznámky z přednášky 9 Berkeley CS 294–2 ze dne 4. října 2004, 7stránkový postscriptový dokument.
• Kapitola 6 Kvantové výpočty, 91stránkový postscriptový dokument, Caltech, Preskill, PH229.
• Kvantový výpočet: výukový program podle Samuel L. Braunstein.
• Kvantové stavy Shorova algoritmu, Autor: Neal Young, Poslední úprava: Út 21. května 11:47:38 1996.
• III. Prolomení šifrování RSA pomocí kvantového počítače: Shorův faktoringový algoritmus „Přednášky o kvantovém výpočtu, Cornell University, Fyzika 481–681, CS 483; Jaro 2006 N. David Mermin. Poslední revize 2006-03-28, 30stránkový dokument PDF.
• Lavor, C .; Manssur, L. R. U .; Portugalsko, R. (2003). "Shorův algoritmus pro faktorování velkých celých čísel". arXiv:quant-ph / 0303175.
• Lomonaco, Jr (2000). „Algoritmus Shorova kvantového faktoringu“. arXiv:quant-ph / 0010034. Tento příspěvek je písemnou verzí hodinové přednášky o algoritmu kvantového factoringu Petera Shora. 22 stránek.
• Kapitola 20 Kvantové výpočty, z Výpočetní složitost: moderní přístup, Návrh knihy: Z ledna 2007, Sanjeev Arora a Boaz Barak, Princetonská univerzita. Publikováno jako Kapitola 10 Kvantové výpočty Sanjeev Arory, Boaz Barak, „Výpočetní složitost: moderní přístup“, Cambridge University Press, 2009, ISBN  978-0-521-42426-4
• Krok k kvantovému výpočtu: zapletení 10 miliard částic z časopisu Discover Magazine ze dne 19. ledna 2011.
• Josef Gruska - Kvantové počítačové výzvy také v Matematika neomezená: 2001 a dále Redaktoři Björn Engquist, Wilfried Schmid, Springer, 2001, ISBN  978-3-540-66913-5

externí odkazy

• Verze 1.0.0 z libquantum: obsahuje implementaci Shorova algoritmu v jazyce C s jejich simulovanou kvantovou počítačovou knihovnou, ale proměnná width v shor.c by měla být nastavena na 1, aby se zlepšila složitost běhového prostředí.
• PBS Infinite Series vytvořil dvě videa vysvětlující matematiku za Shorovým algoritmem, “Jak prolomit kryptografii " a "Hackování kvantovou rychlostí pomocí Shorova algoritmu ".