Shori algoritm

Shori algoritm on kvantarvutusalgoritm täisarvu algtegurite leidmiseks. Selle töötas välja Ameerika matemaatik Peter Shor aastal 1994. 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. Teisalt nõuab piisavalt suurte arvude tegurdamine palju rohkem kvantbitte, kui on lähitulevikus saadaval. Teine probleem on see, et kvantahelates tekkiv müra võib tulemusi rikkuda, 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.

Kvantarvutis töötab Shori algoritm täisarvu  tegurdamiseks polünoomses ajas, mis tähendab, et kuluv aeg on polünoomne  suhtes. See kasutab kiire korrutamise korral kvantväravaid suurusjärgus , või isegi , kasutades asümptootiliselt kõige kiiremat praegu teadaolevat korrutamisalgoritmi, mille töötasid välja Harvey ja Van Der Hoven, 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: .

 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:

 RSA skeem

 Lõpliku korpuse Diffie-Hellmani võtmevahetus

 Elliptilise kõvera Diffie-Hellmani võtmevahetus

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.

 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  teguriteks , kasutades NMR-tehnoloogial (tuuma magnetresonantsil) põhinevat kvantarvutit seitsme kvantbitiga.

 Vaata ka 

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

 Viited 

Kategooria:Kvantmehaanika
Kategooria:Algoritmid