Shorův algoritmus - Shor's algorithm

Shorův algoritmus je kvantový počítačový algoritmus polynomiálního času pro celočíselnou faktorizaci . Neformálně řeší následující problém: Vzhledem k celému číslu najděte jeho hlavní faktory . To bylo objeveno v roce 1994 americkým matematikem Peterem Shorem . ${\ displaystyle N}$

Na kvantovém počítači pracuje Shorův algoritmus pro výpočet celého čísla v polynomiálním čase (čas je polynomiální v , velikost celého čísla uvedená jako vstup). Konkrétně to vyžaduje kvantové brány řádu pomocí rychlého násobení, což ukazuje, že problém celočíselné faktorizace lze efektivně vyřešit na kvantovém počítači a je tedy ve třídě složitosti BQP . To je téměř exponenciálně rychlejší než nejefektivnější známou klasickou faktoringové algoritmu se obecně číslo pole síto , která pracuje v sub-exponenciální čas : . Účinnost Shorův algoritmus je z důvodu účinnosti kvanta Fourierova transformace a modulární umocňování podle opakovaných squarings . ${\ displaystyle N}$ ${\ displaystyle \ log N}$ ${\ displaystyle O \! \ left ((\ log N) ^ {2} (\ log \ log N) (\ log \ log \ log N) \ right)}$ ${\ displaystyle O \! \ left (e ^ {1,9 (\ log N) ^ {1/3} (\ log \ log N) ^ {2/3}} \ right)}$

Pokud by kvantový počítač s dostatečným počtem qubitů mohl fungovat, aniž by podlehl kvantovému šumu a dalším jevům kvantové dekoherence , mohl by být použit Shorův algoritmus k rozbití kryptografických schémat veřejného klíče , jako je široce používané schéma RSA . 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, tento předpoklad platí pro klasické (nekvantové) počítače; není znám klasický algoritmus, který by dokázal ovlivnit celá čísla v polynomiálním čase. 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čené před kvantovými počítači, souhrnně nazývané postkvantová kryptografie .

V roce 2001 Shorův algoritmus byla prokázána skupinou u společnosti IBM , který factored do , pomocí implementace NMR kvantového počítače s qubits. Po implementaci IBM implementovaly dvě nezávislé skupiny Shorův algoritmus pomocí fotonických qubitů, což zdůraznilo, že při běhu Shorových algoritmických obvodů bylo pozorováno multi-qubitové zapletení . V roce 2012 byla faktorizace provedena pomocí polovodičových qubitů. Také v roce 2012 bylo dosaženo faktorizace , čímž se vytvořil rekord pro největší celé číslo zohledněné Shorovým algoritmem. V roce 2019 byl učiněn pokus faktorovat číslo 35 pomocí Shorova algoritmu na systému IBM Q System One , ale algoritmus selhal kvůli hromadění chyb. Mnohem větší počty však byly započítány kvantovými počítači pomocí jiných algoritmů, konkrétně kvantového žíhání . ${\ displaystyle 15}$ ${\ displaystyle 3 \ krát 5}$ ${\ displaystyle 7}$ ${\ displaystyle 15}$ ${\ displaystyle 21}$

Postup

Problém, který se snažíme vyřešit, je daný složené číslo , najít netriviální dělitele z (dělitel striktně mezi a ). Před pokusem o nalezení takového dělitele je možné pomocí relativně rychlých algoritmů testování primality ověřit, zda je skutečně složený. ${\ displaystyle N}$ ${\ displaystyle N}$ ${\ displaystyle 1}$ ${\ displaystyle N}$ ${\ displaystyle N}$

Musíme být liché (jinak je dělitel), a ne být nějaká síla na vrcholu (v opačném případě, že prvotní je dělitel), takže je třeba zkontrolovat, zda nejsou celočíselné kořeny pro . ${\ displaystyle N}$ ${\ displaystyle 2}$ ${\ displaystyle {\ sqrt [{k}] {N}}}$ ${\ displaystyle 2 \ leq k \ leq {\ log _ {3}} (N)}$

