Quantum Annealing

Kurzfassung

Quantum Annealer sind spezielle Quantenarchitekturen, die auf Basis des adiabatischen Theorems ein Quantensystem in ein anderes durch adiabatische Evolution überführen und dabei den Grundzustand, den Zustand der niedrigsten Energie, erhalten. Durch Kodieren einer Funktion im Zielquantensystem kann damit deren Minimum bestimmt werden. Da die theoretischen Voraussetzungen des adiabatischen Theorems jedoch in der Realität nie vollständig erfüllt werden können, stellt der Quantum Annealer einen heuristischen Optimierer für diese Zielfunktionen dar, der durch wiederholtes Ausführen die Optimallösung nur mit einer gewissen Wahrscheinlichkeit findet. Die Firma D-Wave Systems Inc. ist die erste, die einen Quantum Annealer kommerziell verfügbar machte. Die Realisierung der Qubits über überlappende supraleitende Schleifen erlaubt hierbei die Optimierung quadratischer Zielfunktionen über binäre Variablen. Diese sogenannten Ising-Probleme sind klassisch schwer zu lösende Probleme. Dazu gehört beispielsweise das Flugzeug-Gate-Zuordnungsproblem, bei dem die Zeit, die Transitpassagiere von einem Gate zum anderen benötigen, optimiert wird. Die eingeschränkte Hardwarestruktur erfordert jedoch verschiedene Transformationsschritte. So müssen beispielsweise alle Variablen binär kodiert und Nebenbedingungen durch Strafterme in die Zielfunktion integriert werden. Zudem realisieren die Qubit-Kopplungen nur einen ganz bestimmten Hardwaregraphen, in den eine sogenannte Einbettung gefunden werden muss, bevor auf der Maschine Berechnungen durchgeführt werden können. Auf Basis dieser Einbettung muss anschließend das eingebettete Ising-Problem formuliert werden, das das eigentlich zu lösende Problem auf der Maschine repräsentiert. Hierbei muss die eingeschränkte Maschinenpräzision beachtet werden. All diese Schritte haben einen starken Einfluss auf die Erfolgswahrscheinlichkeit und müssen daher mit großer Sorgfalt durchführt werden, um sinnvolle Experimente auf dem Quantum Annealer zu ermöglichen.