Novi kvantni algoritam ubrzava rješavanje ogromne klase problema

Izvorna verzija od ova priča pojavio se u Magazin Quanta.

Za računalne znanstvenike rješavanje problema pomalo je nalik na planinarenje. Prvo moraju odabrati problem koji će riješiti – akun za prepoznavanje vrha za uspon – i tada moraju razviti strategiju za rješavanje. Klasični i kvantni istraživači natječu se koristeći različite strategije, sa zdravim suparništvom između njih dvojice. Kvantni istraživači prijavljuju brz način da riješe problem – često skaliranjem vrhunca za koji se nitko nije mislio da se vrijedi penjati – tada se klasični timovi utrkuju kako bi vidjeli mogu li pronaći bolji način.

Ovo natjecanje gotovo uvijek završava kao virtualna veza: kada istraživači misle da su osmislili kvantni algoritam koji djeluje brže ili bolje od bilo čega drugog, klasični istraživači obično dolaze s onim koji ga je jednak. Samo prošli tjedan, navodna kvantna brzina, objavljena u časopisu Znanostsusreo se s trenutnim skepticizmom dvije odvojene skupine koje su pokazale kako nastupiti sličan proračun na klasičnim strojevima.

Ali u radu objavljenom na znanstvenom mjestu preprinta arxiv.org prošle godine, istraživači su opisali kako izgleda kvantna brzina koja je i uvjerljiva i korisna. Istraživači su opisali novi kvantni algoritam koji djeluje brže od svih poznatih klasičnih u pronalaženju dobrih rješenja za široku klasu problema s optimizacijom (koji traže najbolje moguće rješenje među ogromnim brojem izbora).

Do sada nijedan klasični algoritam nije deronirao novi algoritam, poznat kao dekodirana kvantna interferometrija (DQI). To je “proboj u kvantnim algoritmima”, rekao je Gil Kalaimatematičar na Sveučilištu Reichman i Istaknuti skeptik kvantnog računanja. Izvještaji o kvantnim algoritmima uzbuđuju istraživače, dijelom i zato što mogu rasvijetliti nove ideje o teškim problemima, a dijelom i zato što, za sve zujanje oko kvantnih strojeva, nije jasno koji će problemi od njih zapravo imati koristi. Kvantni algoritam koji nadmašuje sve poznate klasične na zadacima optimizacije predstavljali bi veliki korak naprijed u iskorištavanju potencijala kvantnih računala.

“Oduševljen sam zbog toga”, rekao je Ronald de WolfTeoretski računalni znanstvenik iz CWI -a, Nacionalnog istraživačkog instituta za matematiku i informatiku u Nizozemskoj, koji nije bio uključen u novi algoritam. Ali istodobno je upozorio da je još uvijek sasvim moguće da će istraživači na kraju pronaći klasični algoritam koji se isto tako dobro čini. A zbog nedostatka kvantnog hardvera, proći će još neko vrijeme prije nego što empirijski mogu testirati novi algoritam.

Algoritam bi mogao potaknuti novi rad na klasičnoj strani, prema Ewin Tangračunalni znanstvenik sa Sveučilišta u Kaliforniji, Berkeley, koji je kao tinejdžer došao u istaknuti kao tinejdžer Stvaranje klasičnih algoritama koji odgovaraju kvantnim. Nove tvrdnje “dovoljno su zanimljive da bih rekao ljudima klasičnih algoritama:” Hej, trebali biste pogledati ovaj rad i raditi na ovom problemu “, rekla je.

Najbolji put naprijed?

Kad se takmiče klasični i kvantni algoritmi, to često rade na bojnom polju optimizacije, polje se usredotočilo na pronalaženje najboljih mogućnosti za rješavanje trnovitih problema. Istraživači se obično fokusiraju na probleme u kojima broj mogućih rješenja eksplodira kako problem postaje veći. Koji je najbolji način da kamion za dostavu posjeti 10 gradova u tri dana? Kako biste trebali spakirati parcele u leđa? Klasične metode rješavanja ovih problema, koje često uključuju probijanje mogućih rješenja na pametne načine, brzo postaju neodržive.

Specifični problem optimizacije koji se DQI rješava otprilike je ovo: dobila vam je zbirku točaka na listu papira. Morate smisliti matematičku funkciju koja prolazi kroz ove točke. Konkretno, vaša funkcija mora biti polinom-kombinacija varijabli podignutih na eksponente cijelog broja i pomnožene s koeficijentima. Ali to ne može biti previše komplicirano, što znači da moći ne mogu previsoko. To vam daje zakrivljenu liniju koja se viri gore i dolje dok se kreće preko stranice. Vaš je posao pronaći liniju Wiggly koja dodiruje najviše bodova.

Varijacije ovog problema prikazuju se u različitim oblicima u računalnoj znanosti, posebno u kodiranju pogrešaka i kriptografiji – polja su usredotočena na sigurno i precizno kodiranje podataka dok se prenosi. Istraživači DQI -a prepoznali su, u osnovi, da je crtanje bolje crte srodno prebacivanju bučne kodirane poruke bliže njegovom točnom značenju.