qubolite: Eine Toolbox für das Arbeiten mit QUBO

Quantencomputing (QC) hat eine neue Ära der Berechnung eingeläutet und verspricht, Probleme zu lösen, die für klassische Computer praktisch unlösbar sind. Eine der vielversprechendsten Anwendungen des Quantencomputings ist die Fähigkeit, kombinatorische Optimierungsprobleme wie „Quadratic unconstrained binary optimization“ (QUBO) Probleme zu lösen. Diese Problematik hat mit dem Aufkommen des Quantencomputings wieder an Bedeutung gewonnen. Solch schwer zu lösenden kombinatorischen Probleme treten in vielen verschiedenen Bereichen auf, einschließlich dem Finanzbereich, der Logistik, dem Maschinellen Lernen (ML) und Data Mining. Für mehr Details über QC und die Optimierung im Maschinellen Lernen sei hier auf unsere Blogeinträge „Quantencomputer: Neue Potenziale für Maschinelles Lernen” und „Optimierung im Maschinellen Lernen” verwiesen.

Um das Potenzial des Quantencomputings für QUBO zu nutzen, stellen wir qubolite vor, ein Python-Paket, das Hilfsmittel zur Erstellung, Analyse und Lösen von QUBO-Instanzen umfasst. Dieses Paket beinhaltet aktuelle Forschungsalgorithmen, die von Wissenschaftlern des Lamarr Instituts entwickelt werden.

QUBO verstehen: Optimierung binärer Variablen

Bevor wir tiefer in qubolite unser Python-Pakt eingehen hier ein kurzer Exkurs, was QUBO ist: Wie der Name bereits andeutet, beschäftigen wir uns mit dem Problem, binäre Werte zu finden, die eine quadratische Zielfunktion minimieren. Mathematisch kann unser Ziel wie folgt ausgedrückt werden:

wobei x einen binären Vektor darstellt und Q eine symmetrische Matrix ist, welche die Problemparameter beinhaltet.

Aufgrund ihrer diskreten Natur treten QUBO-Instanzen hauptsächlich im Bereich der kombinatorischen Optimierung auf, also dort, wo wir eine optimale Konfiguration von Variablen aus einer endlichen Anzahl von Möglichkeiten finden möchten. Allerdings sind solche Probleme oft schwer oder sogar unlösbar für klassische Computer, da die Anzahl der möglichen Lösungen mit der Problemgröße, d. h. der Anzahl der Variablen, exponentiell wächst. Quantencomputing verspricht eine erhebliche Beschleunigung beim Lösen von QUBO-Problemen, dank Algorithmen wie dem Quantum Approximate Optimization Algorithm (QAOA) und dem Quantenannealing. Aufgrund der Fehleranfälligkeit und begrenzten Rechenleistung der heutigen Quantenhardware muss man jedoch bei der Entwicklung geeigneter Problemformulierungen, die mit den uns zur Verfügung stehenden Quantenressourcen gelöst werden können, sehr sorgfältig vorgehen. Integrierte Steuerungsfehler sind ein prominentes Beispiel für diese Einschränkungen. Sie beschreiben die physikalischen Fehler, die auftreten, wenn ein gegebenes QUBO-Problem auf der Hardware implementiert wird. Während dieses Prozesses können Parameter verändert werden, was dazu führt, dass der Quantenannealer ein anderes Problem löst und somit suboptimale Lösungen des ursprünglichen Problems erhält. Dieser Effekt ist in Abb. 1 visualisiert.

QUBO erschließen: qubolite stellt sich vor

Um die Arbeit mit QUBO zugänglicher zu machen, haben Wissenschaftler des Lamarr Instituts qubolite entwickelt, ein umfassendes Python-Paket, das eine Reihe von Funktionalitäten bietet:

• QUBO-Hilfsmittel: Viele nützliche Hilfsmittel für die Arbeit mit QUBO sind integriert, wie zum Beispiel einfache Instanziierung, Umwandlung in und aus dem Ising-Modell, Berechnung des Dynamikbereichs der Parameter, Sampling oder Teilzuweisungen bestimmter Variablen.
• Problem-Solvers: Das Paket bietet State-of-the-Art-Solver wie „Simulated Annealing”, aber auch einen „Brute-Force”-Ansatz, mit einer effizienten, parallelisierten Implementierung in C/C++.
• Preprocessing: Um das Beste aus den verfügbaren Solvern herauszuholen, sind Methoden zur Vorverarbeitung implementiert. Diese können entweder bestimmte Eigenschaften von Lösungen identifizieren und die Größe des Suchraums reduzieren oder QUBO-Instanzen optimal für die Verwendung auf echten Quantencomputern konditionieren.
• QUBO-Embeddings: Verschiedene reale Probleme, formuliert als QUBO, werden bereitgestellt, angefangen bei ML-Problemen wie Clustering bis hin zu allgemeinen kombinatorischen Problemen.