Proto můžeme předpokládat, že je součinem dvou celých čísel coprime větších než . Z čínské věty o zbytku vyplývá, že existují nejméně čtyři odlišné druhé odmocniny modulo (protože pro každou modulární rovnici existují dva kořeny). Cílem tohoto algoritmu je nalézt odmocninu z modulem , který je odlišný od a , protože pak ${\ displaystyle N}$ ${\ displaystyle 2}$ ${\ displaystyle 1}$ ${\ displaystyle N}$ ${\ displaystyle b}$ ${\ displaystyle 1}$ ${\ displaystyle N}$ ${\ displaystyle 1}$ ${\ displaystyle -1}$

{\ Displaystyle b ^ {2} -1 = (b + 1) (b-1) = mN}

pro nenulové celé číslo , které nám dává netriviální dělitele a ze . Tato myšlenka je podobná jako u jiných factoringových algoritmů , jako je kvadratické síto . ${\ displaystyle m}$ ${\ displaystyle \ gcd (N, b + 1)}$ ${\ displaystyle \ gcd (N, b-1)}$ ${\ displaystyle N}$

Nalezení takového se zase sníží na nalezení prvku 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í periody náhodně vybraných prvků , což je na klasickém počítači obtížný problém. ${\ displaystyle b}$ ${\ displaystyle a}$ ${\ displaystyle a}$

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

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

Klasická část

Vyberte náhodné číslo . ${\ displaystyle 1 <a <N}$
Compute je největší společný dělitel of a . To lze provést pomocí euklidovského algoritmu . ${\ displaystyle K = \ gcd (a, N)}$ ${\ displaystyle a}$ ${\ displaystyle N}$
Pokud , pak je netriviální faktor , takže jsme hotovi. ${\ displaystyle K \ neq 1}$ ${\ displaystyle K}$ ${\ displaystyle N}$
V opačném případě použijte k vyhledání podprogram kvantového hledání období (níže) , který označuje období následující funkce: ${\ displaystyle r}$
${\ displaystyle f (x) = a ^ {x} {\ bmod {N}}.}$
Toto je pořadí z ve skupině , která je nejmenší kladné celé číslo , pro které , nebo . Podle Eulerovy věty , dělí , kde označuje Eulerovu totientovou funkci . ${\ displaystyle r}$ ${\ displaystyle a}$ ${\ displaystyle (\ mathbb {Z} _ {N}) ^ {\ times}}$ ${\ displaystyle r}$ ${\ displaystyle f (x + r) = f (x)}$ ${\ displaystyle f (x + r) = a ^ {x + r} {\ bmod {N}} \ ekviv a ^ {x} {\ bmod {N}}}$ ${\ displaystyle r}$ ${\ displaystyle \ varphi (N)}$ ${\ displaystyle \ varphi}$
Pokud je liché, vraťte se zpět ke kroku 1. ${\ displaystyle r}$
Pokud ano, vraťte se zpět ke kroku 1. ${\ displaystyle a ^ {r / 2} \ equiv -1 ({\ bmod {N}})}$
V opačném případě, jak a jsou netriviální faktory , a tak jsme skončili. ${\ displaystyle \ gcd (a ^ {r / 2} + 1, N)}$ ${\ displaystyle \ gcd (a ^ {r / 2} -1, N)}$ ${\ displaystyle N}$

Například: Vzhledem k tomu , a máme , kde a . Protože to je produkt dvou odlišných prvočísel, a hodnota je jen , která pro je , a dělí se . ${\ displaystyle N = 15}$ ${\ displaystyle a = 7}$ ${\ displaystyle r = 4}$ ${\ displaystyle \ gcd (7 ^ {2} \ pm 1,15) = \ gcd (49 \ pm 1,15)}$ ${\ displaystyle \ gcd (48,15) = 3}$ ${\ displaystyle \ gcd (50,15) = 5}$ ${\ displaystyle N}$ ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle \ varphi (N)}$ ${\ displaystyle Np-q + 1}$ ${\ displaystyle N = 15}$ ${\ displaystyle 8}$ ${\ displaystyle r}$ ${\ displaystyle 8}$

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

Kvantový podprogram v Shorově algoritmu

