Een bekend rekenprobleem is het vinden van de meest efficiënte route voor een handelsreiziger om klanten in een aantal steden te bezoeken. Schijnbaar eenvoudig, het is eigenlijk verrassend complex en veel bestudeerd, met implicaties op uiteenlopende terreinen als fabricage en luchtverkeersleiding.

Onderzoekers van de University of Central Florida en Boston University hebben een nieuwe aanpak ontwikkeld om zulke moeilijke rekenproblemen sneller op te lossen. Zoals gemeld 12 mei in Natuurcommunicatie , ze hebben een manier ontdekt om statistische mechanica toe te passen, een tak van de natuurkunde, om efficiëntere algoritmen te creëren die kunnen worden uitgevoerd op traditionele computers of een nieuw type kwantumcomputer, zei professor Eduardo Mucciolo, voorzitter van het departement Natuurkunde in UCF's College of Sciences.

Statistische mechanica is ontwikkeld om vaste stoffen te bestuderen, gassen en vloeistoffen op macroscopische schaal, maar wordt nu gebruikt om een ​​verscheidenheid aan complexe toestanden van materie te beschrijven, van magnetisme naar supergeleiding. Methoden die zijn afgeleid van statistische mechanica zijn ook toegepast om verkeerspatronen te begrijpen, het gedrag van netwerken van neuronen, zandlawines en beursschommelingen.

Er zijn al succesvolle algoritmen op basis van statistische mechanica die worden gebruikt om rekenproblemen op te lossen. Dergelijke algoritmen brengen problemen in kaart op een model van binaire variabelen op de knooppunten van een grafiek, en de oplossing is gecodeerd op de configuratie van het model met de laagste energie. Door het model in hardware of een computersimulatie in te bouwen, onderzoekers kunnen het systeem afkoelen tot het zijn laagste energie bereikt, het onthullen van de oplossing.

"Het probleem met deze benadering is dat men vaak door faseovergangen moet komen die vergelijkbaar zijn met die bij het overgaan van een vloeibare naar een glazen fase, waar veel concurrerende configuraties met lage energie bestaan, "Mucciolo zei. "Dergelijke faseovergangen vertragen het afkoelingsproces tot een kruip, waardoor de methode onbruikbaar wordt."

Mucciolo en collega-fysici Claudio Chamon en Andrei Ruckenstein van BU hebben deze hindernis overwonnen door het oorspronkelijke rekenprobleem in kaart te brengen op een elegant statistisch model zonder faseovergangen, die ze het vertex-model noemden. Het model is gedefinieerd op een tweedimensionaal rooster en elk hoekpunt komt overeen met een omkeerbare logische poort die is verbonden met vier buren. Invoer- en uitvoergegevens bevinden zich op de grenzen van het rooster. Het gebruik van omkeerbare logische poorten en de regelmaat van het rooster waren cruciale ingrediënten om de faseovergang te vermijden, zei Mucciolo.

"Onze methode draait de zaken in feite omgekeerd, zodat we deze zeer moeilijke problemen kunnen oplossen, "Zei Mucciolo. "We kennen aan elk van deze logische poorten een energie toe. We hebben het zo geconfigureerd dat elke keer dat aan deze logische poorten wordt voldaan, de energie is erg laag - daarom als alles tevreden is, de totale energie van het systeem moet erg laag zijn."

Chamon, een hoogleraar natuurkunde aan de BU en de teamleider, zei dat het onderzoek een nieuwe manier van denken over het probleem vertegenwoordigt.

"Dit model vertoont geen bulk thermodynamische faseovergang, dus een van de obstakels voor het bereiken van oplossingen die aanwezig waren in eerdere modellen werd geëlimineerd, " hij zei.

Het vertex-model kan helpen bij het oplossen van complexe problemen in machine learning, circuit optimalisatie, en andere grote rekenkundige uitdagingen. De onderzoekers onderzoeken ook of het model kan worden toegepast op de factoring van semi-priemgetallen, getallen die het product zijn van twee priemgetallen. De moeilijkheid om deze operatie uit te voeren met zeer grote semi-priemgetallen ligt ten grondslag aan moderne cryptografie en heeft een belangrijke reden geboden voor het creëren van grootschalige kwantumcomputers.

Bovendien, het model kan worden gegeneraliseerd om een ​​ander pad toe te voegen naar de oplossing van complexe klassieke rekenproblemen door gebruik te maken van kwantummechanisch parallellisme - het feit dat, volgens de kwantummechanica, een systeem kan zich tegelijkertijd in veel klassieke toestanden bevinden.

"Ons artikel biedt ook een natuurlijk raamwerk voor het programmeren van rekenapparatuur voor speciale doeleinden, zoals D-Wave Systems-machines, die kwantummechanica gebruiken om de tijd tot oplossing van klassieke rekenproblemen te versnellen, ’ zei Ruckenstein.

Zhi-Cheng Yang, een afgestudeerde student natuurkunde aan de BU, is ook co-auteur van het papier. De universiteiten hebben patent aangevraagd op aspecten van het vertex-model.