Die ersten Schritte mit qubolite

Um mit qubolite loszulegen, reicht es das Paket über pip zu installieren:

Für die vollständige Nutzung von qubolite werden alle optionalen Abhängigkeiten verwendet, die sich auf mehrere Open-Source Python-Pakete wie sklearn und igraph stützen. Die Standardversion ist jedoch nur vom numpy -Paket abhängig. Nach der Installation können wir QUBO-Probleme instanziieren. Hierfür betrachten wir ein einfaches Clustering-Problem, das mit dem ML-Paket sklearn generiert wird:

Der Datensatz ist in Abb. 2 (links) visualisiert. Das Ziel ist jetzt, die Datenpunkte in zwei Cluster aufzuteilen. Dazu importieren wir eine Clustering-Einbettung und erhalten eine QUBO-Instanz:

Die Lösung dieses QUBO-Problems stellt ein perfektes Clustering der Datenpunkte dar. Da unsere Problemgröße klein ist (30), können wir die Brute-Force-Methode verwenden, welche garantiert die beste Lösung findet.

The erhaltene Lösung ist in Abb. 2 (rechts) visualisiert, wobei die Clusterzuweisungen mit unterschiedlichen Farben angezeigt werden. Allerdings ist bei zunehmender Größe des Datensatzes ein Brute-Force-Ansatz nicht mehr möglich, da die Anzahl der Lösungen mit der Problemgröße exponentiell wächst.

Preprocessing für Quantencomputer

Da Quantencomputer das quantenmechanische Phänomen der Superposition nutzen, haben sie die Fähigkeit, effizient nach einer optimalen Lösung in exponentiell großen Räumen zu suchen. Heutzutage befindet sich Quantenhardware noch in ihren Anfängen, da sie eine begrenzte Anzahl von Qubits besitzt und anfällig für Fehler ist.

Wie stark sich diese Fehler auf die Lösungsqualität auswirken, hängt in großem Maße von dem Dynamikbereich der gegebenen QUBO-Matrixparameter ab. Der Dynamikbereich entspricht der Anzahl der Bits, die erforderlich sind, um die QUBO-Parameter unter Berücksichtigung des abgedeckten Wertebereichs und kleiner Abstufungen treu zu kodieren. Wissenschaftler des Lamarr Instituts entwickelten einen Algorithmus zur Reduzierung des Dynamikbereich eines gegebenen QUBO-Problems, während die optimale Lösung erhalten bleibt. Diese Methode ist in qubolite implementiert und kann folgendermaßen verwendet werden:

Nicht nur die Leistungsfähigkeit echter Quantenannealer wird durch die Reduzierung des Dynamikbereichs erhöht, sondern auch die Leistung klassischer Hardwarelösungen, die eine begrenzte Parameter-Bit-Präzision haben. Ein solcher beispielhafter Hardwarelöser ist unser IAIS Evo Annealer. Weitere Details zu dieser Technologie sind in unserem Blogbeitrag „Vorbereitung auf das Quantenzeitalter mit dem IAIS Evo Annealer“ zu finden.

Wir schließen die Lücke mit modernster Quantenforschung und ihrem Impact in der realen Welt

qubolite eröffnet neue Möglichkeiten zur Lösung komplexer Optimierungsprobleme mit Quantencomputing, da die neuesten Forschungsergebnisse des Lamarr-Instituts in Echtzeit integriert werden. Das Python-Paket bietet eine benutzerfreundliche und vielseitige Toolbox, um das Potenzial von QC zu nutzen. Darüber hinaus wird es nicht nur in unserer Forschung verwendet, sondern auch in verschiedenen Industrieprojekten am Fraunhofer IAIS, einer der vier Lamarr-Partnerinstitutionen, eingesetzt. Im Zuge der fortschreitenden Entwicklung von Quanten-Hardware trägt qubolite als frei nutzbares Softwarepaket dazu bei, Quantenoptimierung für eine Vielzahl von Branchen zugänglich und nutzbar zu machen.

Weitere Informationen über qubolite:

https://github.com/smuecke/qubolite

Optimum-Preserving QUBO Parameter Compression

Mücke, Sascha et al., 2023, arXiv-Vorabdruck, pdf