Toshiba Corporation har realiserat ett stort genombrott inom kombinatorisk optimering – valet av de bästa lösningarna bland ett enormt antal kombinatoriska mönster – med utvecklingen av en algoritm som levererar världens snabbaste och största prestanda, och en cirka 10-faldig förbättring jämfört med nuvarande metoder. Toshibas nya metod kan tillämpas på sådana skrämmande men viktiga uppgifter som att identifiera effektiva leveransvägar, bestämma de mest effektiva molekylära strukturerna att undersöka vid utveckling av nya läkemedel, och bygga portföljer av lönsamma finansiella produkter.

Den nyutvecklade tekniken, den simulerade bifurkationsalgoritmen, erhåller snabbt mycket exakta ungefärliga lösningar (bra lösningar) för komplexa storskaliga kombinatoriska optimeringsproblem - problem som har motstått lösning under lång tid, och som är mycket svåra att lösa med konventionella tekniker. Potentiellt ännu viktigare, Algoritmen realiserar också utmärkt skalbarhet till en låg kostnad med nuvarande datorer, som skulle kunna revolutionera nuvarande optimeringsprocesser.

Toshiba kommer att använda Simulated Bifurcation Algorithm för att bygga en tjänsteplattform som snabbt kan lösa olika sociala och affärsmässiga problem, siktar på kommersialisering 2019.

Detaljer om den nya tekniken publiceras i den akademiska onlinetidskriften Vetenskapens framsteg .

Många problem kan bara lösas genom att sålla igenom ett stort antal alternativ för att hitta de bästa kombinationerna. Dessa inkluderar att förverkliga effektiv logistik (det resande säljarproblemet i matematik), styra trafiken för att minska trängseln, tillämpa molekylär design på läkemedelsutveckling, och optimera finansiella portföljer. I dag, att förverkliga sådan kombinatorisk optimering kräver en enorm mängd beräkningar, och att använda nuvarande datorer för att hitta lösningar är fortfarande svårt.

Det finns växande förväntningar på att nästa generations datorenheter, som kvantdatorer, kommer att leda vägen till bättre lösningar, och aktuell forskning syftar till att utveckla datorer speciellt utformade för kombinatorisk optimering genom användning av supraledande kretsar, lasrar, och halvledarbaserade digitala datorer. Trots dessa ansträngningar, det är fortfarande en utmaning att öka storleken på lösbara problem och att minska beräkningstiden.

Till exempel, det är fortfarande svårt för kvantdatorer med supraledande kretsar att lösa komplexa storskaliga problem. Och medan dagens halvledarbaserade digitala datorer har gjort det lättare att öka storleken på lösbara problem, nuvarande algoritmer för kombinatorisk optimering är svåra att parallellisera, vilket gör det svårt att använda parallell beräkning för att påskynda problemlösning.

Toshiba har löst dessa problem genom att utveckla en ny kombinatorisk optimeringsalgoritm, den simulerade bifurkationsalgoritmen. Det är mycket parallelliserbart, och kan därför enkelt påskynda problemlösning på standard digital dator genom parallell beräkning. Eftersom nuvarande storskaliga beräkningssystem kan användas som de är, det finns inget behov av att installera ny utrustning, gör det enkelt att skala upp till en låg kostnad.

Till exempel, genom att använda fältprogrammerbara gate arrays (FPGAs), en bra lösning på ett optimeringsproblem med 2, 000 helt anslutna variabler (cirka 2 miljoner anslutningar) kan erhållas på bara 0,5 millisekunder. Detta är ungefär 10 gånger snabbare än den laserbaserade kvantdatorn som anses vara världens snabbaste kan lösa samma problem. Dessutom, använder ett kluster med åtta GPU:er, Toshiba fick en bra lösning för ett storskaligt problem som involverade 100, 000 helt anslutna variabler (cirka 5 miljarder anslutningar) på bara några sekunder. Dessa resultat öppnar upp för nya sätt att lösa storskaliga kombinatoriska optimeringsproblem inom många olika tillämpningsområden.

Den simulerade bifurkationsalgoritmen utnyttjar bifurkationsfenomen, adiabatiska processer, och ergotiska processer inom klassisk mekanik för att snabbt hitta mycket exakta lösningar. Toshiba härledde principen från en teori om en kvantdator som föreslagits av företaget självt. Denna upptäckt inom klassisk mekanik inspirerad av kvantmekanik är en akademiskt intressant, mycket nytt resultat som tyder på att det finns okända matematiska satser.

Går framåt i år, Toshiba siktar nu på att använda detta nyckelteknologiska genombrott för att realisera och kommersialisera en tjänsteplattform som uppfyller alla optimeringsbehov inom logistik, finansiera, och andra områden i det moderna samhället.