Wat is optimalisatie?

Optimalisatie is het proces van het vinden van de beste oplossing voor een probleem vanuit een reeks mogelijke opties, gezien het gewenste resultaat en de gewenste beperkingen.

De beste oplossing kan op verschillende manieren worden gedefinieerd: dit kan de optie zijn met de laagste kosten, de snelste runtime of misschien wel de laagste impact op het milieu. Om het eenvoudig te houden, wordt het beste meestal gedefinieerd als een kosten die moeten worden geminimaliseerd. Als u in plaats daarvan de kosten wilt maximaliseren (bijvoorbeeld als u de energie-uitvoer van een zonnecel wilt maximaliseren), hoeft u de kosten alleen maar te vermenigvuldigen met een negatieve cel en deze vervolgens te minimaliseren.

Zie de belangrijkste concepten van optimalisatie voor meer informatie over optimalisatieproblemen en de terminologie.

Optimalisatie is een klasse computingproblemen die in de toekomst een belangrijke kandidaat zijn voor het uitvoeren op kwantumcomputers, wat een kwantumvoordeel biedt ten opzichte van klassieke oplossingen. U kunt optimalisatieproblemen al implementeren met behulp Azure Quantum oplossers die tegenwoordig op klassieke hardware in Azure worden uitgevoerd, sneller dan veel andere klassieke optimalisatietechnieken.

Wat is op kwantum geïnspireerde optimalisatie?

Het simuleren van de kwantumeffecten op klassieke computers heeft geleid tot de ontwikkeling van nieuwe typen kwantumoplossingen. Op kwantum geïnspireerde optimalisatiealgoritmen maken gebruik van enkele van de voordelen van kwantumcomputing op klassieke hardware, waardoor de traditionele benaderingen sneller worden uitgevoerd.

Door kwantum geïnspireerde algoritmen zijn klassieke algoritmen waarin u de essentiële kwantumfenomenen die de versnelling bieden, op klassieke basis nabootsen. Er zijn veel soorten op kwantum geïnspireerde algoritmen. Een veelgebruikt algoritme is gebaseerd op een rekenmodel met de naam adiabatische kwantumcomputing, dat uit het volgende bestaat:

1. Eerst bereidt u een systeem voor en initialiseert u het naar de laagste energietoestand.

2. Vervolgens transformeert u dat systeem in een complexer systeem, dat voldoet aan het probleem dat u probeert op te lossen. Het adiabatische model geeft aan dat, zolang deze transformatie langzaam genoeg wordt gedaan, het systeem tijd heeft om zich aan te passen en in die laagste energieconfiguratie blijft. Wanneer de transformaties zijn uitgevoerd, kunt u het probleem oplossen.

Een goede analogie hiervan is om u voor te stellen dat u een glas water hebt. Als u het glas langzaam over een tafel verplaatst, gaat de inhoud niet over de rand, omdat het systeem de tijd heeft om zich aan te passen aan de nieuwe configuratie. Als u het glas echter snel zou verplaatsen, is het systeem gedwongen om te snel te veranderen en hebt u overal water.

Waar kan op kwantum geïnspireerde optimalisatie worden toegepast?

Het toepassen van op kwantum geïnspireerde optimalisatie op problemen in de echte wereld kan bedrijven nieuwe inzichten bieden of helpen de kosten te verlagen door hun processen efficiënter te maken. Op kwantum geïnspireerde optimalisatie biedt ons de mogelijkheid om:

• Sneller een oplossing te vinden dan met andere optimalisatietechnieken voor een gelijkblijvend gebruiksscenario en een gelijkblijvende kwaliteit van de oplossing.
• Een oplossing van hogere kwaliteit te vinden dan bij andere optimalisatietechnieken voor een gelijkblijvend probleem en een gelijkblijvende hoeveelheid tijd.
• Een realistischer model te gebruiken dan bij andere optimalisatietechnieken door het probleem uit te breiden en met meer variabelen rekening te houden.

Omdat op kwantum geïnspireerde optimalisatiemethoden heuristiek zijn, is het niet gegarandeerd dat ze de optimale oplossing vinden en ook niet altijd beter presteren dan andere optimalisatietechnieken. In werkelijkheid is het afhankelijk van het probleem en het ontdekken wat door kwantum geïnspireerde optimalisatie in sommige situaties beter presteert dan andere methoden en andere niet, is nog steeds een actief onderzoeksgebied.

Hier zijn de voorwaarden die nodig zijn om op kwantum geïnspireerde optimalisatie goed te laten presteren, vergeleken met andere klassieke optimalisatiealgoritmen:

