Dagens bästa digitala datorer kämpar fortfarande med att lösa, inom en praktisk tidsram, en viss klass av problem:kombinatoriska optimeringsproblem, eller de som innebär att kamma igenom stora uppsättningar möjligheter för att hitta den bästa lösningen. Kvantdatorer har potential att ta sig an dessa problem, men att skala upp antalet kvantbitar i dessa system är fortfarande ett hinder.

Nu, MIT Lincoln Laboratory forskare har visat ett alternativ, analogbaserat sätt att påskynda beräkningen av dessa problem. "Vår dator fungerar genom att" beräkna med fysik "och använder naturen själv för att lösa dessa tuffa optimeringsproblem, "säger Jeffrey Chou, medförfattare till ett papper om detta arbete publicerat i Nature's Vetenskapliga rapporter . "Den är gjord av vanliga elektroniska komponenter, tillåta oss att skala vår dator snabbt och billigt genom att utnyttja den befintliga mikrochipindustrin. "

Det kanske mest kända kombinatoriska optimeringsproblemet är den resande säljarens. Problemet ber att hitta den kortaste vägen en säljare kan ta genom ett antal städer, börjar och slutar på samma. Det kan tyckas enkelt med bara några få städer, men problemet blir exponentiellt svårt att lösa när antalet städer växer, trasslar ner även de bästa superdatorer. Ändå måste optimeringsproblem lösas i den verkliga världen dagligen; lösningarna används för att schemalägga skift, minimera ekonomisk risk, upptäcka droger, planera leveranser, minska störningar på trådlösa nätverk, och mycket mer.

"Det har varit känt under mycket lång tid att digitala datorer är i grunden dåliga på att lösa den här typen av problem, "säger Suraj Bramhavar, också en medledande författare. "Många av de algoritmer som har utvecklats för att hitta lösningar måste byta ut lösningskvaliteten för tid. Att hitta den absoluta optimala lösningen hamnar på orimligt lång tid när problemstorleken växer." Att hitta bättre lösningar och göra det på dramatiskt kortare tid kan spara industrier miljarder dollar. Således, forskare har letat efter nya sätt att bygga system utformade specifikt för optimering.

Att hitta takten

Naturen gillar att optimera energi, eller uppnå mål på det mest effektiva och distribuerade sättet. Denna princip kan ses i naturens synkronisering, som hjärtceller som slår ihop eller fiskskolor som rör sig som en. Liknande, om du ställer in två pendelklockor på samma yta, oavsett när den enskilda pendeln sätts i rörelse, de kommer så småningom att vaggas in i en synkroniserad rytm, når sin spets samtidigt men rör sig i motsatta riktningar (eller ur fas). Detta fenomen observerades första gången 1665 av den nederländska forskaren Christiaan Huygens. Dessa klockor är ett exempel på kopplade oscillatorer, utformas på ett sådant sätt att energi kan överföras mellan dem.

"Vi har i huvudsak byggt en elektronisk, programmerbar version av denna [klockinställning] med hjälp av kopplade olinjära oscillatorer, "Chou säger, visar en YouTube -video av metronomer som visar ett liknande fenomen. "Tanken är att om du installerar ett system som kodar ditt problem energilandskap, då kommer systemet naturligtvis att försöka minimera energin genom att synkronisera, och därmed, kommer att nöja sig med den bästa lösningen. Vi kan sedan läsa upp den här lösningen. "

Laboratoriets prototyp är en typ av Ising -maskin, en dator baserad på en modell i fysik som beskriver ett nätverk av magneter, var och en har en magnetisk "snurr" -orientering som bara kan peka uppåt eller nedåt. Varje snurr slutliga orientering beror på dess interaktion med varannan snurr. De enskilda spin-to-spin-interaktionerna definieras med en specifik kopplingsvikt, vilket betecknar styrkan i deras anslutning. Målet med en Ising -maskin är att hitta, givet ett specifikt nätverk för kopplingsstyrka, rätt konfiguration för varje snurr, upp eller ner, som minimerar den totala systemenergin.

Men hur löser en Ising -maskin ett optimeringsproblem? Det visar sig att optimeringsproblem kan kartläggas direkt på Ising -modellen, så att en uppsättning av ett snurr med vissa kopplingsvikter kan representera varje stad och avstånden mellan dem i problemet med resande säljare. Således, Att hitta den lägsta energikonfigurationen av snurr i Ising-modellen översätts direkt till lösningen för säljarens snabbaste rutt. Dock, att lösa detta problem genom att individuellt kontrollera var och en av de möjliga konfigurationerna blir oöverkomligt svårt när problemen växer till även blygsamma storlekar.

