Quantenalgorithmen für Optimierung

• Antragsteller: Professor Dr. Sebastian Pokutta
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung seit 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 499407162

Computer und die damit eng verbundenen Technologien zur Informationsverarbeitung gehören zu den revolutionärsten Erfindungen des vergangenen Jahrhunderts. Eine weitere bahnbrechende Entdeckung des 20. Jahrhunderts war die Quantenmechanik. Entwickelt als theoretisches Modell zur Beschreibung der Physik auf atomarer Ebene, veränderte sie unser Verständnis der Welt um uns herum grundlegend. Das Gebiet der Quanteninformatik geht auf diese beiden Entdeckungen zurück. Sein Hauptziel ist es, zu verstehen, wie die Quantenmechanik unser Verständnis von Berechnung verändert, insbesondere die Unterscheidung zwischen machbaren und nicht machbaren Problemen. Jüngste Entwicklungen bei Quantenalgorithmen zeigen, dass verschiedene Optimierungsprobleme auf einem Quantencomputer viel schneller gelöst werden können. Optimierungsprobleme durchdringen unsere Gesellschaft, sie sind der Schlüssel für den effizienten Betrieb von Industrie, Logistik und für unzählige andere Aufgaben, die für das Funktionieren unserer modernen Gesellschaft entscheidend sind. Außerdem sind Optimierungsprobleme notorisch schwierig, und viele von ihnen präzise zu lösen, ist selbst für die leistungsstärksten modernen Computer unerreichbar, selbst für Instanzen von bescheidener Größe. Die Vision dieses Projektes ist es, den Einsatz von Quantencomputern für Optimierungsaufgaben viel weiter voranzutreiben und neue Quantenalgorithmen zu entwickeln, die weit über die Fähigkeiten selbst der besten klassischen Computer, die wir heute haben, hinausgehen. Wir streben sowohl allgemeine Algorithmen an, die für eine Vielzahl von Anwendungen eingesetzt werden können, als auch anwendungsspezifische Algorithmen. Wir betrachten sowohl kontinuierliche als auch diskrete Optimierung, Quantenalgorithmen für gemischt-ganzzahlige Optimierung, sowie Anwendungen für maschinelles Lernen, Logistik, Big Data und Physik. Unser Ansatz umfasst aktuelle und spannende Entwicklungen wie die quantendynamische Programmierung und die Graphsparsifizierung. Wir sind auch daran interessiert, QAOA Algorithmen zu untersuchen, die auf realen kleinen Quantencomputern, wie sie heute verfügbar sind, ausgeführt werden können.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Belgien, Frankreich, Lettland
• Kooperationspartner: Professor Dr. Aleksandrs Belovs; Privatdozent Dr. Frédéric Magniez; Professor Jérémie Roland