Beschleunigte TSP-Approximation durch Optimierung der Problemcodierung
In der ersten Projektphase von SEQUOIA haben wir einen Algorithmus entwickelt, der Instanzen von kombinatorischen Optimierungsproblemen in mehrere kleine Unterinstanzen gleicher Größe zerlegt. Die selektive Lösung einiger dieser Teilprobleme und die Kombination ihrer Lösungen ergibt eine Lösung für die ursprüngliche Problemstellung. Dieser Ansatz wurde durch die begrenzte Anzahl von Qubits der derzeit verfügbaren Quantenhardware motiviert.
In SEQUOIA End-to-End beschäftigten wir uns mit der Methode zur Lösung der generierten Teilprobleme. In der ersten Projektphase haben wir zur Lösung der Teilprobleme QAOA so implementiert, wie es in Forschungsarbeiten beschrieben ist. Wir stellten jedoch Mängel bei der Laufzeit und der Lösungsqualität fest, die das Gesamtergebnis stark beeinträchtigten. Daher beschlossen wir, eine andere Problemkodierung für das TSP zu konstruieren, die es uns ermöglichen würde, die Problemparameter und -beschränkungen direkter in einem Quantenschaltkreis zu implementieren. Die Kernidee besteht darin, die Abstände zwischen den Punkten direkt zu kodieren, anstatt eine 1-hot-kodierte Reihe von Punkten zu verwenden. Wir stellen unsere Implementierung und die Ergebnisse im Demonstrator vor und vergleichen sie mit dem bisherigen Ansatz.
Szenariobasierte Routenplanung zur Absicherung automobiler Fahrfunktionen (TSP/ORP)
Der Demonstrator zeigt zwei verschiedene Modellierungsansätze und entsprechende Implementierungen für die szenariobasierte Routenplanung. Der erste Ansatz basiert auf einer im Rahmen des Projekts erstellten QAOA-Implementierung für das »Traveling Salesperson Problem«. Darüber hinaus wird ein im Rahmen des Projekts entwickelter Algorithmus zur Partitionierung des TSP demonstriert. Der Algorithmus, der auf A* basiert, teilt große TSP-Instanzen in mehrere kleinere auf, so dass sie auf dem Quantencomputer gelöst werden können. Dabei handelt es sich um einen hybriden Ansatz, bei dem die Partitionierung auf einem klassischen Computer erfolgt und nur der schwierige kombinatorische »Kern« des Problems auf einem Quantencomputer gelöst wird. Unsere QAOA-Implementierung ist in diesen Algorithmus eingebettet und kann alternativ zum Vergleich mit dem klassischen Löser ausgetauscht werden. Um unsere Methode bei der Auswahl der zu erzeugenden Subinstanzen zu leiten, haben wir mehrere Heuristiken entwickelt. Dazu gehört vor allem ein kleines neuronales Netz, das die erwartete Länge einer TSP-Instanz abschätzen kann. Der zweite Ansatz modelliert das Problem als ein Orientierungsproblem und nicht als das übliche TSP. Das Orientierungsproblem ist eine Kombination aus TSP und Knapsackproblem. In diesem Ansatz zeigen wir, wie sich diese Art der Modellierung auf die Implementierung und die Komplexität des zugrunde liegenden Optimierungsproblems auswirkt.
Haftungsausschluss
Die interaktiven Demonstratornotebooks wurden unter der Apache-Lizenz (Version 2.0) lizenziert. Die Dateien dürfen nur in Übereinstimmung mit der Lizenz verwendet werden. Eine Kopie der Lizenz kann unter http://www.apache.org/licenses/LICENSE-2.0 abgerufen werden. Sofern nicht durch geltendes Recht vorgeschrieben oder schriftlich vereinbart, wird unter dieser Lizenz vertriebene Software auf einer »AS IS«-Basis vertrieben, ohne Gewährleistungen oder Bedingungen jeglicher Art, weder explizit noch implizit. In der Lizenz finden Sie die damit verbundenen spezifischen Bestimmungen zu den Rechten und Beschränkungen.
Dies ist ein Forschungsprototyp. Die Haftung für entgangenen Gewinn, Produktionsausfall, Betriebsunterbrechung, entgangene Nutzungen, Verlust von Daten und Informationen, Finanzierungsaufwendungen sowie sonstige Vermögens- und Folgeschäden ist, außer in Fällen von grober Fahrlässigkeit, Vorsatz und Personenschäden, ausgeschlossen.