De beste digitale computers van vandaag hebben nog steeds moeite om op te lossen, in een praktisch tijdsbestek, een bepaalde klasse van problemen:combinatorische optimalisatieproblemen, of die waarbij een groot aantal mogelijkheden wordt uitgekamd om de beste oplossing te vinden. Quantumcomputers hebben potentieel om deze problemen aan te pakken, maar het opschalen van het aantal kwantumbits in deze systemen blijft een horde.

Nutsvoorzieningen, MIT Lincoln Laboratory-onderzoekers hebben een alternatief aangetoond, analoge manier om de berekening van deze problemen te versnellen. "Onze computer werkt door 'computing with physics' en gebruikt de natuur zelf om deze moeilijke optimalisatieproblemen op te lossen, " zegt Jeffrey Chou, co-hoofdauteur van een paper over dit werk gepubliceerd in Nature's Wetenschappelijke rapporten . "Het is gemaakt van standaard elektronische componenten, waardoor we onze computer snel en goedkoop kunnen schalen door gebruik te maken van de bestaande microchip-industrie."

Misschien wel het meest bekende combinatorische optimalisatieprobleem is dat van de handelsreiziger. Het probleem vraagt ​​om de kortste route te vinden die een verkoper kan nemen door een aantal steden, beginnend en eindigend op dezelfde. Het lijkt misschien eenvoudig met slechts een paar steden, maar het probleem wordt exponentieel moeilijk op te lossen naarmate het aantal steden groeit, zelfs de beste supercomputers vastlopen. Maar optimalisatieproblemen moeten in de echte wereld dagelijks worden opgelost; de oplossingen worden gebruikt om diensten in te plannen, het financiële risico minimaliseren, drugs ontdekken, zendingen plannen, interferentie op draadloze netwerken te verminderen, en nog veel meer.

"Het is al heel lang bekend dat digitale computers fundamenteel slecht zijn in het oplossen van dit soort problemen. " zegt Suraj Bramhavar, ook een co-hoofdauteur. "Veel van de algoritmen die zijn bedacht om oplossingen te vinden, moeten de kwaliteit van de oplossing inruilen voor tijd. Het vinden van de absoluut optimale oplossing kost onredelijk veel tijd als het probleem groter wordt." Door betere oplossingen te vinden en dit in aanzienlijk minder tijd te doen, kunnen industrieën miljarden dollars besparen. Dus, onderzoekers hebben gezocht naar nieuwe manieren om systemen te bouwen die speciaal zijn ontworpen voor optimalisatie.

De beat vinden

De natuur optimaliseert graag energie, of doelen bereiken op de meest efficiënte en gedistribueerde manier. Dit principe kan worden gezien in de synchronie van de natuur, zoals hartcellen die tegen elkaar slaan of scholen vissen die als één geheel bewegen. evenzo, als je twee slingerklokken op hetzelfde oppervlak zet, het maakt niet uit wanneer de individuele slinger in beweging wordt gezet, ze zullen uiteindelijk in slaap worden gesust in een gesynchroniseerd ritme, tegelijkertijd hun top bereiken, maar in tegengestelde richtingen bewegen (of uit fase). Dit fenomeen werd voor het eerst waargenomen in 1665 door de Nederlandse wetenschapper Christiaan Huygens. Deze klokken zijn een voorbeeld van gekoppelde oscillatoren, zo opgesteld dat er energie tussen hen kan worden overgedragen.

"We hebben in wezen een elektronische, programmeerbare versie van deze [klokopstelling] met behulp van gekoppelde niet-lineaire oscillatoren, "Chou zegt, met een YouTube-video van metronomen die een soortgelijk fenomeen vertonen. "Het idee is dat als je een systeem opzet dat het energielandschap van je probleem codeert, dan zal het systeem natuurlijk proberen de energie te minimaliseren door te synchroniseren, en daarbij, zal tot de beste oplossing komen. Deze oplossing kunnen we dan voorlezen."

Het prototype van het laboratorium is een soort Ising-machine, een computer gebaseerd op een natuurkundig model dat een netwerk van magneten beschrijft, die elk een magnetische "spin" -oriëntatie hebben die alleen naar boven of naar beneden kan wijzen. De uiteindelijke oriëntatie van elke draai hangt af van de interactie met elke andere draai. De individuele spin-to-spin interacties worden gedefinieerd met een specifiek koppelingsgewicht, wat de sterkte van hun verbinding aangeeft. Het doel van een Ising-machine is om te vinden, gegeven een specifiek koppelingssterktenetwerk, de juiste configuratie van elke draai, op of neer, dat minimaliseert de totale systeemenergie.

Maar hoe lost een Ising-machine een optimalisatieprobleem op? Het blijkt dat optimalisatieproblemen direct op het Ising-model in kaart kunnen worden gebracht, zodat een set van a spins met bepaalde koppelingsgewichten elke stad en de afstanden daartussen kan vertegenwoordigen in het handelsreizigersprobleem. Dus, het vinden van de laagste energieconfiguratie van spins in het Ising-model vertaalt zich direct in de oplossing voor de snelste route van de verkoper. Echter, dit probleem oplossen door elk van de mogelijke configuraties afzonderlijk te controleren, wordt onbetaalbaar wanneer de problemen zelfs maar bescheiden worden.