Under de senaste åren har det har gjorts ansträngningar för att bygga kvantmaskiner som kartlägger Ising -modellen, den mest anmärkningsvärda är en från det kanadensiska företaget D-Wave Systems. Dessa maskiner kan erbjuda ett effektivt sätt att söka i det stora lösningsutrymmet och hitta rätt svar, även om de fungerar vid kryogena temperaturer.

Laboratoriets system kör en liknande sökning, men gör det med enkla elektroniska oscillatorer. Varje oscillator representerar ett snurr i Ising -modellen, och tar på samma sätt en binär fas, där oscillatorer som är synkroniserade, eller i fas, representerar "spin up" -konfigurationen och de som är ur fas representerar "spin down" -konfigurationen. För att ställa in systemet för att lösa ett optimeringsproblem, problemet först mappas till Ising -modellen, översätta den till programmerbara kopplingsvikter som ansluter varje oscillator.

Med kopplingsvikterna programmerade, oscillatorerna får gå, som pendelarmen för varje klocka som släpps. Systemet slappnar sedan av naturligt till sitt övergripande lägsta energitillstånd. Elektronisk avläsning av varje oscillators slutfas, representerar "snurra upp" eller "snurra ner", "presenterar svaret på den ställda frågan. När systemet körde mot mer än 2, 000 problem med slumpmässig optimering, det kom till rätt lösning 98 procent av tiden.

Tidigare, forskare vid Stanford University demonstrerade en Ising -maskin som använder lasrar och elektronik för att lösa optimeringsproblem. Det arbetet avslöjade potentialen för en betydande snabbare hastighet än digital dator, även om, enligt Chou, systemet kan vara svårt och kostsamt att skala till större storlekar. Målet att hitta ett enklare alternativ tända laboratoriets forskning.

Uppskalning

Den individuella oscillatorkretsen som teamet använde i sin demonstration liknar kretsar som finns i mobiltelefoner eller Wi-Fi-routrar. Ett tillägg de har gjort är en tvärstångsarkitektur som gör att alla oscillatorer i kretsen kan kopplas direkt till varandra. "Vi har hittat en arkitektur som är både skalbar att tillverka och som möjliggör full anslutning till tusentals oscillatorer, "Säger Chou. Ett fullt anslutet system gör att det enkelt kan kartläggas till en mängd olika optimeringsproblem.

"Detta arbete från Lincoln Laboratory utnyttjar innovativt en tvärstångsarkitektur i sin konstruktion av en analog-elektronisk Ising-maskin, "säger Peter McMahon, en biträdande professor i tillämpad och teknisk fysik vid Cornell University som inte var inblandad i denna forskning. "Det kommer att bli intressant att se hur framtida utveckling av denna arkitektur och plattform fungerar."

Laboratoriets prototyp Ising -maskin använder fyra oscillatorer. Teamet arbetar nu med en plan för att skala prototypen till ett större antal oscillatorer, eller "noder, "och tillverka det på ett kretskort." Om vi ​​kan komma till, säga, 500 noder, det finns en chans att vi kan börja konkurrera med befintliga datorer, och vid 1, 000 noder vi kanske kan slå dem, "Säger Bramhavar.

Teamet ser en tydlig väg framåt för att skala upp eftersom tekniken är baserad på elektroniska standardkomponenter. Det är också extremt billigt. Alla delar till deras prototyp finns i ett typiskt grundutbildat elektrotekniklaboratorium och köptes online för cirka $ 20.

"Det som väcker mig är enkelheten, "Bramhavar tillägger." Kvantdatorer förväntas visa fantastisk prestanda, men de vetenskapliga och tekniska utmaningar som krävs för att skala upp dem är ganska hårda. Demonstrera även en liten del av de prestandavinster som tänkts med kvantdatorer, men gör det med hjälp av hårdvara från den befintliga elektronikindustrin, skulle vara ett stort steg framåt. Att utnyttja dessa kretsars naturliga beteende för att lösa verkliga problem är ett mycket övertygande alternativ för vad nästa datatid kan vara. "

Denna artikel publiceras på nytt med tillstånd av MIT News (web.mit.edu/newsoffice/), en populär webbplats som täcker nyheter om MIT -forskning, innovation och undervisning.