Konzeption und Implementierung der Eingabe von Constraints und Umsetzung von QUBO-Formulierungen mit Constraints im Rahmen eines Quantum Computing Advisers
Typ: Masterarbeit
Betreuer: Markus Zajac
Beschreibung:
Die Verfügbarkeit von Quantenannealern über geeignete Quantencomputing-Clouddienste bietet Unternehmen neue Möglichkeiten, eine Vielzahl an Optimierungsproblemen [1] zu berechnen. Die Auswahl geeigneter Quantenannealer ist aufgrund ihrer technischen Eigenschaften für Nicht-Experten jedoch schwierig. Aus dieser Motivation heraus wurde im Rahmen einer Abschlussarbeit an der FernUniversität in Hagen die Software QC-Adviser entwickelt. Diese empfiehlt geeignete Quantenannealer für verschiedene Optimierungsprobleme, die in den Bereichen Routing Problems, Sequencing Problems und General Problems eingeordnet sind.
Viele Optimierungsprobleme lassen sich als Quadratic Unconstrained Binary Optimization (QUBO) Probleme formulieren. Diese Formulierungen bilden die Grundlage für den QC-Adviser, da Empfehlungen auf der Grundlage von QUBO-Formulierungen abgeleitet werden können. Des Weiteren enthalten Probleme häufig sogenannte Constraints, welche zwingend in die QUBO-Formulierungen aufgenommen werden müssen. Der QC-Adviser sieht die Nutzung der Constraints vor, berücksichtigt jedoch nur einige wenige. Zudem ist die Angabe einiger dieser Constraints für Benutzerinnen und Benutzer des QC-Advisers nicht immer verständlich.
Ziel der Masterarbeit besteht in der Weiterentwicklung des QC-Advisers um zusätzliche QUBO-Formulierungen, um diese bei der Ermittlung von Empfehlungen zu berücksichtigen. Dabei sollen unter Einbeziehung zusätzlicher Constraints neue QUBO-Formulierungen implementiert oder bestehende um diese erweitert werden. Als Eingrenzung sollen Probleme aus der Problemklasse Routing Problems mit ihren jeweiligen Constraints betrachtet werden [2, 3]. Ein weiteres damit verbundenes Ziel besteht in der Erstellung eines GUI-Konzepts zur benutzerfreundlichen und verständlichen Spezifikation von Constraints durch Benutzer und Benutzerinnen sowie seiner Implementierung im QC-Adviser.
Zur Erreichung dieses Ziels sollen die folgenden Aufgaben bearbeitet werden:
- Recherche von weiteren QUBO-Formulierungen samt zugehöriger Constraints für Routing Problems
- Erstellung eines GUI-Konzeptes zur problemspezifischen Eingabe von Constraints im QC-Adviser. Benutzer und Benutzerinnen müssen dabei verstehen, welche Constraints wie eingegeben werden können, sowie was diese grundsätzlich fachlich bewirken.
- Implementierung des GUI-Konzeptes für die Eingabe von Constraints
Implementierung neuer bzw. Erweiterung bestehender QUBO-Formulierungen anhand Rechercheergebnisse im QC-Adviser, so dass diese bei der Ermittlung von Empfehlungen berücksichtigt werden. Die Constraints für die QUBO-Formulierungen sollen aus den problemspezifischen Eingaben übernommen werden.
Voraussetzungen:
- Programmiererfahrung in Java
- Kenntnisse in Spring Boot sind von Vorteil
- Kenntnisse in Maven sind von Vorteil
- Kenntnisse in Vue.js sind von Vorteil
- Sie haben Grundkenntnisse im Quantum Annealing / QUBO-Formulierung bzw. bringen die Bereitschaft mit, sich in die für diese Arbeit notwendigen Grundlagen einzuarbeiten.
Referenzen
- Yarkoni, S., Raponi, E., Bäck, T. & Schmitt, S. (2022), ‘Quantum annealing for industry applications: Introduction and review’, Reports on Progress in Physics 85(10), 104001.
- Harikrishnakumar, R., Nannapaneni, S., Nguyen, N. H., Steck, J. E., & Behrman, E. C. (2020). A quantum annealing approach for dynamic multi-depot capacitated vehicle routing problem. arXiv preprint arXiv:2005.12478.
- Gonzalez-Bermejo, S., Alonso-Linaje, G., & Atchade-Adelomou, P. (2022). GPS: A new TSP formulation for its generalizations type QUBO. Mathematics, 10(3), 416.