Kvantové obvody použité pro tento algoritmus jsou navrženy pro každou volbu a každou volbu náhodného použitého v . Vzhledem k tomu , najít takové , z čehož vyplývá, že . Vstupní a výstupní qubitové registry musí obsahovat superpozice hodnot od do , a proto musí mít qubits každý. Použití toho, co se může zdát dvakrát tolik qubitů, než je nutné, zaručuje, že existují přinejmenším různé hodnoty, které produkují stejné , i když se období blíží . ${\ displaystyle N}$ ${\ displaystyle a}$ ${\ displaystyle f (x) = a ^ {x} {\ bmod {N}}}$ ${\ displaystyle N}$ ${\ displaystyle Q = 2 ^ {q}}$ ${\ displaystyle N ^ {2} \ leq Q <2N ^ {2}}$ ${\ displaystyle {\ dfrac {Q} {r}}> N}$ ${\ displaystyle 0}$ ${\ displaystyle Q-1}$ ${\ displaystyle q}$ ${\ displaystyle N}$ ${\ displaystyle x}$ ${\ displaystyle f (x)}$ ${\ displaystyle r}$ ${\ displaystyle {\ dfrac {N} {2}}}$

Postupujte následovně:

Inicializujte registry na
${\ displaystyle {\ frac {1} {\ sqrt {Q}}} \ sum _ {x = 0} ^ {Q-1} | x \ rangle = \ left ({\ frac {1} {\ sqrt {2 }}} \ sum _ {x_ {1} = 0} ^ {1} | x_ {1} \ rangle \ right) \ otimes \ cdots \ otimes \ left ({\ frac {1} {\ sqrt {2}} } \ sum _ {x_ {q} = 0} ^ {1} | x_ {q} \ rangle \ right).}$

kde označuje tenzorový součin . ${\ displaystyle \ otimes}$
Tento počáteční stav je superpozicí stavů a lze jej snadno získat generováním nezávislých qubitů , z nichž každý je superpozicí a stavů. Můžeme toho dosáhnout tak, že inicializujeme qubity do nulové polohy a potom paralelně aplikujeme Hadamardovu bránu na každý z qubits, kde . ${\ displaystyle Q}$ ${\ displaystyle q}$ ${\ displaystyle 0}$ ${\ displaystyle 1}$ ${\ displaystyle q}$ ${\ displaystyle 2 ^ {q} = Q}$
Konstruujte jako kvantovou funkci a aplikujte ji na výše uvedený stav, abyste získali ${\ displaystyle f (x)}$
${\ displaystyle U_ {f} | x, 0 ^ {q} \ rangle = | x, f (x) \ rangle}$

