Quadratische binäre Optimierung ohne Nebenbedingungen auf Chimera-Graphen

Abstract

In dieser Arbeit werden zunächst die Grundlagen der Optimierung über quadratische Funktionen mit binären Variablen ohne Nebenbedingungen (QUBOs) vorgestellt und einige Reduktionsmöglichkeiten verschiedener kombinatorischer Optimierungsprobleme darauf aufgezeigt. Der zweite Teil konzentriert sich auf den speziellen Chimera-Graphen als Interaktionsgraph von QUBOs. Dieser ergibt sich aus der Hardware-Struktur des adiabatischen Quanten-Annealers der Firma D-Wave Systems, welcher solche QUBOs lösen kann. Insbesondere wird hier auf spezielle Minoren des Chimera-Graphen und die Einbettungsproblematik allgemeiner Graphen eingegangen. Der dritte Teil zeigt auf, wie die vorherigen Ergebnisse genutzt werden können, um das Problem der Satellitenmissionsplanung schrittweise in ein entsprechendes QUBO zu übertragen. Anschließend wird die Veränderung der Problemgröße und Übertragbarkeit auf den Quanten-Annealer evaluiert.