• Optimalisatielandschappen moeten ruw maar gestructureerd zijn. Dergelijke landschappen komen vaak voor bij problemen in de echte wereld. Zie Optimalisatielandschappen voor meer informatie.
• Als het aantal variabelen klein is (bijvoorbeeld minder dan honderd), zijn eenvoudige algoritmen al voldoende. Voor problemen met honderden variabelen heeft op kwantum geïnspireerde optimalisatie een verbetering bereikt ten opzichte van eerder gebruikte methoden met orde van grootte.
• Probleemparameters die van invloed zijn op de gekozen metrische kosten, moeten worden weergegeven via de variabelen van een kostenfunctie. Kostenfuncties voor express als polynomialen over binaire variabelen om een PUBO-probleem op te lossen.

Hoe kunnen problemen worden opgelost met op kwantum geïnspireerde optimalisatie?

Er bestaan verschillende methoden om het globale minimum van een kostenfunctie te vinden. Een van de meest succesvolle en veelgebruikte heuristieken is simulated annealing. Heuristiek is een techniek voor het vinden van een geschatte oplossing, met name in situaties waarin het te lang kan duren om een exacte oplossing te vinden. U kunt de techniek zien als een willekeurige walk through the search space, waarbij elke wandelaar een pad door het optimalisatielandschap maakt.

Bij simulated annealing simuleert het algoritme een wandelaar die, in het ideale ideale, altijd een gaatje verplaatst, maar zich ook omhoog kan bewegen met een bepaalde waarschijnlijkheid van niet-nul. Hiermee ontstaat de mogelijkheid dat de wandelaar aan lokale minima kan ontsnappen en dieper in nabijgelegen minima kan afdalen. De omhoogwaartse zetten worden thermische jumps genoemd. Dat komt doordat simulated annealing een algoritme uit de fysica is dat het gedrag van materialen nabootst wanneer ze langzaam worden gekoeld.

Op kwantum geïnspireerde optimalisatie maakt gebruik van de technieken voor het oplossen van combinatoriële problemen van simulated annealing, maar het toepassen van kwantummechanische effecten.

Quantum annealing is een kwantumalgoritme dat vergelijkbaar is met simulated annealing, maar dat op een aantal manieren verschilt. In simulated annealing wordt de zoekruimte verkend door thermische jumps van de ene oplossing naar de volgende te maken, terwijl quantum annealing gebruikmaakt van een kwantumeffect dat kwantumtunneling wordt genoemd, waarmee de wandelaar deze energiebarrières kan passeren.

In deze grafiek ziet u het verschil tussen de klassieke en de kwantumbenadering. Bij simulated annealing van thermische schommelingen kan een wandelaar een energiebarrière overwinnen en bij kwantumtunneling kunnen kwantumeffecten een wandelaar de energiebarrière laten passeren.

Azure Quantum optimalisatietechnieken

Azure Quantum biedt een scala aan op kwantum geïnspireerde technieken om discrete en combinatoriële optimalisatieproblemen op te lossen.

• Parallelle koeling:een gerelateerde klassieke optimalisatiebenadering, waarbij kopieën van een systeem bij verschillende temperaturen worden bewaard, waarbij herhaalde koeling en koeling in de dempingsmethoden worden automatiseren. Het kan worden gebruikt om zowel klassieke als (gesimuleerde) quantum annealing te versnellen, evenals vele andere heuristieken.
• Simulated Annealing:een klassieke stochastische simulatiemethode die de trage koeling van een materiaal nabootst (annealing) om fouten te verwijderen. Een temperatuur wordt verlaagd volgens een schema. Thermische hops helpen bij het escapen van lokale minima in de zoekruimte.
• Population Annealing:Net zoals Simulated Annealing een wandelaar simuleert die in het ideale ideale scenario altijd naar de stad gaat, simuleert Population Annealing een populatie van de !
• Quantum Monte Carlo:een op kwantum geïnspireerde optimalisatie die de quantum annealing-methode nabootst met behulp van kwantumsimulaties Monte-Carlo simulaties. Vergelijkbaar met de temperatuur in simulated annealing, wordt de kracht van kwantumtunneling in de tijd verminderd. Kwantumtunnelingseffecten helpen bij het escapen van lokale minima in de zoekruimte.
• Substochastic Monte Carlo:Substochastic Monte Carlo is een monte carlo-algoritme dat is geïnspireerd op adiabatische kwantumberekening. Het simuleert de longon van een populatie van !'s in de zoekruimte, waar de wandelaar wordt verwijderd of gedupliceerd op basis van de manier waarop ze presteren op basis van de kostenfunctie.
• Tabu Search:Tabu Search kijkt naar aangrenzende configuraties. Het kan worden geaccepteerd als er geen verbeteringen beschikbaar zijn en de overstap naar eerder bezochte oplossingen wordt verboden

Houd er rekening mee dat dit slechts een kleine subset van beschikbare technieken is en dat Microsoft nieuwe oplossingen blijft ontwikkelen en toevoegen aan de Azure Quantum service. Zie de lijst met Microsoft QIO-provider voor meer informatie.