Revija Joker - Nasledniki enic in ničel

ČLANKI
stranka » članki » vedež » Nasledniki enic in ničel

Umetnost algoritmov
Kako pa vemo, da se bo superpozicija vseh mogo­čih vrednosti, ki gre skozi operacije, na koncu 'podrla' v pravo rešitev? V ta namen moramo operacije z logičnimi vrati postaviti v pravo zaporedje ali tako imenovani kvantni algoritem. Končna sekvenca je odvisna od raznih verjetnosti in naloga snovalca takega algoritma je, da ga zasnuje na način, da bo pravilna rešitev imela največ verjetnos­ti, da jo izmerimo. To je dokazano mogoče in pome­ni, da se v praksi računanje nekajkrat ponovi, nakar največ­krat dobljeno rešitev preverimo z navadnim ra­ču­nal­nikom. Za primere, ki zahtevajo rabo kvant­nih naprav, je to še vedno mnogo hitrejše od klasične digitalne poti. Iz tega je razvidno, da bo sestavljanje vezij kvantnih računalnikov in programiranje zanje za stopnjo zahtevnejša naloga od tiste na današnjih pecejih.

Eno od mnogih razkritij Edwarda Snowdena po njegovem prebegu je tudi tisto, da ameriška agencija NSA (tu njen sedež v Marylandu) že dlje časa pridno raziskuje kvantne načine razbijanja šifer.

Uspešni kvantni programski postopki so pomembni izumi sami zase. Za enega najbolj elegantnih velja Shorov algoritem za faktorizacijo celih števil, ki ga je ameriški matematik Peter Shor podal leta 1994. Z njim je moč najti vsa praštevila, ki so delitelji danega naravnega števila. To je izjemno pomembno za varovanje podatkov, saj se mnogi šifrirni algoritmi, kot je RSA, zanašajo ravno na dejstvo, da je faktorizacija zelo velikih števil za digitalne raču­nal­nike presneto trd oreh. Če bi dali število z deset tisoč ciframi faktorizirati navadnemu superraču­nalni­ku, bi naš kozmos prej izdihnil, kot bi dobili rešitev. Shorov algoritem bi z nekaj deset tisoč kubiti nalogo opravil v minuti. Takšna zmogljivost bi v hipu strla dobršen del današnjih šifrirnih ključev, pod­roč­je kriptografije postavila na glavo in ogrozila mnoge državne tajne. Ravno zato pomembne varnostne ustanove, tudi ameriški CIA in NSA, zelo pozorno spremljajo tovrsten razvoj. 
Drug praktični primer je dve leti po Shoru pokazal Lov Grover, in sicer za iskanje po neurejenih bazah podatkov. Klasični postopek bi moral v iskanju podatka s seznama z deset tisoč postavkami v povprečju sprožiti pet tisoč poizvedb. Groverjev algoritem bi za enak rezultat porabil samo sto poizvedb in je torej kvadratno hitrejši. Shor in Grover sta s tem sodobna posnemovalca Ade Lovelace, prve programerke izpred dvesto let. Toda kvantni algoritmi niso vsemogočni. V prvi vrsti obstajajo problemi, ki jih matematiki imenujejo NP-polni, ki jih kvantni raču­nal­­ni­ki ne bodo reševali nič hitreje kot digitalni! Mo­žen je prenos vsega šifriranja na postopke, ki so odporni ali imuni na kvantno razbijanje, in takšne na­či­ne že razvijajo. Predvsem pa pravega splošnega kvant­nega kalkulatorja z dovolj kubiti, da bi lahko res preračunaval nove reči, sploh še nismo sestavili.

Nasledniki enic in ničel objavljeno: Joker 281
december 2016