${\ displaystyle U_ {f} {\ frac {1} {\ sqrt {Q}}} \ sum _ {x = 0} ^ {Q-1} | x, 0 ^ {q} \ rangle = {\ frac { 1} {\ sqrt {Q}}} \ sum _ {x = 0} ^ {Q-1} | x, f (x) \ rangle}$
Toto je stále superpozice států. Avšak qubits, tj. Vstupní qubits a ( ) výstupní qubits, jsou nyní zapletené nebo neoddělitelné , protože stav nelze zapsat jako tenzorový součin stavů jednotlivých qubits. Důležité je, že hodnota obsahující to, co hledáme, je nyní uložena ve fázi vstupních qubitů jako výsledek „fázového zpětného vrhu“, kde použití qubitů jako řídících vstupů do unitárních bran mění relativní fázi kontrolních qubitů. ${\ displaystyle Q}$ ${\ displaystyle q + n}$ ${\ displaystyle q}$ ${\ displaystyle n}$ ${\ displaystyle> {\ log _ {2}} (N)}$ ${\ displaystyle r}$ ${\ displaystyle x}$
Aplikujte inverzní kvantovou Fourierovu transformaci na vstupní registr. Tato transformace (působící na superpozici stavů) používá tý kořen jednoty například
distribuovat amplitudy daném stavu rovnoměrně mezi všechny ze stavů, a to jiným způsobem pro každý jiný . Tím získáváme ${\ displaystyle Q = 2 ^ {q}}$ ${\ displaystyle Q = 2 ^ {q}}$ ${\ displaystyle Q}$ $Q$ ${\ displaystyle \ omega = e ^ {\ frac {2 \ pi i} {Q}}}$ ${\ displaystyle \ omega = e ^ {\ frac {2 \ pi i} {Q}}}$ ${\ displaystyle | x \ rangle}$ $| x \ rangle$ ${\ displaystyle Q}$ $Q$ ${\ displaystyle | y \ rangle}$ ${\ displaystyle | y \ rangle}$ ${\ displaystyle x}$ $X$
${\ displaystyle {U _ {\ operatorname {QFT}}} (| x \ rangle) = {\ frac {1} {\ sqrt {Q}}} \ sum _ {y = 0} ^ {Q-1} \ omega ^ {xy} | y \ rangle.}$
To vede k konečnému stavu
${\ displaystyle {\ frac {1} {Q}} \ součet _ {x = 0} ^ {Q-1} \ součet _ {y = 0} ^ {Q-1} \ omega ^ {xy} | y, f (x) \ rangle.}$
Nyní přeuspořádáme tuto částku jako
${\ displaystyle {\ frac {1} {Q}} \ součet _ {z = 0} ^ {N-1} \ součet _ {y = 0} ^ {Q-1} \ levá [\ součet _ {x \ v \ {0, \ ldots, Q-1 \}; ~ f (x) = z} \ omega ^ {xy} \ right] | y, z \ rangle.}$
Toto je superpozice mnohem více než států, ale mnohem méně než států, protože existuje méně než různých hodnot . Nechat ${\ displaystyle Q}$ $Q$ ${\ displaystyle Q ^ {2}}$ ${\ displaystyle Q ^ {2}}$ ${\ displaystyle Q}$ $Q$ ${\ displaystyle z = f (x)}$ ${\ displaystyle z = f (x)}$
- ${\ displaystyle \ omega = e ^ {\ frac {2 \ pi i} {Q}}}$ být -tým kořenem jednoty, ${\ displaystyle Q}$
- ${\ displaystyle r}$ být obdobím , ${\ displaystyle f}$
- ${\ displaystyle x_ {0}}$ být nejmenší z těch, pro které (máme ), a ${\ displaystyle x \ in \ {0, \ ldots, Q-1 \}}$ ${\ displaystyle f (x) = z}$ ${\ displaystyle x_ {0} <r}$
- napsat ${\ displaystyle m-1 = \ levá \ lfloor {\ frac {Q-x_ {0} -1} {r}} \ pravá \ rfloor}$
- ${\ displaystyle b}$ indexuje je , běží od do , takže . ${\ displaystyle x}$ ${\ displaystyle 0}$ ${\ displaystyle m-1}$ ${\ displaystyle x_ {0} + rb <Q}$
Pak je jednotkový vektor v komplexní rovině ( je kořenem jednoty a a jsou celá čísla) a koeficient v konečném stavu je ${\ displaystyle \ omega ^ {ry}}$ ${\ displaystyle \ omega ^ {ry}}$ ${\ displaystyle \ omega}$ $\ omega$ ${\ displaystyle r}$ $r$ ${\ displaystyle}$ $y$ ${\ displaystyle {\ dfrac {1} {Q}} \ vlevo | y, z \ vpravo \ rangle}$ ${\ displaystyle {\ dfrac {1} {Q}} \ vlevo | y, z \ vpravo \ rangle}$
${\ displaystyle \ sum _ {x \ in \ {0, \ ldots, Q-1 \}; ~ f (x) = z} \ omega ^ {xy} = \ sum _ {b = 0} ^ {m- 1} \ omega ^ {(x_ {0} + rb) y} = \ omega ^ {x_ {0} y} \ sum _ {b = 0} ^ {m-1} \ omega ^ {rby}.}$
Každý člen v tomto součtu představuje jinou cestu ke stejnému výsledku a dochází ke kvantové interferenci - konstruktivní, když jednotkové vektory směřují téměř stejným směrem v komplexní rovině, což vyžaduje tento bod podél
kladné reálné osy . ${\ displaystyle \ omega ^ {ryb}}$ ${\ displaystyle \ omega ^ {ry}}$
Proveďte měření. Získáváme nějaký výsledek ve vstupním registru a nějaký výsledek ve výstupním registru. Jak je periodické, pravděpodobnost měření určitého stavu je dána vztahem ${\ displaystyle}$ ${\ displaystyle z}$ ${\ displaystyle f}$ ${\ displaystyle | y, z \ rangle}$
${\ displaystyle \ mathrm {Pr} (| y, z \ rangle) = \ left | {\ frac {1} {Q}} \ sum _ {x \ in \ {0, \ ldots, Q-1 \}; ~ f (x) = z} \ omega ^ {xy} \ vpravo | ^ {2} = {\ frac {1} {Q ^ {2}}} \ vlevo | \ sum _ {b = 0} ^ {m -1} \ omega ^ {(x_ {0} + rb) y} \ doprava | ^ {2} = {\ frac {1} {Q ^ {2}}} | \ omega ^ {x_ {0} y} | ^ {2} \ left | \ sum _ {b = 0} ^ {m-1} \ omega ^ {bry} \ right | ^ {2}}$

