Immer wieder liest man, dass nur mit Quantencomputern schwierige Optimierungsprobleme gelöst werden könnten. Als Beispiel wird oft das Traveling-Salesperson-Problem genannt, bei dem eine kürzeste Rundreise in einem Graphen gesucht wird. In letzter Zeit hört man auch oft vom sogenannten MaxCut-Problem, bei dem ein Graph so in zwei Teile aufgeteilt werden soll, dass die Kanten zwischen den beiden Teilen maximales Gewicht haben. Die steigende Popularität des MaxCut-Problems erklärt sich dadurch, dass es sich einfach als ein „Quadratisches uneingeschränktes binäres Optimierungsproblem“ (QUBO) modellieren lässt, das auf Quantencomputern besonders gut behandelbar ist. Das liegt wiederum daran, dass man zur Lösung des MaxCut-Problems „nur“ den Knoten des Graphen die Seiten links oder rechts zuweisen muss, und diese Seiten übersetzen sich direkt in die beiden Zustände „0“ und „1“ eines Quantenbits (Qubits).

Mit den am Forschungscampus MODAL entwickelten Verfahren können QUBOs nun schneller auf einem Smartphone gelöst werden als auf dem neusten Quantenannealer und ein Raspberry-Pi löst Traveling-Salesperson-Probleme schneller als jeder aktuelle Quantencomputer. Dank dieser Algorithmen benötigt unser QUBO-Verfahren auf einem normalen PC nur 0,2 Sekunden, um eine Lösung von vergleichbarer Qualität zu finden, wie sie ein Quantencomputer berechnet. Nach zwei Tagen wird die bestmögliche Lösung überhaupt gefunden und nach drei weiteren Tagen auch mathematisch bewiesen, dass es keine bessere Lösung gibt.

Solche Probleme treten in verschiedenen Bereichen in der Informatik, der Physik und den Ingenieurwissenschaften auf:

• Maschinelles Lernen: QUBO-Probleme können verwendet werden, um die Parameter von maschinellen Lernmodellen zu optimieren.
• Finanzwissenschaft: QUBO-Probleme können verwendet werden, um Investmentportfolios zu optimieren, z. B. zur Minimierung von Risiken und zur Maximierung von Erträgen.
• Graphentheorie: QUBO-Probleme können verwendet werden, um graphentheoretische Probleme zu lösen, z. B. das Finden des maximalen Schnittes in einem Graphen.
• Logistik: QUBO-Probleme können verwendet werden, um Transportlogistik zu optimieren, z. B. um Lieferzeiten und Kosten zu minimieren.
• Bilderkennung: QUBO-Probleme können verwendet werden, um die Erkennung von Bildern zu optimieren, z. B. bei der Gesichtserkennung oder der Objekterkennung.
• Energiemanagement: QUBO-Probleme können verwendet werden, um den Energieverbrauch zu optimieren, z. B. in intelligenten Netzen oder beim Energiemanagement von Gebäuden.

Aufgrund seiner großen Bedeutung hat sich auch der Forschungscampus MODAL mit dem Thema QUBO befasst. Die Forschungscampus-Mitglieder Daniel Rehlfeldt, Thorsten Koch und Yuji Shinno haben einen neuen Algorithmus „Qubowl“ entwickelt, der in Kürze in der internationalen Fachzeitschrift „Mathematical Programming: Computation“ veröffentlicht wird.  Für die Implementierung wurden die im SynLab des Forschungscampus MODAL entwickelten Frameworks SCIP https://scipopt.org und UG https://ug.zib.de verwendet. Die Arbeiten erfolgten in Kooperation mit der I²DAMO GmbH und dem assoziierten Fachgebiet Software und Algorithmen für die diskrete Optimierung von Prof. Dr. Thorsten Koch an der TU Berlin, sowie der School of Informatics and Data Science der Hiroshima University, dem Fujisawa Laboratory am Institute of Mathematics for Industry der Kyushu University und dem Departement of Mathematics der National University of Singapore.

Nach dem derzeitigen Stand der Forschung benötigt die beweisbar optimale Lösung von QUBO-Problemen im schlechtesten Fall eine exponentielle Laufzeit, und es gibt keine Resultate, die zeigen, dass sich daran durch den Einsatz von Quantencomputern etwas ändern wird. Die besten Verfahren werden in internationalen Wettbewerben miteinander verglichen. Die bekannten Benchmarks von Prof. Dr. Hans Mittelmann http://plato.asu.edu/ftp/qubo.html zeigen, dass der vom Forschungscampus MODAL entwickelte QUBO Löser derzeit (Stand März 2023) das schnellste der getesteten Programme beim Nonconvex QUBO-QPLIB Benchmark ist.