Problem trgovačkog putnika se smatra odličnim primerom kombinatornog problema optimizacije. Sada je berlinski tim na čelu sa teorijskim fizičarom prof. dr Jensom Ajzertom sa Freie Universitat Berlin i HZB pokazao da se određena klasa takvih problema zapravo može bolje i mnogo brže rešiti kvantnim računarima nego konvencionalnim metodama.
Rad tima je objavljen u časopisu Science Advances.
Kvantni računari koriste takozvane kubite, koji nisu ni nula ni jedan kao u konvencionalnim logičkim kolima, ali mogu poprimiti bilo koju vrednost između. Ovi kubiti se realizuju pomoću visoko ohlađenih atoma, jona ili supravodljivih kola, i još uvek je fizički veoma složeno izgraditi kvantni računar sa mnogo kubita. Međutim, matematičke metode se već mogu koristiti za istraživanje šta bi kvantni računari otporni na greške mogli postići u budućnosti.
„Postoji mnogo mitova o tome, a ponekad i određena količina vrućeg vazduha i uzbuđenja. Ali mi smo tom pitanju pristupili rigorozno, koristeći matematičke metode, i dali solidne rezultate na tu temu. Iznad svega, razjasnili smo u kom smislu mogu postojati bilo kakve prednosti“, kaže prof. dr Ajzert, koji vodi zajedničku istraživačku grupu na Freie Universitat Berlin i Helmholtz-Zentrum Berlin.
Dobro poznati problem trgovačkog putnika služi kao odličan primer: putnik mora da poseti više gradova, a zatim se vrati u svoj rodni grad. Koji je najkraći put? Iako je ovaj problem lako razumeti, on postaje sve složeniji kako se broj gradova povećava, a vreme računanja eksplodira. Problem trgovačkog putnika predstavlja grupu problema optimizacije koji su od ogromnog ekonomskog značaja, bilo da se radi o železničkoj mreži, logistici ili optimizaciji resursa. Dovoljno dobra rešenja mogu se naći korišćenjem metoda aproksimacije.
Tim predvođen Ajzertom i njegovim kolegom Jean-Pierre Seifertom sada je koristio čisto analitičke metode da proceni kako bi kvantni računar sa kubitima mogao da reši ovu klasu problema, klasični misaoni eksperiment sa olovkom i papirom i mnogo stručnosti.
„Jednostavno pretpostavljamo, bez obzira na fizičku realizaciju, da ima dovoljno kubita i sagledavamo mogućnosti izvođenja računarskih operacija sa njima“, objašnjava Vincent Ulitzsch, dr. student na Tehničkom univerzitetu u Berlinu.
Na taj način, tim je otkrio sličnosti sa dobro poznatim problemom u kriptografiji, odnosno šifrovanjem podataka.
„Shvatili smo da bismo mogli da koristimo Šor algoritam da rešimo podklasu ovih problema optimizacije“, kaže Ulič. To znači da vreme računanja više ne „eksplodira“ sa brojem gradova (eksponencijalno, 2N), već samo raste polinomski, odnosno sa Nx, gde je x konstanta. Ovako dobijeno rešenje je i kvalitativno mnogo bolje od približnog rešenja korišćenjem konvencionalnog algoritma.
„Pokazali smo da za specifičnu, ali veoma važnu i praktično relevantnu klasu problema kombinatorne optimizacije, kvantni računari imaju fundamentalnu prednost u odnosu na klasične računare za određene slučajeve problema“, kaže Ajzert.
