[Diese Seite ist derzeit noch in Bearbeitung und wird nach und nach ergänzt.]
QuBRA war ein Verbundvorhaben zur Erforschung und systematischen Bewertung von Quanten- und klassischen Algorithmen für kombinatorische Optimierungsprobleme aus der Wirtschaft, insbesondere in den Bereichen Produktion, Konfiguration und Logistik. Das Projekt wurde vom 01.01.2022 bis 30.06.2025 im Rahmen der Förderinitiative „Anwendungsnetzwerk für das Quantencomputing“ und unter der Leitung von der Leibniz Universität Hannover durch das BMFTR (ehemals BMBF) gefördert, wobei die Technische Universität Braunschweig als Verbundpartner am Projekt mitwirkte.
Die Erwartungen an die Leistungsfähigkeiten von Quantencomputern legen nahe, dass Quantenalgorithmen in Zukunft für das Lösen kombinatorischer Optimierungsprobleme eingesetzt werden können. In der Praxis ist diese Entscheidung jedoch von mehreren Faktoren abhängig, wie den Fähigkeiten von Quanten-Hardware, den strukturellen Feinheiten von Problemmodellierungen und der Leistungsfähigkeit konkurrierender klassischer Lösungsansätze. Demnach war das Ziel von QuBRA das Potenzial und die Grenzen von Quantencomputing für praxisrelevante kombinatorische Optimierungsprobleme umfänglich zu untersuchen und eine belastbare Grundlage für die Bewertung quantenbasierter Algorithmen zu schaffen. Dabei brachte QuBRA ein interdisziplinäres Konsortium aus den Bereichen Quanteninformation, klassische Algorithmik, maschinelles Lernen und Software Engineering zusammen, um verschiedene determistische und quantenbasierte algorithmische Ansätze zu entwickeln, zu implementieren und systematisch miteinander zu vergleichen.
Die Technische Universität Braunschweig war als Verbundpartner insbesondere an der Entwicklung und Implementierung klassischer, deterministischer Lösungsverfahren sowie am Aufbau von Benchmark-Instanzen und Vergleichsmethoden beteiligt.
Im Rahmen von QuBRA wurden an der Technischen Universität Braunschweig bedeutende Fortschritte bei der Entwicklung klassischer Optimierungsverfahren für Konfigurationsprobleme erzielt. Insbesondere wurde mit dem Algorithmus SampLNS von Krupke et al. ein Ansatz entwickelt, der bessere Lösungen berechnen kann als bisherige Verfahren und gleichzeitig mathematisch fundierte untere Schranken für die minimal erforderliche Lösungsgröße bestimmt. Dadurch wurde erstmals eine zuverlässige Bewertung der Lösungsqualität möglich, und in vielen Fällen konnte sogar nachgewiesen werden, dass die berechneten Lösungen optimal sind.
Diese Ergebnisse wurden in der Veröffentlichung „How Low Can We Go? Minimizing Interaction Samples for Configurable Systems“ dokumentiert. Die dort vorgestellten Ergebnisse konnten zeigen, dass klassische Optimierungsverfahren weiterhin ein erhebliches Potenzial zur effizienten Lösung komplexer Optimierungsprobleme besitzen.
Im Rahmen des Projekts wurden zudem Ergebnisse für Optimierungsprobleme im Kontext von Supply Chain Management und Produktionsplanung erzielt. Hierbei entwickelte die Technische Universität Braunschweig sowohl klassische als auch quantenbasierte Lösungsverfahren zur Untersuchung und Lösung kombinatorischer Optimierungsprobleme.
Darüber hinaus wurden bestehende quanteninspirierte Ansätze zur Strukturierung kombinatorischer Suchräume weiterentwickelt und auf verschiedene Varianten des Knapsack-Problems übertragen. Hierzu zählt insbesondere der Quantum Tree Generator, der auf das Knapsack-Problem angewandt und später auf das quadratische sowie das mehrdimensionale Knapsack-Problem erweitert wurde. Nähere Informationen zu diesem Ansatz sowie zu den im Kontext des Knapsack-Problems entwickelten Methoden sind auf der Projektseite von ProvideQ verfügbar.
Die im Rahmen des Projekts erzielten Ergebnisse zeigen, dass klassische Optimierungsverfahren für viele praxisrelevante kombinatorische Optimierungsprobleme derzeit weiterhin eine deutlich höhere Leistungsfähigkeit als quantenbasierte Ansätze aufweisen. Ihr praktischer Einsatz wird dabei maßgeblich durch die derzeit begrenzte Leistungsfähigkeit verfügbarer Quanten-Hardware eingeschränkt.
Vor diesem Hintergrund ist kurzfristig keine direkte, marktfähige wirtschaftliche Nutzung quantenbasierter Optimierungsverfahren zu erwarten. Eine breitere praktische Anwendung quantenbasierter Algorithmen erscheint erst mit zukünftigen technologischen Fortschritten realistisch und ist insbesondere von weiteren Entwicklungen der Quanten-Hardware abhängig. Die im Projekt entwickelten Methoden, Benchmark-Instanzen und Analyseverfahren leisten jedoch einen wichtigen Beitrag zur systematischen Bewertung quantenbasierter Optimierungsansätze und bilden eine belastbare Grundlage für zukünftige Forschungsarbeiten und mögliche Anwendungen mit zunehmender technologischer Reife.
Ziel dieses Arbeitspakets war die Entwicklung eines Benchmarking-Frameworks zur systematischen und reproduzierbaren Bewertung der entwickelten algorithmischen Ansätze. Hierzu wurde ein repräsentatives Benchmark-Set erstellt, um die klassischen, maschinellen und quantenbasierten Verfahren miteinander zu vergleichen.
Diese Arbeitspakete befassten sich mit der Untersuchung mehrerer industriell motivierter Optimierungsprobleme, namentlich dem Konfigurationsproblem, Job-Shop-Scheduling, Supply Chain Management, Flottenmanagement und dem Pickup-and-Delivery im IoT und hatten zum Ziel, die Leistungsfähigkeit der unterschiedlichen algorithmischen Ansätze zu bewerten und insbesondere zu untersuchen, unter welchen Bedingungen quantenbasierte Verfahren einen potenziellen Vorteil gegenüber klassischen Methoden bieten können. Als Lösungsansätze für die jeweiligen Use-Cases wurden sowohl deterministische Algorithmen und Maschinenlernenmethoden als auch Quantenalgorithmen entwickelt.
Dieses Arbeitspaket befasste sich mit der Entwicklung von Methoden und Werkzeugen zur strukturierten Entwicklung von Quantensoftware. Dazu gehörten insbesondere die Identifikation wiederverwendbarer algorithmischer Konzepte, die Entwicklung einer Standardbibliothek sowie die Erforschung geeigneter Methoden zur Gewährleistung der Korrektheit und Zuverlässigkeit quantenbasierter Programme.
Dieses Arbeitspaket umfasste die organisatorische Koordination des Projektverbunds sowie die Dokumentation und Verbreitung der Projektergebnisse.
Die Leibniz Universität Hannover war unter der Leitung von Prof. Dr. Tobias J. Osborne vom Institut für Theoretische Physik und Dr. Avishek Anand als Konsortialführer für die Koordination des Projektverbunds QuBRA verantwortlich. Die Leibniz Universität Hannover war an der wissenschaftlichen Durchführung des Projekts beteiligt und brachte ihre Expertise im Bereich Quantenalgorithmen und kombinatorischer Optimierung ein.
Die Technische Universität Braunschweig war unter der Leitung von Prof. Dr. Sándor P. Fekete der von Abteilung Algorithmik am Institut für Betriebssysteme und Rechnerverbund und Prof. Dr. Ina Schaefer (damals Institut für Softwaretechnik und Fahrzeuginformatik) als Verbundpartner an QuBRA beteiligt. Die Arbeiten der Abteilung Algorithmik umfassten insbesondere die Entwicklung und Bewertung klassischer Optimierungsverfahren sowie die Bereitstellung von Benchmark-Instanzen und Vergleichsmethoden. Darüber hinaus wirkte das Institut für Softwaretechnik und Fahrzeuginformatik an der Implementierung quantenalgorithmischer Methoden mit und beteiligte sich bei der Entwicklung von Methoden und Werkzeugen zur Entwicklung von Quantensoftware.
Die Universität zu Köln war unter der Leitung von Prof. Dr. David Gross vom Institut für Theoretische Physik als Verbundpartner an QuBRA beteiligt. Seine Forschungsschwerpunkte liegen im Bereich der Quanteninformationstheorie, mitunter der Analyse, Charakterisierung und Simulation von Quantensystemen, sowie der Entwicklung mathematischer Methoden für Quantencomputer.
Die Ruhr-Universität Bochum war unter der Leitung von Prof. Dr. Michael Walter (damals an der Fakultät für Informatik) als Verbundpartner an QuBRA beteiligt. Seine Forschungsschwerpunkte liegen im Bereich der Quantenalgorithmik und Quantensoftware sowie in der Entwicklung innovativer Optimierungsalgorithmen für klassische und Quantencomputer.
Die Infineon Technologies AG ist ein weltweit tätiger Halbleiterhersteller mit Hauptsitz in Deutschland und entwickelt elektronische Systeme und Komponenten für Anwendungen in den Bereichen Automobilindustrie, Energiemanagement und digitale Sicherheit. Im Rahmen von QuBRA brachte Infineon industrielle Anwendungsfälle und Anforderungen aus der Halbleiterproduktion und Produktionsplanung in das Projekt ein.
Die Volkswagen AG ist einer der weltweit führenden Automobilhersteller mit Hauptsitz in Wolfsburg und entwickelt Fahrzeuge sowie Mobilitätslösungen für internationale Märkte. Im Rahmen von QuBRA brachte Volkswagen industrielle Anwendungsfälle aus den Bereichen Fahrzeugkonfiguration und Flottenmanagement in das Projekt ein.
Prof. Dr. Tobias J. Osborne
Institut für Theoretische Physik
Leibniz Universität Hannover
Schneiderberg 32
30167 Hannover
Telefon: +49 (0)511 762 17502
E-Mail: tobias.osborne@itp.uni-hannover.de
Internet: Website Prof. Dr. Tobias J. Osborne bei der LUH
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@tu-bs.de
Internet: Webseite Prof. Dr. Fekete bei der TU Braunschweig
Prof. Dr.-Ing. Ina Schaefer
Institut für Informationssicherheit und Verlässlichkeit
Karlsruher Institut für Technologie
Am Fasanengarten 5
76131 Karlsruhe
Telefon: +49 (0)721 9654-609
E-Mail: ina.schaefer@kit.edu
Internet: Webseite Prof. Dr.-Ing. Ina Schaefer am KIT