Shori algoritm

Shori algoritm on kvantarvutusalgoritm täisarvu algtegurite leidmiseks. Selle töötas välja Ameerika matemaatik Peter Shor aastal 1994.^[1]^[2] See on üks väheseid teadaolevaid kvantarvutuse algoritme, millel on veenvad potentsiaalsed rakendused ja tugevad tõendid superpolünoomse kiirenduse kohta võrreldes parimate tuntud klassikaliste (mittekvantiliste) algoritmidega.^[3] Teisalt nõuab piisavalt suurte arvude tegurdamine palju rohkem kvantbitte, kui on lähitulevikus saadaval.^[4] Teine probleem on see, et kvantahelates tekkiv müra võib tulemusi rikkuda,^[5] mis nõuab kvantvigade korrigeerimiseks täiendavaid kvantbitte.

Shor pakkus välja mitmeid sarnaseid algoritme tegurdamisülesande, diskreetse logaritmi ülesande ja perioodi leidmise ülesande lahendamiseks. Shori algoritm viitab tavaliselt tegurdamisalgoritmile, kuid võib tähendada ka ükskõik millist neist kolmest algoritmist. Diskreetse logaritmi algoritm ja tegurdamisalgoritm on perioodi leidmise algoritmi juhtumid ning kõik kolm on varjatud alamgrupi probleemi juhtumid.^[6]

Kvantarvutis töötab Shori algoritm täisarvu $N$ tegurdamiseks polünoomses ajas, mis tähendab, et kuluv aeg on polünoomne $logN$ suhtes.^[6] See kasutab kiire korrutamise korral kvantväravaid suurusjärgus $O((logN)^{2}(loglogN)(logloglogN))$ ,^[7] või isegi $O((logN)^{2}(loglogN))$ , kasutades asümptootiliselt kõige kiiremat praegu teadaolevat korrutamisalgoritmi, mille töötasid välja Harvey ja Van Der Hoven,^[8] seega näidates, et täisarvu tegurdamise probleemi saab kvantarvutis tõhusalt lahendada ning see kuulub keerukusklassi BQP. See on oluliselt kiirem kui kõige tõhusam teadaolev klassikaline tegurdamisalgoritm, üldine arvuvälja sõel (Inglise General number field sieve), mis töötab subeksponentsiaalses ajas: $O(e^{1,9(logN)^{\tfrac {1}{3}}}(loglogN)^{\tfrac {2}{3}})$ .^[9]

Teostatavus ja mõju

Kui kvantarvuti piisava arvu kvantbittidega suudaks töötada ilma kvantmüra ja muude kvantdekoherentsi nähtusteta, võiks Shori algoritmi kasutada avaliku võtme krüptoskeemide murdmiseks, näiteks:^[10]

RSA skeem

Lõpliku korpuse Diffie-Hellmani võtmevahetus

Elliptilise kõvera Diffie-Hellmani võtmevahetus^[10]

RSA põhineb eeldusel, et suurte täisarvude tegurdamine on arvutuslikult keerukas ja aeganõudev. Praegu teadaolevalt kehtib see eeldus klassikaliste (mittekvantiliste) arvutite puhul; ühtegi klassikalist algoritmi ei ole leitud, mis suudaks täisarve polünoomses ajas tegurdada. Kuid Shori algoritm näitab, et täisarvude tegurdamine on ideaalsetes tingimustes kvantarvutis tõhus, seega võib kvantarvutiga olla võimalik RSA murdmine.

Shori algoritm oli ka võimas motivaator kvantarvutite kavandamiseks ja ehitamiseks ning uute kvantarvutuse algoritmide uurimiseks. See on soodustanud uurimistööd uute krüptosüsteemide loomisel, mis oleksid kvantarvutite suhtes turvalised, ja neid nimetatakse ühiselt post-kvantkrüptograafiaks.^[11]

Füüsiline teostus

Arvestades kaasaegsete kvantarvutite kõrgeid veamäärasid ja liiga väheseid kvantbitte kvantvigade korrigeerimise kasutamiseks, saavutatakse laboratoorsetes katsetes õigeid tulemusi ainult murdosa katsete puhul.

2001. aastal demonstreeris IBM-i uurimisrühm Shori algoritmi, tegurdades arvu $15$ teguriteks $(3\times 5)$ , kasutades NMR-tehnoloogial (tuuma magnetresonantsil) põhinevat kvantarvutit seitsme kvantbitiga.^[11]

Vaata ka

GEECM (inglise Generalized Elliptic Curve Method) on tegurdamisalgoritm, mida peetakse sageli "palju kiiremaks" kui Shori oma
Groveri algoritm^[12]

Viited

