Volgens het concept van computationele complexiteit hebben wiskundige problemen verschillende moeilijkheidsgraden, afhankelijk van hoe gemakkelijk ze kunnen worden opgelost. Hoewel een conventionele computer sommige problemen (P) in polynoomtijd kan oplossen - dat wil zeggen, de tijd die nodig is om P op te lossen is een polynoomfunctie van de grootte van de invoer - slaagt hij er vaak niet in om NP-problemen op te lossen die exponentieel schalen met de probleemgrootte en kan daarom niet in polynomiale tijd worden opgelost. Daarom kunnen NP-problemen die groot genoeg zijn niet worden opgelost met behulp van conventionele computers die zijn gebouwd op halfgeleiderapparaten.
Vanwege hun vermogen om een aanzienlijk aantal bewerkingen tegelijkertijd uit te voeren, worden kwantumcomputers in dit opzicht als veelbelovend beschouwd. Als gevolg hiervan wordt de procedure voor het oplossen van NP-problemen versneld. Veel fysieke toepassingen zijn echter erg gevoelig voor temperatuurveranderingen.
Als gevolg hiervan vereist het gebruik van kwantumcomputers vaak zware experimentele omstandigheden, zoals extreem lage temperaturen, waardoor hun fabricage moeilijk wordt en hun kosten stijgen.
Gelukkig is een minder bekend en nog onontdekt alternatief voor quantum computing probabilistic computing. Om NP-problemen effectief op te lossen, maakt stochastisch computergebruik gebruik van zogenaamde "stochastische nanodevices" waarvan de werking afhangt van thermische fluctuaties. Thermische fluctuaties helpen, in tegenstelling tot kwantumcomputers, bij het oplossen van probabilistische rekenproblemen. Hierdoor is probabilistisch rekenen praktischer in het gebruik in alledaagse situaties.
Onderzoekers hebben het vermogen van probabilistische berekeningen bewezen door stochastische nano-apparaatnetwerken te simuleren om specifieke NP-problemen op te lossen, waardoor de broodnodige informatie over dit levensvatbare alternatief wordt verkregen. Het onderzoek, geleid door professor Peter Bermel aan de Purdue University, is gepubliceerd in het Journal of Photonics for Energy (JPE).
Het "Ising-model", een standaardmodel, werd door onderzoekers gebruikt om een breed scala aan fysische en wiskundige onderwerpen te simuleren. De energie-operator die bekend staat als de "Hamiltonian" kan ook NP-problemen beschrijven. De Hamiltoniaan is oorspronkelijk ontwikkeld om de interacties van magnetische dipoolmomenten van atomaire spins te modelleren. In wezen vereist het oplossen van een NP-probleem het oplossen van de bijbehorende Ising Hamiltoniaan.
Deze problemen worden opgelost met behulp van probabilistische computerapparatuur bestaande uit optische parametrische oscillatoren (OPO's) en stochastische cirkelvormige nanomagneetnetwerken met lage thermische barrières.
Onderzoekers hebben zo'n nanomagneetnetwerk geactiveerd met behulp van bestaande fabricagetechnieken. Vervolgens pasten ze dit toe om de Ising Hamiltonianen van vier NP-complete problemen uit de getaltheorie op te lossen die verband houden met combinatorische optimalisatie. NP-complete problemen zijn problemen die geen efficiënt oplossingsalgoritme hebben. Deze omvatten integer lineaire programmering, binaire integer lineaire programmering, volledige dekking en nummerpartitionering.
De theoretische oplossing van het Ising-model (wet van Boltzmann) en de simulatieresultaten van de eerste drie problemen met 3, 3 en 6 probabilistische bits (p-bits) kwamen perfect overeen. Simulaties van vijf verschillende problemen met volledige dekking met 3, 6, 9, 12 en 15 p-bits onthulden een vergelijkbare overeenkomst tussen modellering en theorie. Dit toonde aan dat raamwerken voor probabilistisch computergebruik kunnen worden geschaald.
Volgens Bermel, “is de sleutel om van probabilistisch computergebruik een krachtig en levensvatbaar alternatief voor traditionele computertechnieken te maken, effectief schalen met de taakomvang. Zowel modellen als experimenten zullen moeten worden gebruikt om te bepalen welke strategieën het meest effectief zijn.
De onderzoekers suggereren dat zelfs als de gegeven simulatieresultaten solide bevindingen laten zien voor alle p-bits (van 3 tot 15), parallelle algoritmen kunnen helpen de simulatiecapaciteit verder te vergroten. De overgang van nanomagneet- naar OPO-netwerken kan effectieve probleemoplossing mogelijk maken waar parallellisme niet mogelijk is. Het systeem kan eenvoudig worden geïmplementeerd en in kaart worden gebracht via een OPO-netwerk met behulp van bestaande productieprocessen zoals CMOS-technologie. Als gevolg hiervan kunnen uiteindelijk stochastische nanomagneten met lage energiebarrières voor probabilistische berekeningen worden geconstrueerd.
Volgens Sean Shaheen, professor in Boulder aan de Universiteit van Colorado en hoofdredacteur van JPE: "Nu kunstmatige intelligentie en wetenschappelijke/bedrijfscomputing zo snel toenemen dat er significante, zo niet urgente zorgen ontstaan over energieverbruik en koolstofvoetafdruk, -traditionele vormen van ontwikkeling van computerhardware worden steeds belangrijker.”
Dit werk van Zhu, Xi en Bermel biedt een realistisch pad naar technologie die een aanzienlijke klasse van NP-complete problemen aankan. Het werk demonstreert een schaalbare, energie-efficiënte oplossing die het potentieel heeft om conventionele hardware aanzienlijk te overtreffen bij het uitvoeren van rekenintensieve taken door ingenieus gebruik te maken van niet-lineaire netwerken van optische apparaten om Ising-berekeningen aan te sturen.
Bron: techxplore.com/news
📩 03/05/2023 14:19