ADMM-Surrogate
Gemischt-ganzzahlige oder gemischt-binäre lineare Programmierungsprobleme stellen eine bedeutende Klasse an Optimierungsproblemen dar und sind ein interessantes Objekt für Quantencomputing. Dieses Notebook demonstriert, wie ein gemischt binäres Problem mit Hilfe eines Quantencomputers optimiert werden kann. Zwei verschiedene Strategien sind in diesem Notebook implementiert: eine die vom klassischen ADMM-Algorithmus inspiriert ist und eine andere, die ein Kriging-Surrogate-Modell nutzt. Beide bauen auf dem VQE-Algorithmus auf um das binäre Problem zu optimieren. Sie können mit verschiedenen Ansatzfunktionen und Optimierern für VQE getestet und verglichen werden. Derzeit sind gemischt-binäre Zwangsbedingungen in Form von Gleichungen sowie Intervalle für die kontinuierlichen Variablen möglich.
Szenario-basierte Routenplanung zur Absicherung von Automotive Fahrfunktionen (TSP)
Der Demonstrator zeigt die im Rahmen des Projekts entstandene QAOA-Implementierung für das »Traveling Salesperson Problem«. Außerdem wird ein im Laufe des Projekts entwickelter Algorithmus zur Partitionierung des TSP demonstriert. Der auf A* basierende Algorithmus zerteilt große TSP-Instanzen in mehrere kleinere auf, sodass sie auf dem Quantenrechner gelöst werden können. Dieser Ansatz ist hybrid, wonach die Aufteilung auf einem klassischen Rechner stattfindet und nur der schwierige kombinatorische »Kern« des Problems auf dem Quantenrechner gelöst wird. In diesen Algorithmus eingebettet ist unsere QAOA-Implementierung, die auch wahlweise mit einem klassischen Lösungsverfahren zum Vergleich ausgetauscht werden kann. Um unsere Methode bei der Auswahl der zu generierenden kleinen Instanzen zu führen, wurden verschiedene Heuristiken entwickelt. Dazu gehört insbesondere ein kleines neuronales Netz, das die erwartete Länge einer TSP-Instanz abschätzen kann.
Optimierung von Ladeplänen einer gegebenen Ladesäuleninfrastruktur (EMP)
In diesem Demonstrator zeigen wir anhand von vier Jupyter Notebooks, wie man einen Energie-Anwendungsfall auf einem Quantencomputer lösen kann. Im ersten Notebook stellen wir den Anwendungsfall vor, zeigen wie er als ein mathematisches Optimierungsproblem formuliert werden kann und leiten eine Python-Implementierung her. Im zweiten Notebook erklären wir anhand des Energie-Anwendungsfalls sowohl die Theorie des Quantenalgorithmus QAOA als auch dessen Implementierung in Qiskit. Im dritten Notebook implementieren wir eine Transpilations-Pipeline, mit der QAOA-Schaltkreise auf realen IBM Quantencomputern ausgeführt werden können. Außerdem erklären wir, wie die Resultate eines Quantencomputers mit einem Big-Data-Bibliothek verarbeitet werden können. Im letzten Notebook präsentieren und diskutieren wir eine Reihe von Experimenten, welche auf dem IBM Quantum System One in Ehningen (»ibmq_ehningen«) ausgeführt wurden.
Im weiteren Projektverlauf liegt der Fokus auf der Ausführung von Anwendungsszenarien auf realen Quantencomputern, insbesondere auf dem IBM Quantum System One in Ehningen. Dazu stellen wir systematische Reihen von Probleminstanzen verschiedener Größen und
Kopplungsstärken (d. h. von verschiedenen Schwierigkeitsgraden) zur Verfügung und zeigen ihre Umsetzung – vom klassischen Modell bis zum
Postprocessing der Quantencomputing-Lösung (End-to-End Durchlauf). Der Demonstrator wird zum Projektabschluss im Frühjahr 2024 auf dieser
Seite veröffentlicht.
Optimale Auslegung von Schnittmustern in der Blechfertigung (BPP)
Das unregelmäßige Packproblem auf einem Streifen in 2D beschäftigt sich mit dem Finden von Position und Orientierung von einer Menge Polygonen auf einer rechteckigen Fläche mit bekannter und fester Höhe und variabler Länge, sodass alle Teile komplett in die Fläche passen, keine Teile überlappen und die Länge der Fläche minimal ist. Dieses Problem ist von erheblicher wirtschaftlicher Bedeutung, da es der verarbeitenden Industrie erlaubt, ihre Kosten für Materialien wie Stoff, Leder, Karton, Holz, Kunststoff, Glas, Keramik oder Metall zu minimieren, die für die Herstellung von Einzelteilen verwendet werden, aus denen sich Endprodukte zusammensetzen, wie z. B. Kleidung, Autos, Schiffe, Elektrogeräte, Maschinen und Verpackungen. Das Problem ist auch von großer ökologischer Bedeutung, da es die Einsparung knapper Ressourcen ermöglicht und zur Abfallvermeidung beiträgt.
Unsere Lösung ist ein hybrider quantenklassischer Algorithmus, der das Problem in ein Rechteckpackproblem und Instanzen des Traveling Salesman Problem (TSP) zerlegt. Das TSP wird mit dem Quantum Approximate Optimization Algorithm (QAOA) gelöst, der auf dem IBM Quantum System One in Ehningen, Deutschland ausgeführt wird. Unsere Lösung erlaubt eine beliebige Anzahl von Orientierungen,
skaliert bis zu hundert Teilen und ist in der Lage, eine spezielle Klasse von »puzzleartigen« Problemen optimal zu lösen.
Zero-Noise-Extrapolation (ZNE)
Die Idee der rauschfreien Extrapolation (englisch: Zero-Noise Extrapolation, kurz: ZNE) beruht auf der Annahme, dass es möglich ist, die Stärke des Rauschens in einem Quantenschaltkreis zu erhöhen, z. B. durch das Einfügen zusätzlicher Gatter. Wird die Stärke des Rauschens mehrmals verändert (einfache, dreifache, fünffache Fehlerstärke) kann im Anschluss ein Fit durch die gemessenen Punkte durchgeführt werden. Dadurch wird zum fehlerfreien Fall extrapoliert.
Da die Hauptfehler von fehlerbehafteten CNOT-Gattern herrühren, besteht die einfachste Methode darin, jedes CNOT-Gatter durch 3 (oder auch 5) CNOT-Gatter zu ersetzen und den Fehler somit um das 3- (oder 5-) fache zu verstärken. Im fehlerfreien Fall würde dies den Schaltkreis nicht verändern.
Die im Projekt entwickelte Python-Bibliothek kommt bei allen Algorithmen zur Anwendung, in denen Erwartungswerte berechnet werden. Im Beispiel Jupyter Notebook demonstrieren wir die Anwendung der ZNE für den HHL-Algorithmus mit 4 Qubits. Dieser Algorithmus löst ein zweidimensionales, lineares Gleichungssystem. Die uns interessierende Funktion 𝐹 ist die Norm der entsprechenden Lösung.
Error Mitigation Service
Der »Error Mitigation Service« wurde im Rahmen des SEQUOIA-Projekts entwickelt und kann dazu verwendet werden, die Auswirkungen von Fehlern in verrauschten Messergebnissen eines Quantencomputers zu reduzieren. Er ist als Open-Source-Projekt auf GitHub verfügbar. Dieser Dienst ermöglicht die Erstellung und Verwaltung von Kalibrierungs- und Mitigationsdaten für diverse QPU-Anbieter. Darüber hinaus ermöglicht er den Nutzenden, ihre Ausführungsergebnisse auf der Grundlage neu generierter oder bereits vorhandener Mitigationsdaten zu verbessern. Der Error Mitigation Service implementiert derzeit verschiedene Methoden, wie Mthree oder TPNM für IBMQ und IonQ. Außerdem unterstützt er die Fehlermitigation für Ergebnisse, die auf Quantensimulatoren mit emuliertem Rauschen erzielt wurden. Nutzende können zwischen vollständigen Rauschmodellen und Rauschmodellen, die nur Auslesefehler enthalten, wählen.
Optimierung einer Auftragssequenzierung in der diskreten Fertigung (JSP)
In diesem Demonstrator zeigen wir in Form eines Jupyter Notebooks, wie man den Anwendungsfall des Job Shop Scheduling (JSP) auf einem Quantencomputer lösen kann. In dem Notebook stellen wir den Anwendungsfall vor, zeigen, wie er in ein mathematisches Optimierungsproblem (time-indexed-JSP-QUBO) formuliert werden kann, und erklären, wie dieses Problem in Python implementiert werden kann.
Nachdem wir das QUBO mit einem klassischen Optimierer (CPLEX) gelöst haben, zeigen wir, wie das QUBO in ein Ising-Modell umgewandelt werden kann, das dann auf einem Quantencomputer (ibmq_ehningen) mit dem Quantum Approximate Optimization Algorithm (QAOA) gelöst wird. Abschließend analysieren wir die Shot-Samples des Algorithmus.
Routenplanung von LKW-Flotten im Supply-Chain-Management (TSP / SPP)
In diesem Demonstrator zeigen wir wie ein Vehicle Routing Problem (VRP) auf dem Quantencomputer gelöst werden kann. Ein VRP ist ein verallgemeinertes Traveling-Salesperson-Problem (TSP), bei dem eine Rundreise auf mehrere Agenten (Lastwagen) aufgeteilt werden muss. Das Jupyter Notebook erklärt zunächst wie ein VRP als sogenanntes Quadratic Unbounded Binary Optimization (QUBO) Problem aufgefasst werden kann und weiter wie man dieses für den Quantencomputer codieren kann.
An Beispielen wird deutlich gemacht, wie viele Qubits zur Lösung der Probleme jeweils notwendig sind. Abschließend besteht die Möglichkeit für ein einzelnes Beispiel interaktiv den QAOA-Algorithmus (als Simulation) auszuführen und dabei Optimierungsparameter und die Schaltkreistiefe zu verändern.
In der zweiten Projektphase haben wir im Hinblick auf TSP die DWave-Hardware systematisch untersucht, um eine bessere Leistung zu erzielen. Wir betrachteten die asymmetrische und symmetrische Verteilung der Städte, um herauszufinden, ob die Symmetrie bei der Ermittlung der korrekten Lösung hilft und fanden heraus, dass dies tatsächlich der Fall ist. Die Berechnungen führen wir in der zweiten
Projektphase mit dem VQE-Algorithmus anstatt mit QAOA durch. Dieser wurde für ein einzelnes Beispiel interaktiv (als Simulation) ausgeführt,
wobei die Optimierungsparameter und die Schaltkreistiefe verändert wurden. Der Demonstrator wird zum Projektabschluss im Frühjahr 2024
auf dieser Seite veröffentlicht.
Computergestützte Strömungsdynamik (VQLS)
In diesem Demonstrator zeigen wir, wie partielle Differentialgleichungen auf einem Quantencomputer mit linearen Gleichungssystemen gelöst werden können. Der Demonstrator besteht aus drei Jupyter Notebooks. Im ersten Notebook wird die Theorie zur Umwandlung partieller Differentialgleichungen in lineare Gleichungssysteme unter Nutzung von Finite-Differenzmethoden zusammen mit einem interaktiven Code zur Lösung der Gleichungen vorgestellt. Der Quantenalgorithmus VQLS steht im Mittelpunkt des zweiten und dritten Notebooks. Im zweiten Notebook werden die Theorie und die Implementierung der globalen Kostenfunktion besprochen, der Code erklärt und die Ergebnisse anhand eines einfachen Beispiels veranschaulicht. Im dritten Notebook werden anhand eines weiteren anschaulichen Beispiels die Theorie und Implementierung lokaler Kostenfunktionen besprochen.
Quantum Application Lifecycle Management (QuAntiL): Modularisierte Schnittstellen-Architektur zur workflow-basierten Ausführung von Quantensoftware
Diese Arbeiten sind in enger Kooperation mit dem PlanQK-Projekt entstanden.
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.