${\ displaystyle = {\ frac {1} {Q ^ {2}}} \ vlevo | \ sum _ {b = 0} ^ {m-1} \ omega ^ {bry} \ vpravo | ^ {2} = { \ frac {1} {Q ^ {2}}} \ vlevo | {\ frac {\ omega ^ {mry} -1} {\ omega ^ {ry} -1}} \ vpravo | ^ {2} = {\ frac {1} {Q ^ {2}}} {\ frac {\ sin ^ {2} ({\ frac {\ pi mry} {Q}})}} \ \ sin ^ {2} ({\ frac {\ pi ry} {Q}})}}}$
Analýza nyní ukazuje, že tato pravděpodobnost je vyšší, čím blíže je jednotkový vektor ke kladné reálné ose, nebo čím blíže je celé číslo. Pokud to není síla , nebude to faktor . ${\ displaystyle \ omega ^ {ry}}$ ${\ displaystyle {\ dfrac {yr} {Q}}}$ ${\ displaystyle r}$ ${\ displaystyle 2}$ ${\ displaystyle Q}$
Protože je blízké nějakému celému číslu , známá hodnota je blízká neznámé hodnotě . Živé [klasické] pokračovala expanze podíl
na nám umožňuje nalézt aproximace o tom, že splňovat dvě podmínky: ${\ displaystyle {\ frac {yr} {Q}}}$ ${\ displaystyle {\ frac {yr} {Q}}}$ ${\ displaystyle c}$ $C$ ${\ displaystyle {\ dfrac {y} {Q}}}$ ${\ displaystyle {\ dfrac {y} {Q}}}$ ${\ displaystyle {\ dfrac {c} {r}}}$ ${\ displaystyle {\ dfrac {c} {r}}}$ ${\ displaystyle {\ dfrac {y} {Q}}}$ ${\ displaystyle {\ dfrac {y} {Q}}}$ ${\ displaystyle {\ dfrac {d} {s}}}$ ${\ displaystyle {\ dfrac {d} {s}}}$
1. ${\ displaystyle s <N}$ .
2. ${\ displaystyle \ left | {\ dfrac {y} {Q}} - {\ dfrac {d} {s}} \ right | <{\ dfrac {1} {2Q}}}$ .
Vzhledem k těmto mnohonásobným podmínkám (a za předpokladu, že je
neredukovatelné ), je velmi pravděpodobné, že bude vhodné období , nebo alespoň jeho faktor. ${\ displaystyle {\ dfrac {d} {s}}}$ ${\ displaystyle s}$ ${\ displaystyle r}$
Zkontrolujte (klasicky), zda . Pokud ano, pak jsme hotovi. ${\ displaystyle f (x) = f (x + s) \ šipka doleva a ^ {s} \ equiv 1 {\ bmod {N}}}$
Jinak (klasicky) získáte více kandidátů pomocí násobků nebo pomocí jiných s blízkým . Pokud některý kandidát funguje, pak jsme hotovi. ${\ displaystyle r}$ ${\ displaystyle s}$ ${\ displaystyle s}$ ${\ displaystyle {\ dfrac {d} {s}}}$ ${\ displaystyle {\ dfrac {y} {Q}}}$
Jinak zkuste znovu začít od kroku 1 tohoto podprogramu.

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ž a souběžně s tvoří multiplikativní skupinu celých čísel modulo , což je konečná abelianská skupina . Velikost této skupiny je dána vztahem . Na konci kroku 3 máme v této skupině celé číslo . Protože skupina je konečná, musí mít konečné pořadí , což je nejmenší kladné celé číslo ${\ displaystyle N}$ ${\ displaystyle N}$ ${\ displaystyle N}$ ${\ displaystyle G}$ ${\ displaystyle \ varphi (N)}$ ${\ displaystyle a}$ ${\ displaystyle a}$ ${\ displaystyle r}$

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

