Novi Kvantni Alat za Optimizaciju

Novi teorijski rad iz Google Quantum AI pokazuje da veliki kvantni računari mogu riješiti određene probleme optimizacije koji su za konvencionalne klasične računare neizvodljivi. Od dizajniranja efikasnijih zračnih ruta do organiziranja kliničkih ispitivanja, problemi optimizacije su svugdje. Ipak, čak i naše najmoćnije superračunari teže pronaći najbolje rješenje za mnoge praksne izazove. To je dovelo do glavnog, decenija dugotrajnog pitanja u kvantnoj računarstvu: mogu li kvantni uređaji uspjeti na problemima optimizacije gdje klasični ne uspiju? To je dokazano da je vrlo teško matematičko pitanje, koje je uglavnom otvoreno.

Kao što se sposobnosti kvantnog hardvera brzo napreduju, takvi teorijski problemi o iscrpnom komercijalnom i znanstvenom korištenju velikih kvantnih računara postaju samo hitniji. U nedavnom članku u Natureu, istraživači iz Google Quantum AI i suradnici sa Stanforda, MIT-a i Caltecha prosvjetljavaju ovo pitanje. Predstavljamo efikasan kvantni algoritam – Decoded Quantum Interferometry (DQI) – koji koristi valovit prirodu kvantne mehanike da stvori interferencijske uzorke koji konvergiraju na blisko optimalna rješenja koja su neizvodljiva za klasične računare.

Kvantna veza između optimizacije i dekodiranja

Ima jedan “uvjet”: da bi se stvorili potrebni interferencijski uzorci, morate riješiti još jedan teški računarski problem zvan dekodiranje. U problemu dekodiranja dajete se mreža i točka u prostoru, a potrebno je pronaći najbliži element mreže točki. Na primjer, kutovi kvadrata na šahovskoj ploči formiraju dvodimenzionalnu mrežu. Nakon što baciš zrno pijeska na nasumičnu lokaciju na šahovskoj ploči, problem dekodiranja bi bio pronaći najbliži kut. Dok je ovaj problem lagan za kvadratnu mrežu u dvije dimenzije, može postati vrlo teško na nekim mrežama u stotinama ili tisućama dimenzija. Srećom, problemi dekodiranja su izuzetno dobro proučavani u zadnjih nekoliko decenija, uglavnom zbog primjena u ispravljanju grešaka nastalih tijekom pohrane ili prenosa podataka. Razvijeni su mnogi napredni i moćni algoritmi za rješavanje problema dekodiranja za različito strukturirane mreže. Otkrili smo da za određene vrste problema optimizacije, povezani problemi dekodiranja imaju pravu vrstu strukture da ih riješe neki od ovih moćnih dekodirajućih algoritama. Međutim, to je samo kroz moć kvantne računarstva da se ovi dekodirajući algoritmi iskoriste i za rješavanje problema optimizacije. Upareći kvantnu interferenciju DQI s ovim naprednim dekodirajućim algoritmima, dovoljno veliki kvantni računar mogao bi pronaći aproksimativna rješenja za ove probleme optimizacije – rješenja koja čine da izgledaju izvan dosega bilo kojeg poznatog klasičnog metoda.

Jasna kvantna pobjeda: Optimalno polinomijalno presjekanje

Najbolji rezultat našeg rada je za problem koji zovemo optimalno polinomijalno presjekanje (OPI). U problemu OPI dajete se popis ciljnih točaka i želite presjeći što više od njih podešavanjem koeficijenata polinoma čiji je stepen manji od broja točaka. To je uobičajena zadatak u data scienceu poznat kao polinomijalna regresija. Varijante ovog problema pojavile su se u kontekstu digitalnog ispravljanja grešaka, kao i kriptografije. Stoga su razvijeni napredni algoritmi za rješavanje ga u određenim posebnim slučajevima, ali za druge slučajeve, problem ostaje neizvodljiv za rješavanje poznatim algoritmima na klasičnim računarima. Koristeći DQI, kvantni računar mogao bi ovo pretvoriti u problem dekodiranja Reed-Solomon kodova (široko korištena porodica kodova pronađena u DVD-ovima i QR kodovima). Razvijeni su vrlo dobri dekodirajući algoritmi za dekodiranje Reed-Solomon kodova, pa zato kvantni računari koristeći DQI mogu pronaći bolja aproksimativna optima za problem OPI od onih koje mogu pronaći poznati algoritmi na klasičnim računarima. Na primjer, naša analiza pokazuje da određeni primjeri problema OPI mogu se riješiti kvantnim računarima koristeći samo na redu od nekoliko milijuna elementarnih kvantnih logičkih operacija, što bi zahtijevalo preko 10^23 (sto sextiliona) elementarnih operacija za rješavanje na klasičnom računalu.

Zaključak

Ova matematička otkrića kvantnog algoritma koji nudi ubrzanje za optimizaciju poboljšava naše razumijevanje potencijalnih upotreba kvantnih računara. Kada hardver kvantne računarstva bude dovoljno napredan, istraživači će moći koristiti algoritam DQI za rješavanje klasično izazovnih problema optimizacije. Ovo otvaranje novih mogućnosti za rješavanje problema optimizacije može imati duboke i široke posljedice u mnogim područjima, od operacija do znanosti i inženjerstva.

Česta pitanja

Što je Decoded Quantum Interferometry (DQI)?

Decoded Quantum Interferometry (DQI) je efikasan kvantni algoritam koji koristi valovit prirodu kvantne mehanike da stvori interferencijske uzorke koji konvergiraju na blisko optimalna rješenja problema optimizacije.

Koji problemi optimizacije mogu biti riješeni pomoću DQI?

DQI može biti koristan za rješavanje problema optimizacije kao što je optimalno polinomijalno presjekanje (OPI), gdje se traži da se presječe što više ciljnih točaka podešavanjem koeficijenata polinoma.

Koliko operacija je potrebno za rješavanje problema OPI na kvantnom računalu?

Naša analiza pokazuje da određeni primjeri problema OPI mogu se riješiti kvantnim računarima koristeći samo na redu od nekoliko milijuna elementarnih kvantnih logičkih operacija, što bi zahtijevalo preko 10^23 elementarnih operacija za rješavanje na klasičnom računalu.

Kada se očekuje da će kvantni računari biti dovoljno napredni za korištenje DQI?

To ovisi o napretku kvantnog hardvera, ali očekuje se da će to biti u narednih nekoliko godina kada hardver postane dovoljno napredan za iskorištavanje moći kvantnih algoritama.

Koliko je važno otkriće DQI za polje kvantne računarstva?

Otkriće DQI je važno jer pokazuje da kvantni računari mogu riješiti određene probleme optimizacije koje su neizvodljive za klasične računare, otvarajući nove mogućnosti za rješavanje problema u mnogim područjima.