Leta 1994 je matematik ugotovil, kako narediti kvantni računalnik, da naredi nekaj, česar noben navaden klasičen računalnik ne zmore. Delo je razkrilo, da bi načeloma lahko stroj, ki temelji na pravilih kvantne mehanike, učinkovito razdelil veliko število na svoje glavne faktorje – naloga, ki je tako težka za klasičen računalnik, da predstavlja osnovo za večino današnje internetne varnosti.
Sledil je val optimizma. Morda, so mislili raziskovalci, bomo lahko izumili kvantne algoritme, ki lahko rešijo ogromno različnih problemov.
Toda napredek je zastal. "To je bila nekoliko slaba pot," je rekel Ryan O'Donnell Univerze Carnegie Mellon. "Ljudje so si mislili:" To je neverjetno, prepričan sem, da bomo dobili vse vrste drugih neverjetnih algoritmov. "Ne." Znanstveniki so odkrili dramatične pospešitve le za en sam, ozek razred problemov znotraj standardnega niza imenovan NP, kar pomeni, da so imeli učinkovito preverljive rešitve – kot je faktoring.
Tako je bilo skoraj tri desetletja. Nato aprila raziskovalci izumil bistveno nova vrsta problema, ki bi ga moral kvantni računalnik rešiti eksponentno hitreje kot klasični. Vključuje izračun vhodnih podatkov v zapleten matematični proces, ki temelji izključno na njegovih zmešanih rezultatih. Ali je problem samostojen ali je prvi na novi meji mnogih drugih, je treba še ugotoviti.
"Obstaja občutek vznemirjenja," je rekel Vinod Vaikuntanathan, računalničar na tehnološkem inštitutu Massachusetts. "Veliko ljudi razmišlja o tem, kaj je še tam zunaj."
Računalniški znanstveniki poskušajo razumeti, kaj so kvantni računalniki boljši s preučevanjem matematičnih modelov, ki jih predstavljajo. Pogosto si predstavljajo model kvantnega ali klasičnega računalnika v kombinaciji z idealiziranim računskim strojem, imenovanim orakelj. Orakli so kot preproste matematične funkcije ali računalniški programi, ki sprejmejo vhod in izpljunejo vnaprej določen izhod. Morda imajo naključno vedenje, izpišejo »da«, če vnos spada v določen naključni obseg (recimo 12 do 67), in »ne«, če ne. Lahko pa so periodični, tako da vnos med 1 in 10 vrne »da«, 11 do 20 daje »ne«, 21 do 30 ponovno proizvede »da« in tako naprej.
Recimo, da imate enega od teh periodičnih orakljev in ne poznate obdobja. Vse, kar lahko storite, je, da mu podate številke in vidite, kaj oddaja. Kako hitro bi lahko računalnik s temi omejitvami našel točko? Leta 1993 je Daniel Simon, takrat na univerzi v Montrealu, ugotovil, da lahko kvantni algoritem izračuna odgovor na tesno povezan problem eksponentno hitreje kot kateri koli klasični algoritem.
Rezultat je Simonu omogočil določitev enega prvih namigov o tem, kje bi lahko pričakovali dramatično premoč kvantnih računalnikov. Ko pa je svoj prispevek predložil vodilni konferenci, so ga zavrnili. Prispevek pa je zanimal mlajšega člana programskega odbora konference - Peter Šor, ki je bil takrat v Bell Laboratories v New Jerseyju. Shor je nato ugotovil, da bi lahko prilagodil Simonov algoritem za izračun obdobja oraklja, če bi ga imel. Potem je spoznal, da bi lahko še enkrat prilagodil algoritem, da bi rešil enačbo, ki se obnaša podobno kot periodični orakelj: enačbo, ki opisuje faktoring, ki je periodična.
Šorov rezultat je bil zgodovinski. Kvantni algoritem, ki ga je odkril, bi lahko hitro reduciral velikanska števila na njihove sestavne prafaktorje, česar ne zmore noben znani klasični algoritem. V letih, ki so sledila, so raziskovalci odkrili druge učinkovite kvantne algoritme. Nekateri od njih, kot je Shorov algoritem, so celo zagotovili eksponentno prednost, vendar nihče ni mogel dokazati dramatične kvantne prednosti pri katerem koli problemu NP, ki ni bil periodičen.
To pomanjkanje napredka je vodilo dva računalniška znanstvenika, Scott Aaronson Teksaške univerze v Austinu in Andris Ambainis Univerze v Latviji, da poda pripombo. Dokazi o kvantni prednosti so se vedno zdeli odvisni od orakljev, ki so imeli nekakšno nenaključno strukturo, kot je periodičnost. Leta 2009 so domneval da pri problemih NP, ki so naključni ali nestrukturirani, ne more biti dramatičnih pospešitev. Nihče ni našel izjeme.
Njihova domneva je omejila moč kvantnih računalnikov. Vendar je pisalo le, da ni bilo dramatičnih pospešitev za določeno vrsto nestrukturiranega problema NP – tistih z odgovorom da ali ne. Če je težava vključevala iskanje bolj specifičnih, kvantitativnih odgovorov, kar je znano kot težava iskanja, domneva ni veljala.
S tem v mislih raziskovalci Takashi Yamakawa Laboratorijev za družbeno informatiko NTT in Mark Zhandry z NTT Research in Univerze Princeton sta se odločila eksperimentirati s posebnim iskalnim problemom, ki ga je leta 2005 predstavil Oded Regev.
Predstavljajte si niz vremenskih loput, ki so vse usmerjene v isto smer. Vsakega od njih odmerjeno potisnite, nato pa pustite, da sunkovit veter vpliva na njihovo smer. Regev je na podlagi njunih končnih smeri želel ugotoviti, kam so vse najprej usmerili. Težave, kot je ta, so poimenovali »učenje z napakami«, ker sunek in veter delujeta kot vir naključne napake na prvotni smeri. Obstajajo dokazi, da ga je težko rešiti tako za klasične kot za kvantne algoritme.
Yamakawa in Zhandry sta prilagodila nastavitev. Spremenili so moč teh začetnih udarcev in jih naredili bolj predvidljive. Povzročili so tudi, da je veter določil naključni orakelj, tako da je bil v nekaterih primerih še bolj naključen, v drugih pa popolnoma mirujoč.
S temi spremembami so raziskovalci odkrili, da lahko kvantni algoritem učinkovito najde začetno smer. Dokazali so tudi, da mora biti vsak klasični algoritem počasnejši za eksponentni faktor. Tako kot Shor so nato prilagodili svoj algoritem za rešitev resnične različice problema, ki nadomešča orakelj z dejansko matematično enačbo.
Računalniški znanstveniki si še vedno prizadevajo razumeti in nadgraditi problem. Vaikuntanathan ga primerja z drugim, ki se pojavi pri stiskanju podatkov: Ko se informacije stisnejo navzdol, se lahko dva bita pomotoma stisneta na isto mesto in ju prepišeta. Težava vnaprejšnjega napovedovanja teh trkov, da se jim lahko izognete, je nekoliko podobna. "To je vrsta problemov, ki v bistvu izgledajo takole," je dejal. "Mogoče je te težave mogoče rešiti kvantno."
Obstajalo je upanje, da bi bil nestrukturiran problem, kot je novi, morda rešljiv celo na današnjih novonastalih različicah kvantnih računalnikov, s čimer bi zagotovili sredstva za njihovo testiranje. Razmišljanje je bilo, da lahko nestrukturirani problemi zahtevajo manj sredstev za programiranje ali pa so manj občutljivi na hrup, saj so že naključni. Toda do zdaj se zdi, da je nova težava še vedno preveč napredna, da bi jo rešili obstoječi kvantni računalniki. »To je čudna težava. Nisem pomislil, da bi ga definiral,« je dejal Aaronson. "Toda v retrospektivi ima nekaj zelo lepih lastnosti."
Rezultat je prvi primer dramatične kvantne prednosti pri nestrukturiranem problemu NP. Ali lahko obstaja veliko drugih problemov, ki jih kvantni svet spremeni iz praktično nerešljivih v rešljive? Zdaj je več razlogov za tako mnenje.
"To je nekoliko obrnilo naša prepričanja o tem, pri kakšnih težavah so lahko kvantni računalniki dobri," je dejal O'Donnell.