Proto dělí (také písemně ). Předpokládejme, že jsme schopni získat a že je to rovnoměrné. (Pokud je liché, pak v kroku 5 musíme restartovat algoritmus s jiným náhodným číslem ) Nyní je druhá odmocnina modulo, která se liší od . Je to proto, že je to pořadí modulo , jinak by bylo pořadí v této skupině takové . Pokud tedy v kroku 6 musíme restartovat algoritmus s jiným náhodným číslem . ${\ displaystyle N}$ ${\ displaystyle a ^ {r} -1}$ ${\ displaystyle N \ mid a ^ {r} -1}$ ${\ displaystyle r}$ ${\ displaystyle r}$ ${\ displaystyle a}$ ${\ displaystyle b \ equiv a ^ {r / 2} {\ bmod {N}}}$ ${\ displaystyle 1}$ ${\ displaystyle N}$ ${\ displaystyle 1}$ ${\ displaystyle r}$ ${\ displaystyle a}$ ${\ displaystyle N}$ ${\ displaystyle a ^ {r / 2} \ not \ equiv 1 {\ bmod {N}}}$ ${\ displaystyle a}$ ${\ displaystyle {\ dfrac {r} {2}}}$ ${\ displaystyle a ^ {r / 2} \ equiv -1 {\ bmod {N}}}$ ${\ displaystyle a}$

Nakonec musíme hit provoz v taková, že . Důvodem je, že taková a je druhá odmocnina modulo jiné než a , jehož existence je zaručena čínskou větou o zbytku, protože to není hlavní síla. ${\ displaystyle a}$ ${\ displaystyle r}$ ${\ displaystyle G}$ ${\ displaystyle b \ equiv a ^ {r / 2} \ not \ equiv \ pm 1 {\ bmod {N}}}$ ${\ displaystyle b}$ ${\ displaystyle 1}$ ${\ displaystyle N}$ ${\ displaystyle 1}$ ${\ displaystyle -1}$ ${\ displaystyle N}$

Tvrdíme, že je to vhodný faktor , tj . Ve skutečnosti, pokud , pak se rozdělí , takže to , což jde proti konstrukci . Pokud na druhou stranu, pak podle Bézoutovy identity existují celá taková celá čísla ${\ displaystyle d = \ gcd (b-1, N)}$ ${\ displaystyle N}$ ${\ displaystyle d \ neq 1, N}$ ${\ displaystyle d = N}$ ${\ displaystyle N}$ ${\ displaystyle b-1}$ ${\ displaystyle b \ equiv 1 {\ bmod {N}}}$ ${\ displaystyle b}$ ${\ displaystyle d = \ gcd (b-1, N) = 1}$ ${\ displaystyle u, v}$

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

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

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

Jako dělení zjistíme, že dělí , takže to opět odporuje konstrukci . ${\ displaystyle N}$ ${\ displaystyle b ^ {2} -1 \ equiv a ^ {r} -1 {\ bmod {N}}}$ ${\ displaystyle N}$ ${\ displaystyle b + 1}$ ${\ displaystyle b \ equiv -1 {\ bmod {N}}}$ ${\ displaystyle b}$

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

Nalezení období

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

Fyzici nazývají toto chování „ superpozicí “ stavů. Abychom vypočítali periodu funkce , vyhodnotíme funkci ve všech bodech současně. ${\ displaystyle f}$

Kvantová fyzika nám však neumožňuje přímý přístup ke všem těmto informacím. Měření se získá pouze jeden ze všech možných hodnot, ničí všechny ostatní. Pokud ne pro klonovací teorém , mohli bychom nejprve měřit bez měření a poté vytvořit několik kopií výsledného stavu (což je superpozice stavů, které mají všechny stejné ). Měření na těchto stavech by poskytlo různé hodnoty, které dávají stejné , což by vedlo k období. Protože nemůžeme vytvořit 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 kvantovou Fourierovou transformací . ${\ displaystyle f (x)}$ ${\ displaystyle x}$ ${\ displaystyle f (x)}$ ${\ displaystyle x}$ ${\ displaystyle x}$ ${\ displaystyle f (x)}$

