[Diese Seite ist derzeit noch in Bearbeitung und wird nach und nach ergänzt.]
ProvideQ war ein Verbundvorhaben zur Erforschung und praktischen Erprobung von Quanten- und hybriden Algorithmen für wirtschaftlich relevante Optimierungsprobleme. Das Projekt wurde vom 01.01.2022 bis 31.03.2025 vom BMWE (ehemals BMWK) gefördert, wobei die Technische Universität Braunschweig als Konsortialführer das Projekt geleitet hat.
Ziel von ProvideQ war es, die Potenziale und Grenzen von Quantencomputing für wirtschaftlich relevante Optimierungsprobleme systematisch zu untersuchen und praxisnahe Einsatzmöglichkeiten für die deutsche Wirtschaft zu erschließen. Dabei lag der Fokus auf der Entwicklung, Integration und Bewertung quantenbasierter und hybrider Algorithmen für konkrete industrielle Anwendungsfelder – insbesondere in den Bereichen Logistik und Produktion. Die Ergebnisse der theoretischen Arbeit wurden in eine offene Softwareplattform, der ProvideQ Toolbox, implementiert. Unter dem Leitmotiv "Enable the Enablers" konnten durch die direkte Zusammenarbeit mit führenden Dienstleistern die Ergebnisse breit zugänglich gemacht werden.
Das Karlsruher Institut für Technologie stellt eine öffentlich zugängliche Version der ProvideQ Toolbox zur Verfügung.
Eines der zentralen Ergebnisse von ProvideQ war die Entwicklung der ProvideQ Toolbox als modulare Integrationsplattform für klassische, quantenbasierte und hybride Optimierungsverfahren. Ziel dieser Toolbox war es, eine flexible Plattform bereitzustellen, auf der unterschiedliche algorithmische Ansätze systematisch kombiniert und getestet werden können – unterstützt durch einen Plug-and-Play-Ansatz, der es ermöglicht, Solver, Algorithmen und Subroutinen unkompliziert miteinander zu verknüpfen.
Kernbestandteil der Toolbox war eine Meta-Solver-Logik, die Optimierungsprobleme als Zusammenspiel verschiedener Teilprobleme versteht. Abhängig von Problemstruktur, Modellierung und Lösungsanforderungen können klassische Solver, quantenbasierte Subroutinen oder hybride Verfahren orchestriert werden. Dieser polylithische Ansatz erlaubte die Kombination von klassischen Optimierungsverfahren und experimentellen Quantenverfahren. Insbesondere wurde mit Hybrid-Meta-Solving ein hybrider Ansatz entwickelt, mit welchem sich erfolgreich ein Problem in Teilprobleme aufteilen ließ, die anschließend entsprechend von den entwickelten algorithmischen Ansätzen bearbeitet wurden. Meta-Solver-Strategien haben sich als geeignetes konzeptionelles Werkzeug erwiesen, um Quantenalgorithmen realistisch in bestehende Optimierungsworkflows einzuordnen.
Ausgangspunkt für ProvideQ bildeten drei praxisrelevante Use Cases aus der Logistik und Produktionsplanung, anhand derer die Leistungsfähigkeit der entwickelten Quanten- und hybriden Algorithmen mit traditionellen Lösungsverfahren bewertet werden sollte. Die betrachteten Szenarien umfassten Load Building, das Vehicle Routing Problem sowie Production Planning. Diese Anwendungsfälle wurden zunächst formalisiert und mit realitätsnahen Datensätzen hinterlegt. Im Projektverlauf zeigte sich jedoch, dass die direkte Anwendung quantenbasierter und hybrider Lösungsansätze auf diese komplexen Problemstellungen aufgrund der aktuellen Grenzen von Quantenhardware und Algorithmen mit erheblichen Herausforderungen verbunden ist.
Um dennoch eine fundierte Bewertung der entwickelten Verfahren zu ermöglichen, wurden Kernprobleme identifiziert, die zentrale strukturelle Eigenschaften der Use Cases widerspiegeln. Beim Load Building wurde der Fokus auf Varianten des Knapsack-Problems verlagert, für das Vehicle Routing Problem erfolgte eine Abstraktion auf das Traveling Salesman Problem und im Bereich der Produktionsplanung wurde Job-Shop Scheduling als repräsentatives Basisproblem betrachtet. Diese Kernprobleme erlaubten es, standardisierte Benchmark-Instanzen zu nutzen und klassische sowie quantenbasierte Verfahren unter kontrollierten Bedingungen systematisch miteinander zu vergleichen.
Für ganzzahlige Optimierungsprobleme wurden in ProvideQ verschiedene quantenbasierte und hybride Ansätze entwickelt und untersucht. Ein zentrales Ergebnis war die Entwicklung der Quantum Tree Generation (QTG), die insbesondere für Varianten des bekannten 0-1-Knapsack-Problems vielversprechende Resultate lieferte und zeigte, dass bestimmte kombinatorische Teilprobleme prinzipiell von Quantenbeschleunigung profitieren können.
Zusätzlich wurde der Quantum-Simplex-Algorithmus intensiv untersucht, um daraus eine realistische Einschätzung der Konkurrenzfähigkeit von Quantenalgorithmen für ganzzahlige Optimierungsprobleme abzuleiten. Das im Kontext von ProvideQ veröffentlichte Paper zum besagten Algorithmus konnte herausarbeiten, dass die Performance von Quanten-Ansätzen durch fundamentale, strukturelle Gegebenheiten begrenzt wird und daher auch im Falle von erheblichem Fortschritt der Quantenhardware hinter ausgefeilten konventionellen Algorithmen zurückbleiben wird. Gleichzeitig liefert der Quantum-Simplex-Algorithmus eine methodische Grundlage, um zukünftige Quantenalgorithmen systematisch zu bewerten und in bestehende Optimierungsworkflows einzuordnen.
Insgesamt verdeutlichten die Ergebnisse, dass ganzzahlige Optimierung aufgrund ihrer diskreten Struktur besondere Herausforderungen für Quantencomputing darstellt. Während ausgewählte Teilprobleme quantenmechanisch adressierbar sind, bleiben dennoch Einschränkungen bezüglich der Skalierbarkeit, weshalb klassische Verfahren in realistischen Szenarien weiterhin überlegen sind. Dennoch konnten Einsichten gewonnen werden, wie klassische und quantenbasierte Verfahren sinnvoll kombiniert werden können.
Für konvexe Optimierungsprobleme wurden in ProvideQ hybride algorithmische Verfahren entwickelt. Ein zentrales Konzept war dabei der Hamiltonian-Updates-Algorithmus, der iterativ Lösungsvorschläge erstellt und dabei klassische Verfahren und experimentelle Quantenmethoden miteinander kombiniert. Zusätzlich wurde ein Benchmarking Framework entwickelt, welches den klassischen und quantenbasierten Hamiltonian-Updates-Algorithmus auf den in ProvideQ definierten Use Cases gegenüberstellte.
Die Ergebnisse zeigen, dass klassische Ansätze für praktisch relevante Problemgrößen zurzeit überlegen sind, während Quantenverfahren bisher vor allem theoretisches Potenzial liefern. Grund für die Dominanz der klassischen Verfahren sind vor allem die Einschränkungen von Quantenhardware und die Komplexität der Übersetzung realer Probleme in quantenkompatible Formate.
Für Optimierungsprobleme unter Unsicherheit wurden in ProvideQ quantengestützte Verfahren mit speziellem Fokus auf die Optimierung in Netzwerken und die Produktionsplanung entwickelt.
Ein zentrales Ergebnis war die Entwicklung polyedrischer Modelle zur systematischen Ausdünnung stochastischer Abhängigkeiten. Diese Modelle ermöglichen es, große Abhängigkeitsgraphen durch geeignete strukturelle Eigenschaften deutlich zu vereinfachen. Im Vergleich zu bestehenden Ansätzen zeigte sich dieser Ansatz wesentlich effizienter und erlaubte eine kompakte Darstellung robuster Optimierungsprobleme. Insbesondere die Identifikation geeigneter polyedrischer Strukturen stelle sich als entscheidend heraus, um die Komplexität solcher Probleme zu reduzieren.
Ein weiterer Beitrag war die Entwicklung des Multi-Objective Quantum Approximate Optimization Algorithmus (MOQA). Dieser Ansatz erweitert bestehende Quantenoptimierungsverfahren dahingehend, mehrere konkurrierende Zielgrößen innerhalb eines gemeinsamen Optimierungsrahmens zu berücksichtigen. Im Gegensatz zu bisherigen heuristischen Verfahren konnte MOQA mit theoretisch fundierten Approximationsgarantien untermauert werden und eröffnet somit neue Perspektiven für die quantenbasierte Behandlung binärer Optimierungsprobleme.
Ziel dieses Arbeitspaketes war die Sicherstellung und Bewertung des praktischen Nutzens, der durch Quantencomputing erzeugten Lösungen für logistische Optimierungsprobleme. Dazu wurden vorab drei relevante Use Cases identifiziert, die aus verschiedenen Domänen der praktischen Logistik stammen.
Ziel dieses Arbeitspaketes war es, eine modulare und erweiterbare Softwarearchitektur für die ProvideQ Toolbox zu entwerfen, die klassische Optimierungsverfahren und hybride Quantenalgorithmen in einem einheitlichen System integriert. Die Architektur sollte unterschiedliche Modellierungssysteme, Quanten-SDKs, Hardwareplattformen und klassische Solver verbinden und so flexible Lösungsstrategien ermöglichen.
Ziel dieses Arbeitspaketes war die Entwicklung polylithischer Meta-Solver, die klassische Optimierungsverfahren systematisch mit quantenbasierten Subroutinen verbinden. Diese Meta-Solver sollten hybride Lösungsstrategien steuern, indem sie festlegen, an welchen Stellen eines klassischen Algorithmus Quantenalgorithmen eingesetzt werden. Durch die Erweiterung des polylithischen Ansatzes in GAMS sollte eine flexible, wiederverwendbare und korrekt überprüfbare Einbindung von Quantenalgorithmen in industrielle Optimierungsworkflows ermöglicht werden.
In diesem Arbeitspaket ging es darum, ganzzahlige Optimierungsprobleme aus industriellen Anwendungsfällen um Quantenheuristiken und Quantenalgorithmen als Unterprogramme zu ihrer Lösung zu erweitern. Hierfür waren drei Ansätze vorgesehen: Formulierung des Problems als Suchproblem zur Nutzung von Quantensuchalgorithmen, Relaxierung mittels konvexer Methoden für lineare Quantenalgebra und Einsatz von Quantenoptimierungsheuristiken für eingeschränkte Teilprobleme.
Analog zu AP4 hatte dieses Arbeitspaket das Ziel, konvexe Optimierungsprobleme aus industriellen Anwendungen zu adressieren und deren Lösung durch Quantenalgorithmen und Quantenheuristiken zu untersuchen. Dazu sollten zum einen konkrete konvexe Optimierungsprobleme, welche aus der Relaxierung von nicht-konvexen kombinatorischen Anwendungsfällen hervorgehen, näher betrachtet werden und bereits existierende quantenalgorithmische Ansätze so aufbereitet werden, sodass dieses in die ProvideQ Toolbox integriert werden können.
In diesem Arbeitspaket sollte ein neues Verfahren entwickelt werden, um Unsicherheit in Netzwerken mit Störungen in der Optimierung von Logistikproblemen zu berücksichtigen. Kern war eine Ausdünnung des sehr großen Abhängigkeitsgraphen durch einen Quantenalgorithmus.
Dieses Arbeitspaket hatte das Ziel, die effektive Zusammenarbeit innerhalb des ProvideQ-Verbunds zu gewährleisten und die Projektergebnisse erfolgreich nach außen zu vermitteln.
Die Technische Universität Braunschweig übernahm mit Prof. Dr. Sándor Fekete die Konsortialführung des Projekts und trug die inhaltliche Gesamtverantwortung für die Entwicklung der mathematischen und algorithmischen Grundlagen der Toolbox. Am Institut für Algorithmik lag der Schwerpunkt auf der inhaltlichen Integration der mathematischen Methoden, der Entwicklung polylithischer Meta-Solver-Strategien, sowie von Verfahren zur ganzzahligen Optimierung. Prof. Dr. Fekete leitete die Koordination des Projektverbunds und die Dissemination der Ergebnisse. Das Institut für Mathematische Optimierung unter der Leitung von Prof. Dr. Sebastian Stiller arbeitete an hybriden Quantenalgorithmen für Optimierungsprobleme unter Unsicherheit, während das Institut für Analysis und Algebra unter Leitung von Prof. Dr. Timo de Wolff hybride Quantenalgorithmen für konvexe Optimierungsprobleme entwickelte.
Das Karlsruher Institut für Technologie verantwortete im Projekt ProvideQ den Architekturentwurf, die Implementierung sowie die Qualitätssicherung der ProvideQ Toolbox. Unter der Leitung von Prof. Dr. Ina Schaefer wirkte das KIT koordinierend zwischen den Projektpartnern und stellte sicher, dass die in den drei Problemfeldern entwickelten Methoden konsistent, wartbar und industriell nutzbar in die Toolbox integriert wurden.
Die Universität zu Köln brachte ihre Expertise in der Quanteninformationstheorie und konvexen Optimierung in das Projekt ein. Prof. Dr. David Gross war verantwortlich für die Analyse und Entwicklung hybrider Quantenalgorithmen für konvexe Optimierungsprobleme, insbesondere unter Nutzung quantenbasierter Subroutinen für Teilprobleme. Die Arbeiten erfolgten in enger Zusammenarbeit mit der TU Braunschweig und der Johannes Kepler Universität Linz.
Die Leibniz Universität Hannover beteiligte sich mit ihrer ausgewiesenen Expertise im Design von Quantenalgorithmen an ProvideQ. Prof. Dr. Tobias J. Osborne war für die Entwicklung hybrider Quantenalgorithmen für ganzzahlige Optimierungsprobleme verantwortlich. Dabei arbeitete er eng mit der Technischen Universität Braunschweig und der Johannes Kepler Universität Linz zusammen.
Die 4flow AG war verantwortlich für die Datenerhebung, Aufbereitung und mathematische Formulierung realer logistischer Optimierungsprobleme sowie für die Ableitung wirtschaftlicher Anforderungen an die ProvideQ Toolbox. Darüber hinaus evaluierte 4flow die entwickelten Quantenverfahren und die Toolbox hinsichtlich ihrer wirtschaftlichen Anwendbarkeit.
Der Schwerpunkt der GAMS Software GmbH lag auf der Entwicklung polylithischer Meta-Solver-Strategien als logischem Kernstück der ProvideQ Toolbox. Auf Basis der in den drei Problemfeldern entwickelten Quantenalgorithmen wurden diese Strategien abgeleitet, evaluiert und validiert.
Die Johannes Kepler Universität Linz unterstützte das Projekt ProvideQ als Unterauftragnehmer unter der Technischen Universität Braunschweig im Bereich des Quantum Computing sowie der konvexen Optimierung. Unter der Leitung von Assistenzprofessor Dr. Richard Küng wirkte die Johannes Kepler Universität Linz maßgeblich an der Entwicklung und wissenschaftlichen Bewertung hybrider und quantengestützter Methoden für verschiedene Optimierungsklassen mit.
Prof. Dr. Sándor P. Fekete
Abteilung Algorithmik
Technische Universität Braunschweig
Mühlenpfordtstraße 23
38106 Braunschweig
Telefon: +49 (0)531 391 311 1
Telefax: +49 (0)531 391 310 9
E-Mail: s.fekete[[at]]tu-bs.de
Internet: Webseite Prof. Dr. Fekete bei der TU Braunschweig
Dr. Christian Rieck
Diskrete Mathematik
Universität Kassel
Heinrich-Plett-Str. 40
34132 Kassel
Telefon: +49 561 804-4192
E-Mail: christian.rieck[[at]]mathematik.uni-kassel.de
Internet: Webseite Dr. Rieck bei der Universität Kassel
Tobias Wallner
Abteilung Algorithmik
Technische Universität Braunschweig
Mühlenpfordtstraße 23
38106 Braunschweig
Telefon: +49 (0)531 391 311 6
E-Mail: wallner[[at]]ibr.cs.tu-bs.de
Internet: Webseite Wallner bei der TU Braunschweig