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 ${\displaystyle N}$ tegurdamiseks polünoomses ajas, mis tähendab, et kuluv aeg on polünoomne ${\displaystyle logN}$ suhtes.^[6] See kasutab kiire korrutamise korral kvantväravaid suurusjärgus ${\displaystyle O((logN)^{2}(loglogN)(logloglogN))}$,^[7] või isegi ${\displaystyle 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: ${\displaystyle 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 ${\displaystyle 15}$ teguriteks ${\displaystyle (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]