Shori kvantfaktoringu algoritm pakub tõepoolest klassikaliste algoritmidega võrreldes eksponentsiaalset kiirust suurte arvude algtegurite leidmisel. See matemaatik Peter Shori poolt 1994. aastal välja töötatud algoritm on kvantarvutuses pöördeline edasiminek. See kasutab kvantomadusi, nagu superpositsioon ja takerdumine, et saavutada peamiste faktorite määramisel märkimisväärne tõhusus.
Klassikalises andmetöötluses on kõige tuntum suurte arvude faktoriseerimise algoritm General Number Field Sieve (GNFS). GNFS-i ajaline keerukus on subeksponentsiaalne, mis tähendab, et selle käitusaeg kasvab kiiremini kui polünoomiaeg, kuid aeglasemalt kui eksponentsiaalne aeg. See omadus muudab selle ebatõhusaks äärmiselt suurte arvude faktoorimisel, eriti nende puhul, mida kasutatakse tänapäevastes krüptosüsteemides.
Shori algoritm seevastu töötab kvantarvutis ja sellel on polünoomne ajaline keerukus. See võib O((log N)^3) operatsioonides faktoriseerida suure täisarvu N, mis on eksponentsiaalselt kiirem kui mis tahes tuntud klassikaline algoritm. See eksponentsiaalne kiirendus tuleneb kvant-Fourieri teisendusest ja perioodi leidmise sammudest Shori algoritmis, mis võimaldab tõhusalt leida N algtegurid.
Shori algoritmi pakutava eksponentsiaalse kiirendamise illustreerimiseks kaaluge 2048-bitise arvu faktoriseerimist, mida tavaliselt kasutatakse RSA krüptimisel. Klassikalise arvuti puhul, mis kasutab GNFS-i, võtaks sellise arvu faktoorikaks arvestamine mõeldamatult kaua aega, ületades potentsiaalselt universumi vanuse. Seevastu kvantarvutis rakendatud Shori algoritm võib selle eksponentsiaalse kiiruse tõttu mõistliku aja jooksul faktoriseerida sama 2048-bitise arvu.
Siiski on oluline märkida, et Shori algoritmi eksponentsiaalne kiirendus ei ole kõigi stsenaariumide puhul absoluutne. Algoritmi efektiivsus sõltub suuresti suuremahulise veaparandusega kvantarvuti olemasolust. Praegusel tehnoloogilisel maastikul on sellise kvantarvuti ehitamine endiselt suur väljakutse selliste tegurite tõttu nagu dekoherentsus, veamäär ja kubitiühenduse piirangud.
Lisaks on Shori algoritmi turvalisuse tagajärjed sügavad. Selle võime suuri numbreid tõhusalt arvesse võtta ohustab laialdaselt kasutatavaid krüptosüsteeme, nagu RSA, mis sõltuvad turvalisuse peamise faktoriseerimise raskusest. Suuremahuliste kvantarvutite tulek, mis on võimelised töötama Shori algoritmi, võib muuta need krüptosüsteemid rünnakute suhtes haavatavaks, mistõttu on vaja välja töötada kvantkindlad krüptograafilised skeemid.
Shori kvantfaktoringu algoritm pakub eksponentsiaalset kiirust suurte arvude algtegurite leidmisel, näidates kvantarvutuse võimsust arvutusmahukate probleemide lahendamisel. Kuigi selle teoreetiline tõhusus on võrreldamatu, on praktiline rakendamine suuremahulises tõrketaluvetes kvantarvutis endiselt kriitilise tähtsusega verstapost selle täieliku potentsiaali realiseerimiseks ja sellega seotud turvamõjudega tegelemiseks.
Muud hiljutised küsimused ja vastused selle kohta EITC/QI/QIF kvantteabe alused:
- Kuidas kvanteituse värav (kvant EI või Pauli-X värav) töötab?
- Miks on Hadamardi värav isepööratav?
- Kui mõõta Belli oleku 1. kubitit teatud baasis ja seejärel mõõta 2. kubitit teatud nurga teeta võrra pööratud baasis, on tõenäosus, et saate vastava vektori projektsiooni, võrdub teeta siinuse ruuduga?
- Mitu bitti klassikalist teavet oleks vaja suvalise kubiti superpositsiooni oleku kirjeldamiseks?
- Mitme mõõtme ruum on 3 kubitit?
- Kas kubiidi mõõtmine hävitab selle kvantsuperpositsiooni?
- Kas kvantväravatel võib sarnaselt klassikalistel väravatel olla rohkem sisendeid kui väljundeid?
- Kas kvantväravate universaalsesse perekonda kuuluvad CNOT värav ja Hadamardi värav?
- Mis on kahe piluga katse?
- Kas polariseeriva filtri pööramine on samaväärne footonite polarisatsiooni mõõtmise aluse muutmisega?
Vaadake rohkem küsimusi ja vastuseid jaotisest EITC/QI/QIF Quantum Information Fundamentals