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]

Vaata ka

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

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
↑ 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] 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]