Vad är optimering?

Optimering är processen att hitta den bästa lösningen på ett problem utifrån en uppsättning möjliga alternativ, med tanke på önskat resultat och begränsningar.

Den bästa lösningen kan definieras på många sätt: det kan vara alternativet med den lägsta kostnaden, den snabbaste körningen eller kanske den lägsta miljöpåverkan. För att hålla det enkelt definieras bäst som en kostnad som ska minimeras. Om du vill maximera kostnaden i stället (till exempel om du vill maximera energiutdata från en solcell) behöver du bara multiplicera kostnaden med negativ och sedan minimera den.

Mer information om optimeringsproblem och terminologi finns i viktiga begrepp inom optimering.

Optimering är en klass av beräkningsproblem som är primära kandidater för körning på kvantdatorer i framtiden, vilket ger en kvantfördel jämfört med klassiska lösningar. Du kan redan implementera optimeringsproblem med hjälp Azure Quantum som körs på klassisk maskinvara i Azure idag snabbare än många andra klassiska optimeringstekniker.

Vad är kvantinspirerad optimering?

Simulering av kvanteffekterna på klassiska datorer har lett till utvecklingen av nya typer av kvantlösningar. Kvantinspirerade optimeringsalgoritmer utnyttjar några av fördelarna med kvantberäkning på klassisk maskinvara, vilket ger en hastighetsfördrång över traditionella metoder.

Kvantinspirerade algoritmer är klassiska algoritmer där du klassiskt emulerar de viktiga kvantfenomen som ger hastigheten. Det finns många typer av kvantinspirerade algoritmer. En vanlig algoritm baseras på en beräkningsmodell som kallas adiabatisk kvantberäkning, som består av följande:

1. Först förbereder du ett system och initierar det till dess lägsta energitillstånd.

2. Sedan transformerar du långsamt det systemet till ett mer komplext system som beskriver det problem du försöker lösa. Den adiabaiska modellen säger att så länge den här omvandlingen sker tillräckligt långsamt, har systemet tid att anpassa sig och håller sig i den lägsta energikonfigurationen. När omvandlingarna är klara kan du lösa problemet.

En bra liknelse är att föreställa sig ett glas med vatten. Om du flyttar glaset långsamt på ett bord spills inte innehållet eftersom systemet har tillräckligt med tid att anpassa sig till den nya konfigurationen. Men om du skulle flytta glassen snabbt har systemet blivit tvingad att ändras för snabbt och du har vatten överallt.

Var kan kvantinspirerad optimering användas?

Genom att tillämpa kvantinspirerad optimering på verkliga problem kan företag få nya insikter eller sänka kostnaderna genom att göra sina processer effektivare. Kvantinspirerad optimering ger oss möjlighet att:

• Hitta en lösning snabbare än med andra optimeringstekniker för ett fast användningsfall och en fast lösningskvalitet.
• Hitta en lösning med högre kvalitet än med andra optimeringstekniker för ett fast problem och en fast varaktighet.
• Använda en mer realistisk modell än andra optimeringstekniker genom att utöka problemet så att fler variabler beaktas.

Eftersom kvantinspirerade optimeringsmetoder är heuristik är de inte garanterade att hitta den optimala lösningen, och de överträffar inte heller alltid andra optimeringstekniker. I verkligheten beror det på problemet och att upptäcka vad som får kvantinspirerad optimering att prestera bättre än andra metoder i vissa situationer och inte andra är fortfarande ett aktivt forskningsområde.

Här är de nödvändiga villkoren för att kvantinspirerad optimering ska fungera väl jämfört med andra klassiska optimeringsalgoritmer:

• Optimeringslandskap ska vara ojämna men strukturerade. Sådana landskap förekommer ofta i verkliga problem. Mer information finns i Optimeringslandskap.
• Om antalet variabler är litet (till exempel mindre än hundra) räcker det redan med förenklade algoritmer. För problem med hundratals variabler har kvantinspirerad optimering uppnått förbättringar jämfört med tidigare använda metoder i storleksordning.
• Problemparametrar som påverkar det valda kostnadsmåttet måste representeras via variablerna för en kostnadsfunktion. Express cost fungerar som polynom över binära variabler för att få fram ett PUBO-problem.

