Quantum Annealing Simulator

Der Quantum Annealing Simulator steht via RESTful API zur Verfügung und unterstützt bei der Erforschung und Erprobung von Lösungen.

Was ist simulated annealing?

Simulated annealing ist ein klassischer Optimierer, der verwendet wird, um ein globales Optimum zu finden. Ein Optimierungsproblem wird in ein Energieproblem umgewandelt und daraufhin wird nach dem globalen Optimum in dem Energieproblem gesucht. Der Vorteil dieses Optimierers ist, dass er eine Wahrscheinlichkeit, sogenannte acceptance probability verwendet. Diese Wahrscheinlichkeit gibt an, ob er von einem Zustand zu einem anderen Zustand wechseln soll. Das heisst, er kann auch zu einem Zustand wechseln, welcher ein schlechteres Energieniveau hat. In dem Falle einer komplexen Energiefunktionen ist dies notwendig, da es mehrere lokale Optima gibt und sonst stecken bleibt.

Eine wesentliche Rolle ist die Temperatur. Die acceptance probability ist nämlich von der Temperatur abhängig. Ist die Temperatur hoch, fällt es dem Optimierer einfacher zu einem anderen Energie-niedrigeren Zustand zu wechseln. Man fängt bei einer hohen Temperatur an und sinkt langsam. Das heißt also, ist der Zustand in einem lokalen Optima, dann sollte die Temperatur hoch genug sein, sodass man aus diesem wieder herraus kommt. Ist der Zustand jedoch in einem globalen Optima, dann sollte die Temperatur niedrig sein, um die acceptance probability klein zu halten und keine schlechteren Energieniveaus anzunehmen.


Diese Methode basiert auf dem Prinizip des Annealings, wo es darum geht Metalle langsam abzukühlen, um diesen stabil zu halten.

Was ist Simulated quantum annealing?

In quantum annealing ist die Wahrscheinlichkeit jedoch von Hamiltonians gegeben, die stoquastic sind. Stoquastic bedeutet, die Matrizen sind reell und nicht positiv. Wendet man nun auf die Hamiltonians Quantum Monte Carlo an, dann ist das simulated quantum annealing. In diesem Annealer wird die Path integral Monte Carlo methode verwendet, d.h. Monte Carlo als Pfadintegral umgeschrieben. Pfadintegrale werden oft in der Quantenmechanik und Quantenfeldtheorie verwendet, wie z.B. um alle möglichen Pfade von Teilchen zu berechnen. In dem Fall werden diese verwendet, um die thermische Dichtematrix zu berechnen, welche die Beziehung zwischen den Zuständen definiert.

Parametereinstellungen im Annealer:

  • Ginit: Initiale Start-Temperatur

  • Gfin: Temperatur, bis zu der abgekühlt erreicht werden soll

  • Tau: Schrittweite mit der man die Temperatur reduzieren möchte. Hier wurde G = G_0 *tau verwendet.

  • Beta: kann bei der verwendung von simulated annealing ignoriert werden. Im Falle von SQA jedoch ist die acceptance probability von beta abhängig. (exp(-dE*beta))

  • Algorithm: coloring oder sa_naive. Coloring ist SQA und sa_naive ist SA.

Input:

Der Annealer löst sogenannte Quadratic Unconstrained Binary Optimization (QUBO) Probleme. Optimierungsprobleme mit/ohne Nebenbedingungen können in ein QUBO Problem umgewandelt werden und der Annealer nimmt dann die QUBO Matrix entgegen. Die Matrix wird in mehreren Iteration berechnet, um das globale Optimum zu finden.

Nachdem die Berechnung abgeschlossen ist, wird ein bitstring mit der optimalen Energie (niedrigsten Energie) zurückgegeben, inkl. der zugehörigen Energie und der Laufzeit.

Project Numbers

live

hoch

hoch