↑ Goldwasser, Shafi; IEEE Computer Society, toim-d (1994). Proceedings / 35th Annual Symposium on Foundations of Computer Science, November 20 - 22, 1994, Santa Fe, New Mexico. Los Alamitos, Calif.: IEEE Computer Society Press. ISBN 978-0-8186-6580-6.
↑ Shor, Peter W. (10. oktoober 1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing (inglise). 26 (5): 1484–1509. DOI:10.1137/S0097539795293172. ISSN 0097-5397.
↑ Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum computation and quantum information (10th anniversary edition trükk). Cambridge: Cambridge university press. ISBN 978-1-107-00217-3.
↑ Gidney, Craig; Ekerå, Martin (15. aprill 2021). "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits". Quantum (inglise). 5: 433. DOI:10.22331/q-2021-04-15-433. ISSN 2521-327X.
↑ Cai, Jin-Yi (juuli 2024). "Shor's algorithm does not factor large integers in the presence of noise". Science China Information Sciences (inglise). 67 (7). DOI:10.1007/s11432-023-3961-3. ISSN 1674-733X.
↑ ^6,0 ^6,1 "Pseudo-polynomial time", Wikipedia (inglise), 4. detsember 2023, vaadatud 24. oktoobril 2024
↑ Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1. august 1996). "Efficient networks for quantum factoring". Physical Review A (inglise). 54 (2): 1034–1063. DOI:10.1103/PhysRevA.54.1034. ISSN 1050-2947.
↑ Harvey, David; van der Hoeven, Joris (1. märts 2021). "Integer multiplication in time $O(n\mathrm{log}\, n)$". Annals of Mathematics. 193 (2). DOI:10.4007/annals.2021.193.2.4. ISSN 0003-486X.
↑ Weisstein, Eric W. "Number Field Sieve". mathworld.wolfram.com (inglise). Vaadatud 25. oktoobril 2024.
↑ ^10,0 ^10,1 Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin (2017), Takagi, Tsuyoshi; Peyrin, Thomas (toim-d), "Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms", Advances in Cryptology – ASIACRYPT 2017 (inglise), Cham: Springer International Publishing, kd 10625, lk 241–270, DOI:10.1007/978-3-319-70697-9_9, ISBN 978-3-319-70696-2, vaadatud 25. oktoobril 2024
↑ ^11,0 ^11,1 Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H.; Chuang, Isaac L. (detsember 2001). "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance". Nature (inglise). 414 (6866): 883–887. DOI:10.1038/414883a. ISSN 0028-0836.
↑ Bernstein, Daniel J.; Heninger, Nadia; Lou, Paul; Valenta, Luke (2017), Lange, Tanja; Takagi, Tsuyoshi (toim-d), "Post-quantum RSA", Post-Quantum Cryptography (inglise), Cham: Springer International Publishing, kd 10346, lk 311–329, DOI:10.1007/978-3-319-59879-6_18, ISBN 978-3-319-59878-9, vaadatud 24. oktoobril 2024

[1] Goldwasser, Shafi; IEEE Computer Society, toim-d (1994). Proceedings / 35th Annual Symposium on Foundations of Computer Science, November 20 - 22, 1994, Santa Fe, New Mexico. Los Alamitos, Calif.: IEEE Computer Society Press. ISBN 978-0-8186-6580-6.

[2] Shor, Peter W. (10. oktoober 1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing (inglise). 26 (5): 1484–1509. DOI:10.1137/S0097539795293172. ISSN 0097-5397.

[3] Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum computation and quantum information (10th anniversary edition trükk). Cambridge: Cambridge university press. ISBN 978-1-107-00217-3.

[4] Gidney, Craig; Ekerå, Martin (15. aprill 2021). "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits". Quantum (inglise). 5: 433. DOI:10.22331/q-2021-04-15-433. ISSN 2521-327X.

[5] Cai, Jin-Yi (juuli 2024). "Shor's algorithm does not factor large integers in the presence of noise". Science China Information Sciences (inglise). 67 (7). DOI:10.1007/s11432-023-3961-3. ISSN 1674-733X.

[:0-6] 6,0 ^6,1 "Pseudo-polynomial time", Wikipedia (inglise), 4. detsember 2023, vaadatud 24. oktoobril 2024

[7] Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1. august 1996). "Efficient networks for quantum factoring". Physical Review A (inglise). 54 (2): 1034–1063. DOI:10.1103/PhysRevA.54.1034. ISSN 1050-2947.

[8] Harvey, David; van der Hoeven, Joris (1. märts 2021). "Integer multiplication in time $O(n\mathrm{log}\, n)$". Annals of Mathematics. 193 (2). DOI:10.4007/annals.2021.193.2.4. ISSN 0003-486X.

[9] Weisstein, Eric W. "Number Field Sieve". mathworld.wolfram.com (inglise). Vaadatud 25. oktoobril 2024.

[:1-10] 10,0 ^10,1 Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin (2017), Takagi, Tsuyoshi; Peyrin, Thomas (toim-d), "Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms", Advances in Cryptology – ASIACRYPT 2017 (inglise), Cham: Springer International Publishing, kd 10625, lk 241–270, DOI:10.1007/978-3-319-70697-9_9, ISBN 978-3-319-70696-2, vaadatud 25. oktoobril 2024

[:2-11] 11,0 ^11,1 Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H.; Chuang, Isaac L. (detsember 2001). "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance". Nature (inglise). 414 (6866): 883–887. DOI:10.1038/414883a. ISSN 0028-0836.

[12] Bernstein, Daniel J.; Heninger, Nadia; Lou, Paul; Valenta, Luke (2017), Lange, Tanja; Takagi, Tsuyoshi (toim-d), "Post-quantum RSA", Post-Quantum Cryptography (inglise), Cham: Springer International Publishing, kd 10346, lk 311–329, DOI:10.1007/978-3-319-59879-6_18, ISBN 978-3-319-59878-9, vaadatud 24. oktoobril 2024

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]