Combinatorial problems in programming quantum annealers

Abstract

Bevor auf einer Quanten-Annealing-Maschine, wie der der Firma D-Wave Systems Inc., Berechnungen durchgeführt werden können, sind zwei grundlegende Schritte notwendig, um das Originalproblem in ein Format zu übertragen, das von solchen Maschinen gelöst werden kann: Als Erstes muss ein mit dem Problem assoziierter Graph in den speziellen Hardwaregraphen eingebettet werden und als Zweites müssen die Parameter des eingebetteten Problems entsprechend weiterer Hardwarerestriktionen gewählt werden, sodass die Lösungen des eingebetteten Problems beweisbar äquivalent zu den ursprünglichen Lösungen sind. Diese Doktorarbeit adressiert graphentheoretische Fragestellungen und kombinatorische Optimierungsprobleme, die bei der genaueren Betrachtung beider Schritte auftreten. Im ersten Teil dieser Arbeit analysieren wir die Komplexität des Einbettungsproblems im Quanten- Annealing-Kontext, das heißt für Chimera- und Pegasus-Hardwaregraphen mit zum Teil nicht nutzbaren, „defekten“ Qubits. Wir beweisen die Schwere des Hamiltonkreisproblems, einem Spezialfall des Einbettungsproblems, in solchen Graphen durch die Konstruktion defekter Chimera-Graphen aus speziellen Graphen, für welche die Schwere des Problems bereits bekannt ist. Da der Chimera- ein Subgraph des Pegasus-Graphen ist, können wir das Resultat auf letzteren übertragen. Ein weiterer Spezialfall ist die Einbettung eines vollständigen Graphen, welcher ein universelles Template für die Einbettung von beliebigen Graphen mit einer kleineren oder gleich großen Zahl an Knoten darstellt. Durch die Formulierung als Matchingproblem mit zusätzlichen linearen Nebenbedingungen können wir zeigen, dass das Problem eingeschränkt auf die sich natürlich ergebende Einbettungsstruktur „fixed-parameter tractable“ ist, wenn wir die Zahl der defekten Qubits im Chimera-Graphen als Parameter betrachten. Wir vergleichen unser Verfahren mit vorherigen, heuristischen Ansätzen auf verschiedenen, zufällig generierten defekten Hardwaregraphen. Dabei können wir einen Vorteil unserer Methode gegenüber den anderen hinsichtlich der gefundenen Graphengrößen in der Praxis zeigen. Zusätzlich geben wir ein heuristisches Modell mit weniger Nebenbedingungen an, welches noch bessere Resultate liefert. Der zweite Teil beschäftigt sich mit derWahl der geeigneten Parameter, für welche wir hinreichende Bedingungen formulieren können. Durch die Betrachtung eines einzelnen Originalknotens und verschiedener, von der Hardware abgeleiteter Zielsetzungen können wir spezielle lineare Optimierungsprobleme extrahieren. Die Analyse eines entsprechenden Polyeders der zulässigen Lösungen zeigt, dass optimale Lösungen zu diesen Problemen in vielen Fällen in Linearzeit gefunden werden können. Für die verbleibenden Fälle konstruieren wir einen Algorithmus, der die Parameter in höchstens kubischer Laufzeit angibt. Aufgrund der Problemstruktur gelten diese Resultate sogar, wenn wir uns auf Ganzzahligkeit einschränken.

Before being able to perform calculations on a quantum annealing device such as D-Wave’s, two essential steps are required to transfer the original problem into a format which can be solved by these machines: First, a graph associated with the problem needs to be embedded into the specific hardware graph and, secondly, the parameters of the embedded problem need to be chosen, in accordance with further hardware restrictions, such that the solutions to the resulting problem are provably equivalent to those of the original problem. This thesis addresses graph theoretical questions and combinatorial optimization problems appearing in the closer examination of both steps. In the first part of this work, we analyze the complexity of the embedding problem in the quantum annealing context, this means when restricting to Chimera or Pegasus hardware graphs containing unavailable, ‘broken’ qubits. We prove the hardness of the Hamiltonian cycle problem, a special case of the embedding problem, in such graphs by constructing broken Chimera graphs from certain graphs for which it is known that finding a Hamiltonian cycle is hard. As the Chimera graph is a subgraph of the Pegasus graph, we can easily extend the result to the latter. A further special case is the embedding of a complete graph, forming a universal template for the embedding of all arbitrary graphs with a smaller or equal number of vertices. By formulating this problem as a matching problem with additional linear constraints, we can prove that the problem restricted to the naturally arising embedding structure is fixed-parameter tractable in the number of broken vertices in the Chimera graph. By testing our model against previous, heuristic approaches on various random broken hardware graphs, we can further show that our method performs superior in practice. Additionally, we provide a heuristic model with less constraints, showing an even better performance. The second part is concerned with the problem of setting feasible parameters for the machine, for which we can formulate sufficient requirements. Considering a single original vertex and different objectives derived from the hardware restrictions, we extract certain linear optimization problems. By analyzing a corresponding polyhedron of feasible solutions, we can show that optimal solutions to these problems can be found in linear time for a lot of cases. For the remaining cases, we construct an algorithm providing the parameters in at most cubic time. Due to the problem structure, these results even hold if we restrict ourselves to integer problems.