Ett välkänt beräkningsproblem försöker hitta den mest effektiva vägen för en resande säljare att besöka kunder i ett antal städer. Till synes enkelt, det är faktiskt förvånansvärt komplext och mycket studerat, med implikationer inom så omfattande områden som tillverkning och flygledning.

Forskare från University of Central Florida och Boston University har utvecklat en ny metod för att lösa sådana svåra beräkningsproblem snabbare. Som rapporterats 12 maj in Naturkommunikation , de har upptäckt ett sätt att tillämpa statistisk mekanik, en gren av fysiken, att skapa mer effektiva algoritmer som kan köras på traditionella datorer eller en ny typ av kvantberäkningsmaskin, sa professor Eduardo Mucciolo, ordförande för institutionen för fysik vid UCF:s vetenskapskollegium.

Statistisk mekanik utvecklades för att studera fasta ämnen, gaser och vätskor i makroskopisk skala, men används nu för att beskriva en mängd komplexa materiatillstånd, från magnetism till supraledning. Metoder härledda från statistisk mekanik har också använts för att förstå trafikmönster, beteendet hos nätverk av neuroner, sandlaviner och börsfluktuationer.

Det finns redan framgångsrika algoritmer baserade på statistisk mekanik som används för att lösa beräkningsproblem. Sådana algoritmer kartlägger problem på en modell av binära variabler på noderna i en graf, och lösningen är kodad på konfigurationen av modellen med lägst energi. Genom att bygga in modellen i hårdvara eller en datorsimulering, forskare kan kyla systemet tills det når sin lägsta energi, avslöjar lösningen.

"Problemet med det här tillvägagångssättet är att man ofta behöver ta sig igenom fasövergångar som liknar de som finns när man går från en flytande till en glasfas, där många konkurrerande konfigurationer med låg energi finns, "Sådana fasövergångar saktar ner nedkylningsprocessen till en krypning, sa Mucciolo. gör metoden värdelös."

Mucciolo och andra fysiker Claudio Chamon och Andrei Ruckenstein från BU övervann detta hinder genom att kartlägga det ursprungliga beräkningsproblemet på en elegant statistisk modell utan fasövergångar, som de kallade vertexmodellen. Modellen är definierad på ett tvådimensionellt gitter och varje vertex motsvarar en reversibel logisk grind kopplad till fyra grannar. In- och utdata ligger vid gränserna för gittret. Användningen av reversibla logiska grindar och regelbundenhet i gittret var avgörande ingredienser för att undvika fasövergångsproblem, sa Mucciolo.

"Vår metod kör i princip saker omvänt så att vi kan lösa dessa mycket svåra problem, ", sa Mucciolo. "Vi tilldelar var och en av dessa logiska grindar en energi. Vi konfigurerade det på ett sådant sätt att varje gång dessa logiska grindar är uppfyllda, energin är mycket låg - därför, när allt är uppfyllt, den totala energin i systemet bör vara mycket låg."

Chamon, en professor i fysik vid BU och teamledaren, sa att forskningen representerar ett nytt sätt att tänka på problemet.

"Denna modell uppvisar ingen bulk termodynamisk fasövergång, så ett av hindren för att nå lösningar som fanns i tidigare modeller eliminerades, " han sa.

Vertexmodellen kan hjälpa till att lösa komplexa problem inom maskininlärning, kretsoptimering, och andra stora beräkningsutmaningar. Forskarna undersöker också om modellen kan tillämpas på factoring av semi-primtal, tal som är produkten av två primtal. Svårigheten att utföra denna operation med mycket stora semi-primtal ligger till grund för modern kryptografi och har erbjudit ett nyckelmotiv för skapandet av storskaliga kvantdatorer.

Dessutom, modellen kan generaliseras för att lägga till ytterligare en väg mot lösningen av komplexa klassiska beräkningsproblem genom att dra fördel av kvantmekanisk parallellism - det faktum att, enligt kvantmekaniken, ett system kan vara i många klassiska tillstånd samtidigt.

"Vår uppsats presenterar också ett naturligt ramverk för programmering av speciella beräkningsenheter, såsom D-Wave Systems maskiner, som använder kvantmekanik för att påskynda tiden till lösning av klassiska beräkningsproblem, sa Ruckenstein.

Zhi-Cheng Yang, en doktorand i fysik vid BU, är också medförfattare på tidningen. Universiteten har ansökt om patent på aspekter av vertexmodellen.