Hur löser kvantinspirerad optimering problem?

Det finns flera metoder för att hitta det globala minimiantalet för en kostnadsfunktion. En av de mest framgångsrika och ofta använda heuristikerna är simulerad an annealing. Heuristik är en teknik för att hitta en ungefärlig lösning, särskilt i situationer där det kan ta för lång tid att hitta en exakt lösning. Du kan se tekniken som en slumpmässig genomgång av sökutrymmet, där varje fotgängare skapar en väg genom optimeringslandskapet.

I simulerad antrottning simulerar algoritmen en fotgängare som helst alltid rör sig i nedförsbacke men som också kan ta uppförsbacke med en viss sannolikhet som inte är noll. Detta skapar möjligheten för fotgängaren att undkomma lokala minima och sedan falla till djupare närliggande minima. Uppåtflyttningarna kallas termiska hopp. Det beror på att simulerad antrottning är en algoritm från fysiken som efterliknar beteendet för material när de kyls långsamt.

Kvantinspirerad optimering använder sig av tekniker för att lösa kombinatoriska problem med simulerad antrottning men tillämpar kvantmekaniska effekter.

Kvantanering är en kvantalgoritm som liknar simulerad antrottning, men den skiljer sig på några olika sätt. I simulerad antrottning utforskas sökområdet genom att göra termiska hopp från en lösning till nästa, medan kvant antringning använder en kvanteffekt som kallas kvanttunnlar , vilket gör att fotgängaren kan färdas genom dessa energibarriärer.

I det här diagrammet kan du se skillnaden mellan den klassiska metoden och kvant metoden. I simulerad antrottning hjälper termiska variationer en fotgängare att lösa en energibarriär, och i kvanttunnlar gör kvanteffekter att fotgängare kan passera energibarriären.

Azure Quantum optimeringstekniker

Azure Quantum erbjuder en mängd kvantinspirerade tekniker för att lösa diskreta och kombinatoriska optimeringsproblem.

• Parallell anlöpning:En relaterad klassisk optimeringsmetod där kopior av ett system förvaras vid olika temperaturer, vilket automatiserar upprepad uppvärmning och kylning i temperaturningsmetoder. Den kan användas för att påskynda både klassisk och (simulerad) kvant antrottning, samt många andra heuristiker.
• Simulated Annealing: En klassisk stokastisk simuleringsmetod som efterliknar den långsamma kylningen av ett material (antrötning) för att ta bort brister. En temperatur minskas enligt ett schema. Termiska hopp hjälper till att undvika lokala minima i sökrymden.
• Befolkningsanering:Precis som simulerad an annealing simulerar en fotgängare som helst alltid rör sig nedåt, simulerar befolkningsanering en population med fotgängare, som kontinuerligt konsoliderar sökarbetet kring fördelaktiga tillstånd.
• Quantum Monte Carlo:En kvantinspirerad optimering som efterliknar kvant antrottningsmetoden med hjälp av Monte-Carlo simuleringar. På samma sätt som temperaturen i simulerad antrottning minskar kraften i kvanttunnlar med tiden. Effekterna av kvanttunnlar hjälper till att komma bort från lokala minima i sökutrymmet.
• Substochastic Monte Carlo:Substochastic Monte Carlo är en monte Carlo-algoritm som inspireras av adiabatisk kvantberäkning. Den simulerar en population med fotgängare i sökrymden, där fotgängare tas bort eller dupliceras baserat på hur de presterar enligt kostnadsfunktionen.
• Tabu-sökning:Tabu Search tittar på närliggande konfigurationer. Den kan acceptera försämrade förflyttningar om inga förbättringsflyttningar är tillgängliga och förbjuder flytt till tidigare besökta lösningar

Observera att detta bara är en liten delmängd av de tillgängliga teknikerna, och Microsoft fortsätter att utveckla och lägga till nya lösare i Azure Quantum tjänsten. Mer information finns i listan över Microsoft QIO-leverantörer.