1994-ben egy matematikus kitalálta, hogyan lehet egy kvantumszámítógépet olyasmire bírni, amire egyetlen klasszikus számítógép sem képes. A munka feltárta, hogy elvileg a kvantummechanika szabályaira épülő gépek nagy számot tud hatékonyan felosztani elsődleges tényezőire – ez a feladat olyan nehéz egy klasszikus számítógép számára, hogy a mai internetbiztonság nagy részének alapját képezi.
Az optimizmus hulláma következett. Talán – gondolták a kutatók – képesek leszünk olyan kvantumalgoritmusokat kitalálni, amelyek különféle problémák széles skáláját képesek megoldani.
De a fejlődés megtorpant. "Ez egy kicsit zűrzavaros pálya volt" - mondta Ryan O'Donnell a Carnegie Mellon Egyetemen. "Az emberek azt mondták: "Ez csodálatos, biztos vagyok benne, hogy mindenféle más csodálatos algoritmust fogunk kapni." Dehogy." A tudósok drámai gyorsulást fedeztek fel a szabványos halmazon belüli problémák egyetlen, szűk csoportjában NP-nek hívják, vagyis hatékonyan ellenőrizhető megoldásaik voltak – például a faktoring.
Így volt ez közel három évtizedig. Aztán áprilisban a kutatók feltalált egy alapvetően újfajta probléma, amelyet egy kvantumszámítógépnek exponenciálisan gyorsabban kell megoldania, mint egy klasszikusnak. Ez magában foglalja egy bonyolult matematikai folyamat bemeneteinek kiszámítását, kizárólag a zavaros kimenetek alapján. Hogy a probléma önmagában áll-e, vagy az első a sok más új határán, még nem határozták meg.
„Van egyfajta izgalom” – mondta Vinod Vaikuntanathan, a Massachusetts Institute of Technology informatikusa. "Sokan gondolkodnak azon, hogy mi van még odakint."
Az informatikusok az őket reprezentáló matematikai modellek tanulmányozásával próbálják megérteni, hogy mit tesznek jobban a kvantumszámítógépek. Gyakran elképzelnek egy kvantum- vagy klasszikus számítógép modelljét egy idealizált számológéppel, amelyet orákulumnak neveznek. Az orákuszok olyanok, mint az egyszerű matematikai függvények vagy számítógépes programok, amelyek bemenetet vesznek, és előre meghatározott kimenetet köpnek ki. Lehet, hogy véletlenszerű viselkedésűek, és „igen”-t adnak ki, ha a bemenet egy bizonyos véletlenszerű tartományba esik (mondjuk 12-től 67-ig), és „nem”-t, ha nem. Vagy lehetnek periodikusak, így az 1 és 10 közötti bevitel „igen”-t ad vissza, 11-től 20-ig „nem”, 21-től 30-ig ismét „igen”-t ad, és így tovább.
Tegyük fel, hogy van egy ilyen periodikus orákulum, és nem ismeri az időszakot. Csak annyit tehet, hogy beadja a számokat, és megnézheti, mit ad ki. Ezekkel a megszorításokkal milyen gyorsan találhatja meg egy számítógép a periódust? 1993-ban Daniel Simon, akkor a Montreali Egyetemen azt találta, hogy egy kvantumalgoritmus exponenciálisan gyorsabban tudja kiszámítani a választ egy szorosan összefüggő problémára, mint bármely klasszikus algoritmus.
Az eredmény lehetővé tette Simon számára, hogy meghatározza az egyik első utalást arra vonatkozóan, hogy hol várható drámai fölény a kvantumszámítógépeknél. Ám amikor benyújtotta dolgozatát egy vezető konferenciára, azt elutasították. A lap azonban érdekelte a konferencia programbizottságának egy fiatalabb tagját - Shor Péter, aki akkoriban a New Jersey-i Bell Laboratories-ban volt. Shor arra a következtetésre jutott, hogy Simon algoritmusát adaptálni tudja egy orákulum periódusának kiszámítására, ha van ilyen. Aztán rájött, hogy újra adaptálhatja az algoritmust, hogy megoldjon egy egyenletet, amely a periodikus orákulumhoz hasonlóan viselkedik: a faktoringot leíró egyenletet, amely periodikus.
Shor eredménye történelmi volt. Az általa felfedezett kvantum-algoritmus gyorsan képes gigantikus számokat alkotó prímtényezőikké redukálni, amire egyetlen ismert klasszikus algoritmus sem képes. A következő években a kutatók más hatékony kvantum-algoritmusokat fedeztek fel. Némelyikük, például Shor algoritmusa, még exponenciális előnyt is biztosított, de senki sem tudott drámai kvantumelőnyt bizonyítani egyetlen NP-probléma esetében sem, amely nem volt periodikus.
A haladás hiánya két informatikust vezetett Scott aaronson a Texasi Egyetemen, Austinban és Andris Ambainis a Lett Egyetemen, hogy tegyen egy megfigyelést. A kvantumelőny bizonyítása mindig azoktól az orákulumoktól függött, amelyeknek volt valamilyen nem véletlenszerű szerkezete, például periodicitása. 2009-ben ők sejtik hogy a véletlenszerű vagy strukturálatlan NP-problémák drámai felgyorsítása nem lehetséges. Senki sem talált kivételt.
Sejtésük korlátot szab a kvantumszámítógépek teljesítményének. De csak annyit írt, hogy nincs drámai felgyorsulás egy adott típusú strukturálatlan NP-probléma esetében – az igen vagy nem válaszadók esetében. Ha egy probléma konkrétabb, kvantitatív válaszok kitalálásával járt, amit keresési problémának neveznek, akkor a sejtés nem érvényesült.
Ezt szem előtt tartva a kutatók Takashi Yamakawa of NTT Social Informatics Laboratories and Mark Zhandry Az NTT Research és a Princeton Egyetem kutatója úgy döntött, hogy kísérletet tesz egy konkrét keresési problémával, amelyet 2005-ben vezetett be Oded Regev.
Képzeljen el egy sor szélkakast, amelyek mind ugyanabba az irányba mutatnak. Adjon mindegyiknek egy mért lökést, majd hagyja, hogy a széllökés befolyásolja az irányukat. Regev végső útmutatásaik alapján meg akarta határozni, hová mutattak kezdetben. Az ehhez hasonló problémákat „hibákkal való tanulásnak” nevezték, mivel a lökések és a szél véletlenszerű hibaforrásként működnek az eredeti irányban. Bizonyítékok vannak arra, hogy nehéz megoldani mind a klasszikus, mind a kvantum algoritmusok esetében.
Yamakawa és Zhandry módosította a beállításokat. Módosították a kezdő lökések erejét, kiszámíthatóbbá téve őket. Azt is előidézték, hogy a szelet egy véletlenszerű orákulum határozta meg, így bizonyos esetekben még véletlenszerűbb volt, míg más esetekben teljesen szunnyad.
Ezekkel a módosításokkal a kutatók felfedezték, hogy egy kvantum-algoritmus hatékonyan képes megtalálni a kezdeti irányt. Azt is bebizonyították, hogy minden klasszikus algoritmusnak exponenciális tényezővel lassabbnak kell lennie. Shorhoz hasonlóan ezután adaptálták az algoritmusukat a probléma valós változatának megoldására, amely az orákulumot egy tényleges matematikai egyenlettel helyettesíti.
Az informatikusok még mindig dolgoznak a probléma megértésén és továbbfejlesztésén. Vaikuntanathan összehasonlítja egy másikkal, amely adattömörítés során merül fel: Amikor az információ összenyomódik, véletlenül két bit szorulhat ugyanarra a helyre, felülírva azokat. Az ütközések előre megjósolásának problémája, hogy elkerülhesse őket, némi hasonlóságot mutat. „Ez a problémák egy osztálya, amely alapvetően így néz ki” – mondta. "Talán ezek a problémák mennyiségileg megoldhatók."
Reménykedtek benne, hogy egy olyan strukturálatlan probléma, mint az új, még a kvantumszámítógépek ma induló verzióiban is megoldható lehet, és így lehetőség nyílik a tesztelésre. Az volt a gondolat, hogy a strukturálatlan problémák programozása kevesebb erőforrást igényelhet, vagy kevésbé érzékenyek a zajra, mivel ezek már véletlenszerűek. Eddig azonban az új probléma még mindig túl fejlettnek tűnik ahhoz, hogy a meglévő kvantumszámítógépek megoldják. „Furcsa probléma. Nem gondoltam volna, hogy meghatározzam” – mondta Aaronson. "De utólag visszagondolva van néhány nagyon szép tulajdonsága."
Az eredmény az első példa drámai kvantumelőnyre egy strukturálatlan NP-probléma esetében. Lehetséges-e még sok más probléma, hogy a kvantumvilág gyakorlatilag megoldhatatlanból megoldhatóvá változik? Most több okunk van így gondolni.
„Néhányszor megdöntötte a hitünket arról, hogy a kvantumszámítógépek milyen problémákra lehetnek jók” – mondta O'Donnell.