Shor tak musel vyřešit tři „implementační“ problémy. Všechny z nich měla být provedena „rychle“, což znamená, že mohou být realizovány s řadou kvantových bran , který je polynom v . ${\ displaystyle \ log N}$

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

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

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

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

Poznámka: Dalším způsobem, jak vysvětlit Shorův algoritmus, je poznamenat, že se jedná pouze o maskovaný algoritmus odhadu kvantové fáze .

Úzké místo

Runtime úzkým místem Shorova algoritmu je kvantová modulární umocňování , která je mnohem pomalejší než kvantová Fourierova transformace a klasické pre- / post-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 s reverzibilními branami , počínaje sčítáním zvlnění . Znalost základu a modulu umocňování usnadňuje další optimalizace. Reverzibilní obvody se obvykle používají v řádu bran pro qubits. Alternativní techniky asymptoticky zlepšují počty hradel pomocí kvantových Fourierových transformací , ale nejsou konkurenceschopné s méně než 600 qubitů kvůli vysokým konstantám. ${\ displaystyle n ^ {3}}$ ${\ displaystyle n}$

Diskrétní logaritmy

Vzhledem k tomu, skupiny s cílem a generátorem , předpokládám, že víme, že pro některé , a chceme spočítat , což je diskrétní logaritmus : . Zvažte abelianskou skupinu , kde každý faktor odpovídá modulárnímu sčítání hodnot. Nyní zvažte funkci ${\ displaystyle G}$ ${\ displaystyle p}$ ${\ displaystyle g \ v G}$ ${\ displaystyle x = g ^ {r} \ v G}$ ${\ displaystyle r \ in \ mathbb {Z} _ {p}}$ ${\ displaystyle r}$ ${\ displaystyle r = {\ log _ {g}} (x)}$ ${\ displaystyle \ mathbb {Z} _ {p} \ krát \ mathbb {Z} _ {p}}$

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

To nám dává problém abelianské skryté podskupiny , který odpovídá skupinovému homomorfismu . Jádro odpovídá násobkům . Takže pokud najdeme jádro, můžeme najít . ${\ displaystyle f}$ ${\ displaystyle (r, 1)}$ ${\ displaystyle r}$

Viz také

GEECM , faktorizační algoritmus, o kterém se říká, že je „často mnohem rychlejší než Shorův“
Groverův algoritmus

Reference

Další čtení

Nielsen, Michael A. & Chuang, Isaac L. (2010), Kvantové výpočty a kvantové informace, 10. výročí , Cambridge University Press, ISBN 9781107002173.
Phillip Kaye, Raymond Laflamme, Michele Mosca, An Introduction to Quantum Computing , Oxford University Press, 2007, ISBN 0-19-857049-X
„Vysvětlení pro muže na ulici“ od Scotta Aaronsona , „ schváleno “ Peterem Shorem. (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 kdy viděl.)“. V jednom z komentářů byla uvedena alternativní metafora pro QFT . Scott Aaronson navrhuje následujících 12 odkazů jako další čtení (z „10 ^{10 ^{5 000}} cvičení 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 “).
Quantum Computing and Shor's Algorithm , Matthew Hayward's Quantum Algorithms Page , 2005-02-17, imsa.edu, LaTeX2HTML verze původního dokumentu LaTeX , dostupná také jako PDF nebo postscriptový dokument.
Kvantové výpočty 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čty: tutoriál od Samuela L. Braunsteina .
Kvantové stavy Shorova algoritmu , autor: Neal Young, poslední změna: Út 21. května 11:47:38 1996.
III. Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm , Lecture notes on Quantum computation, Cornell University, Physics 481–681, CS 483; Jaro 2006 N. David Mermin. Poslední revize 2006-03-28, 30stránkový dokument PDF.
Lavor, C .; Manssur, LRU; 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žitosti: 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 směrem k kvantovému výpočtu: zapletení 10 miliard částic , z časopisu „Discover Magazine“, ze dne 19. ledna 2011.
Josef Gruska - Výzvy kvantové výpočetní techniky také v matematice 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 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í.
Série PBS Infinite vytvořila dvě videa vysvětlující matematiku, která stojí za Shorovým algoritmem, „ How to Break Cryptography “ a „ Hacking at Quantum Speed with Shor's Algorithm “.

Languages

In other projects