Fysik kan bringe hurtigere løsninger på hårde beregningsproblemer

Et velkendt beregningsproblem søger at finde den mest effektive rute for en rejsende sælger til at besøge kunder i en række byer. Tilsyneladende enkelt, det er faktisk overraskende komplekst og meget undersøgt, med implikationer på lige så omfattende områder som fremstilling og lufttrafikkontrol.

Forskere fra University of Central Florida og Boston University har udviklet en ny tilgang til hurtigere at løse sådanne vanskelige beregningsproblemer. Som rapporteret 12. maj i Naturkommunikation , de har opdaget en måde at anvende statistisk mekanik på, en gren af ​​fysik, at skabe mere effektive algoritmer, der kan køre på traditionelle computere eller en ny type kvanteberegningsmaskine, sagde professor Eduardo Mucciolo, formand for Institut for Fysik i UCF's College of Sciences.

Statistisk mekanik blev udviklet til at studere faste stoffer, gasser og væsker ved makroskopiske skalaer, men bruges nu til at beskrive en række komplekse materielle tilstande, fra magnetisme til superledning. Metoder afledt af statistisk mekanik er også blevet anvendt til at forstå trafikmønstre, adfærd i netværk af neuroner, sandskred og udsving i aktiemarkedet.

Der er allerede vellykkede algoritmer baseret på statistisk mekanik, der bruges til at løse beregningsproblemer. Sådanne algoritmer kortlægger problemer på en model af binære variabler på noderne i en graf, og løsningen er kodet på konfigurationen af ​​modellen med den laveste energi. Ved at bygge modellen op i hardware eller en computersimulering, forskere kan afkøle systemet, indtil det når sin laveste energi, afsløre løsningen.

"Problemet med denne tilgang er, at man ofte har brug for at komme igennem faseovergange, der ligner dem, man finder, når man går fra en væske til en glasfase, hvor der findes mange konkurrerende konfigurationer med lav energi, "Sagde Mucciolo." Sådanne faseovergange bremser køleprocessen til en krybning, gør metoden ubrugelig. "

Mucciolo og andre fysikere Claudio Chamon og Andrei Ruckenstein fra BU overvandt denne forhindring ved at kortlægge det oprindelige beregningsproblem på en elegant statistisk model uden faseovergange, som de kaldte toppunktsmodellen. Modellen er defineret på et todimensionalt gitter, og hvert toppunkt svarer til en reversibel logisk port forbundet til fire naboer. Input- og outputdata sidder ved gitterets grænser. Anvendelsen af ​​reversible logiske porte og gitterets regelmæssighed var afgørende ingredienser for at undgå faseovergangshagen, Sagde Mucciolo.

"Vores metode kører grundlæggende tingene omvendt, så vi kan løse disse meget hårde problemer, "Sagde Mucciolo." Vi tildeler hver af disse logiske porte en energi. Vi konfigurerede det på en sådan måde, at hver gang disse logiske porte opfyldes, energien er meget lav - derfor når alt er tilfreds, systemets samlede energi skal være meget lav. "

Chamon, en professor i fysik på BU og teamlederen, sagde forskningen repræsenterer en ny måde at tænke på problemet.

"Denne model udviser ingen termodynamisk faseovergang i bulk, så en af ​​forhindringerne for at nå frem til løsninger i tidligere modeller blev elimineret, " han sagde.

Spidsmodellen kan hjælpe med at løse komplekse problemer inden for maskinlæring, kredsløbsoptimering, og andre store beregningsmæssige udfordringer. Forskerne undersøger også, om modellen kan anvendes på factoring af semi-primtyper, tal, der er produktet af to primtal. Vanskeligheden ved at udføre denne operation med meget store halvprimer ligger til grund for moderne kryptografi og har budt på en central begrundelse for oprettelsen af ​​store kvantecomputere.

I øvrigt, modellen kan generaliseres for at tilføje en anden vej mod løsningen af ​​komplekse klassiske beregningsproblemer ved at drage fordel af kvantemekanisk parallelisme - det faktum, at, ifølge kvantemekanik, et system kan være i mange klassiske tilstande på samme tid.

"Vores papir præsenterer også en naturlig ramme for programmering af beregningsudstyr til specielle formål, såsom D-Wave Systems-maskiner, der bruger kvantemekanik til at fremskynde tiden til løsning af klassiske beregningsproblemer, "sagde Ruckenstein.

Zhi-Cheng Yang, en kandidatstuderende i fysik på BU, er også medforfatter på papiret. Universiteterne har ansøgt om patent på aspekter af toppunktsmodellen.