In recente jaren, er zijn pogingen gedaan om kwantummachines te bouwen die overeenkomen met het Ising-model, de meest opvallende daarvan is er een van het Canadese bedrijf D-Wave Systems. Deze machines kunnen een efficiënte manier zijn om de grote oplossingsruimte te doorzoeken en het juiste antwoord te vinden, hoewel ze werken bij cryogene temperaturen.

Het systeem van het laboratorium voert een soortgelijke zoekopdracht uit, maar doet dit met behulp van eenvoudige elektronische oscillatoren. Elke oscillator vertegenwoordigt een spin in het Ising-model, en neemt op dezelfde manier een binaire fase aan, waar oscillatoren die gesynchroniseerd zijn, of in fase, vertegenwoordigen de "spin-up"-configuratie en degenen die uit fase zijn vertegenwoordigen de "spin-down"-configuratie. Om het systeem in te stellen om een ​​optimalisatieprobleem op te lossen, het probleem wordt eerst toegewezen aan het Ising-model, vertalen naar programmeerbare koppelingsgewichten die elke oscillator verbinden.

Met de koppelingsgewichten geprogrammeerd, de oscillatoren mogen draaien, zoals de slingerarm van elke klok die wordt losgelaten. Het systeem ontspant dan op natuurlijke wijze tot zijn algehele minimale energietoestand. Elektronisch uitlezen van de eindfase van elke oscillator, staat voor "spin up" of "spin down, " geeft het antwoord op de gestelde vraag. Toen het systeem tegen meer dan 2 liep, 000 willekeurige optimalisatieproblemen, het kwam 98 procent van de tijd tot de juiste oplossing.

Eerder, onderzoekers van Stanford University demonstreerden een Ising-machine die lasers en elektronica gebruikt om optimalisatieproblemen op te lossen. Dat werk onthulde het potentieel voor een aanzienlijke versnelling ten opzichte van digitaal computergebruik, hoewel, volgens Cho, het systeem kan moeilijk en kostbaar zijn om op grotere formaten te schalen. Het doel van het vinden van een eenvoudiger alternatief was de aanleiding voor het onderzoek van het laboratorium.

Opschalen

Het individuele oscillatorcircuit dat het team in hun demonstratie gebruikte, is vergelijkbaar met circuits in mobiele telefoons of wifi-routers. Een toevoeging die ze hebben gemaakt, is een crossbar-architectuur waarmee alle oscillatoren in het circuit direct aan elkaar kunnen worden gekoppeld. "We hebben een architectuur gevonden die zowel schaalbaar is om te produceren als volledige connectiviteit met duizenden oscillatoren mogelijk maakt, ", zegt Chou. Dankzij een volledig verbonden systeem kan het eenvoudig worden toegewezen aan een breed scala aan optimalisatieproblemen.

"Dit werk van Lincoln Laboratory maakt innovatief gebruik van een crossbar-architectuur bij de constructie van een analoog-elektronische Ising-machine, " zegt Peter McMahon, een assistent-professor toegepaste en technische fysica aan de Cornell University die niet betrokken was bij dit onderzoek. "Het zal interessant zijn om te zien hoe toekomstige ontwikkelingen van deze architectuur en dit platform presteren."

Het prototype van de Ising-machine van het laboratorium maakt gebruik van vier oscillatoren. Het team werkt nu aan een plan om het prototype op te schalen naar grotere aantallen oscillatoren, of "knooppunten, " en maak het op een printplaat. "Als we kunnen komen, zeggen, 500 knooppunten, is er een kans dat we kunnen gaan concurreren met bestaande computers, en op 1, 000 knooppunten kunnen we ze misschien verslaan, ' zegt Bramhavar.

Het team ziet een duidelijke weg voorwaarts naar opschaling omdat de technologie gebaseerd is op standaard elektronische componenten. Het is ook extreem goedkoop. Alle onderdelen voor hun prototype zijn te vinden in een typisch niet-gegradueerd elektrotechnisch laboratorium en werden online gekocht voor ongeveer $ 20.

"Wat mij boeit is de eenvoud, Bramhavar voegt toe. "Van quantumcomputers wordt verwacht dat ze verbazingwekkende prestaties leveren, maar de wetenschappelijke en technische uitdagingen die nodig zijn om ze op te schalen zijn behoorlijk moeilijk. Het demonstreren van zelfs maar een klein deel van de prestatiewinst die wordt verwacht met kwantumcomputers, maar daarbij gebruikmakend van hardware uit de bestaande elektronica-industrie, zou een enorme sprong voorwaarts zijn. Het gebruik van het natuurlijke gedrag van deze circuits om echte problemen op te lossen, biedt een zeer aantrekkelijk alternatief voor wat het volgende computertijdperk zou kunnen zijn."

Dit verhaal is opnieuw gepubliceerd met dank aan MIT News (web.mit.edu/newsoffice/), een populaire site met nieuws over MIT-onderzoek, innovatie en onderwijs.