Einfluss von Embedding Methoden auf Generalisierbarkeit in Quantum Machine Learning

Masterarbeit (August 2023)

Autor: Steffen Brandenburg

Abstract:

Quantum Machine Learning ist ein vielversprechendes Anwendungsgebiet für Quantum Computer. Um aber reale Vorteile gegenüber klassischen Computern zu sehen, benö- tigt es ausgereifte Quantum Grundlagen. Ein Grundbaustein von Quantum Computern sind Embeddings, welche reelle Daten in Quantum Daten umwandeln. In dieser Arbeit stehen der Einfluss verschiedener Embedding-Methoden auf die ”Qualität” eines Quantum Machine Learning Modells im Mittelpunkt. Da der Fokus auf diesen Embeddings liegt, werden Modell und Quantum Circuit simpel gehalten. Sie lösen ein binäres Klassifikationsproblem. Dennoch ist auch das Zusammenspiel von bestimmten Embeddings mit verschiedenen Circuits von Interesse und darauf wird in dieser Arbeit knapp eingegangen. Da in der Literatur bereits viel zu den Embedding-Methoden ”Angle-Embedding” und ”Amplitude-Embedding” existiert, fokussiert diese Arbeit auch auf andere Embedding- Methoden aus der Literatur. Zum Bestimmen der Qualität eines Modells untersuchten wir die Generalisierbarkeit. Dazu wurden verschiedene Maße aus dem klassischen Machine Learning verwendet. Es konnte zwar die Frage nach einem besten Embedding nicht beantwortet werden, dennoch konnten interessante Erkenntnisse zu den Auswirkungen der Embeddings bei unterschiedlichen Datensätzen gewonnen werden.

Betreuer: Leo Sünkel, Thomas Gabor, Claudia Linnhoff-Popien

Community detection für gewichtete Graphen mittels Trennknotenerkennung in der NISQ Ära

Bachelorarbeit (August 2023)

Autor: Dominik Ott

Abstract:

Ein wichtiges Optimierungsproblem in der Informatik ist die Community Detection. Dabei können durch die Analyse von Netzwerken sogenannte Communities gefunden werden und wichtige Informationen in vielen Bereichen – von der Biologie bis zu sozialen Strukturen – abgeleitet werden. Durch Gewichte an den einzelnen Kanten können noch mehr Informationen verarbeitet werden als durch die bloße Existenz jener Kanten, jedoch müssen für die Community Detection auf gewichteten Graphen dadurch auch mehr Faktoren berücksichtigt werden. Als NP-schweres Optimierungsproblem werden häufig Heuristiken benutzt, um schneller und effizienter eine akzeptable Lösung zu finden. Ein vielversprechender Ansatz ist dabei die Nutzung von Quanten-Computern, da bereits experimentell gezeigt werden konnte, dass diese in bestimmten Bereichen (z.B. Grover oder Shor-Algorithmus) effizienter Resultate erzielen können als klassische Computer. Da die meisten Ansätze für Community Detection durch QUBO-Matrizen jedoch sehr viel Speicherplatz verbrauchen, ist das Ziel dieser Arbeit einen Ansatz mit möglichst guter Speichereffizienz zu finden. Dafür wird ein vielversprechender Ansatz für die Community Detection vorgestellt, der auf der Erkennung und Analyse von Trennknoten basiert, was den Vorteil bietet, dass die Dimensionen der daraus resultierenden QUBO-Matrix die Anzahl der Knoten nicht übersteigen und die Matrix selber genauso dünn besetzt ist wie die Adjazenzmatrix des Graphs. Diese Trennknoten sollen den Graphen bei ihrer Entfernung so unterteilen, dass die übrig gebliebenen Komponenten jeweils exakt Teil einer Community sind. Dieser Ansatz wird auf gewichtete Graphen ausgebaut, indem die Wahrscheinlichkeit, dass es sich bei einer Kante um eine Trennkante handelt, anhand des Informationsdurchflusses der Nachbarschaft bestimmt wird. Dies wird anhand von synthetisch hergestellten Graphen mit einer festen Grundwahrheit über deren Communities, denen Gewichte zugewiesen werden ohne die Community-Struktur zu verändern, überprüft.

Betreuer: Jonas Stein, Jonas Nüßlein, Claudia Linnhoff-Popien

Anwendung von Graphpartitionierungsalgorithmen und genetischen Algorithmen zur Optimierung der Teleportationskosten in verteilten Quantenschaltkreisen

Bachelorarbeit (August 2023)

Autor: Teodor Slaveykov

Abstract:

Derzeit befinden wir uns in der Noisy Intermediate Scale Quantum (NISQ) – Ära, in der die Anzahl der Qubits, die in einem einzelnen Quantencomputer verwendet werden können, zunimmt. Mit dieser Entwicklung entstehen jedoch Herausforderungen bei der Handhabung großer Quantensysteme. Die verteilte Quantenberechnung gewinnt daher an Bedeutung, um diese Herausforderungen zu bewältigen. Dabei werden mehrere Quantencomputer oder Quantenverarbeitungseinheiten miteinander verbunden, um gemeinsam an einem Problem zu arbeiten. Dies ermöglicht die Nutzung größerer Rechenkapazitäten und effizientere Lösungen komplexer Aufgaben. In der verteilten Quantenberechnung kommunizieren verschiedene Einheiten oder Teilsysteme miteinander, um Quanteninformation auszutauschen. Dabei spielt das grundlegende Teleportationsprotokoll eine wichtige Rolle. Es ermöglicht die Übertragung von Quanteninformationen zwischen den Teilsystemen. Ein wichtiger Aspekt besteht darin, die Anzahl der Teleportationen zu minimieren. Somit wird angestrebt, die Genauigkeit der Quantenberechnungen zu steigern, die Fehleranfälligkeit der Qubits zu reduzieren und gleichzeitig den Ressourcenverbrauch effizienter zu gestalten. In dieser Arbeit werden verschiedene Graphpartitionierungsalgorithmen, wie der Kernighan-Lin-Algorithmus und die Spektrale Partitionierung, ein Genetischer Algorithmus (GA) sowie zwei hybride Genetische Algorithmen (HGA), die eine Kombination aus den Graphpartitionierungsalgorithmen und einem GA sind, angewendet und untersucht, um die Anzahl globaler Quantengatter und die damit verbundenen Teleportationskosten zu minimieren. Zunächst werden die Graphpartitionierungsalgorithmen verwendet, um die Knoten möglichst gleichmäßig zu partitionieren. Zusätzlich wird ein GA implementiert, der sich um die Aufteilung der Qubits mittels zufälliger Partitionen kümmert. Die beiden HGA führen zu einer nahezu optimalen Anordnung der globalen Quantengatter, nachdem die Qubits mithilfe der Graphpartitionierungsalgorithmen partitioniert sind. Schließlich werden die vorgeschlagenen Ansätze anhand von neun Benchmark-Schaltkreisen untersucht und hinsichtlich der Anzahl globaler Quantengatter und Teleportationskosten verglichen. Außerdem werden zufällige Suchläufe für den GA und der beiden HGA durchgeführt, um deren Leistungsfähigkeit in Bezug auf das Optimierungsziel zu überprüfen. Die Ergebnisse deuten auf eine signifikante Verbesserung der Teleportationskosten hin.

Betreuer: Leo Sünkel, Thomas Gabor, Claudia Linnhoff-Popien

Multi-Agent Exploration through Peer Incentivization

Masterarbeit (August 2023)

Autor: Johannes Tochtermann

Abstract:

Während Exploration im Bereich des bestärkenden Lernens (Reinforcement Learning) mit einem einzelnen Agenten innerhalb der letzten Jahre weitreichend untersucht wurde, gibt es diesbezüglich weitaus weniger Arbeiten im Bereich des bestärkenden Lernens mit Multi-Agenten-Systemen (Multi-Agent Reinforcement Learning). Um diese Lücke zu adressieren, wird in dieser Arbeit eine Belohnungsfunktion mit Peer Incentivisation Mechanismus (d.h., Agenten haben die Möglichkeit, sich gegenseitig zu belohnen) vorgeschlagen, inspiriert von vorangegangenen Arbeiten in den Bereichen intrinsische Neugier und Belohnung basierend auf Einfluss. Die PIMAEX Belohnung – kurz für Peer-Incentivised Multi-Agent Exploration – zielt darauf ab, Exploration in Multi-Agenten Szenarien zu verbessern, und gibt Agenten einen Anreiz, in einer Art und Weise aufeinander Einfluss auszuüben, die es wahrscheinlicher macht, dass die Agenten neue Zustände (im Zustandsraum ihrer Umgebung) entdecken. Die PIMAEX Belohnung wird in Verbindung mit PIMAEX-Communication evaluiert, einem Multi-Agenten Trainings-Algorithmus, der einen Kommunikationskanal nutzt, um Agenten Einfluss aufeinander ausüben zu lassen. Zur Evaluation werden Agenten in der Consume/Explore Umgebung trainiert, einer partiell-beobachtbaren Umgebung mit irreführenden Belohnungen, die mit dem Ziel entwickelt wurde, eine Herausforderung in Bezug auf das Exploration-vs.-Exploitation Dilemma sowie das Credit-Assignment Problem darzustellen. Die Resultate dieser Evaluation zeigen empirisch, dass Agenten, die die PIMAEX Belohnung in Verbindung mit PIMAEX-Communication nutzen, die Leistung von Agenten übertreffen, die dies nicht tun.

Betreuer: Michael Kölle, Claudia Linnhoff-Popien

Genetic Neuron Selection for Deep Neural Networks

Bachelorarbeit (Juni 2023)

Autor: Julian Schönberger

Abstract:

Die Lottery Ticket Hypothesis wurde kürzlich um die Behauptung erweitert, dass in einem ausreichend großen und breiten künstlichen Neuronalen Netz Subnetzwerke existieren, sogenannte starke Lotterietickets, welche ohne Training bereits hohe Accuracies erzielen. Dies löste ein großes Interesse in der Forschungsgemeinschaft aus, insbesondere in dem Feld des Prunings von Neuronalen Netzen, da diese Erkenntnis die Basis für eine Alternative zum Training mittels Backpropagation darstellen könnte. In diesem alternativen Ansatz können durch einfaches Pruning aller nicht notwendigen und accuracy-schadenden Gewichte leistungsstarke Subnetzwerke entdeckt werden. Verschiedene Algorithmen wurden zum Finden dieser Subnetzwerke entwickelt. Oft folgen sie einem sogenannten greedy Ansatz, sodass sie nur die lokalen Informationen im Suchraum verwenden. Dadurch neigen sie dazu ausschließlich lokale Optima zu finden. Als Antwort auf diese Limitierungen argumentieren wir für die Vorteile des Einsatzes von genetischen Algorithmen (GA) welche Methodiken, die von der natürlichen Evolution inspiriert wurden, dazu verwenden effektiv den Suchraum nach dem globalen Optimum zu durchsuchen. Trotz des blackbox Charakters des Optimierungsproblems, welches offensichtlich für die Verwendung von metaheuristischen Verfahren spricht, existieren unserer Kenntnis nach keine weiteren Arbeiten welche GAs in breitem Umfang einsetzen. Aus diesen Gründen präsentieren, analysieren und diskutieren wir verschiedene Methoden, die in den einzelnen Schritten des GA-Zyklus eingesetzt werden können. Auf Basis extensiver empirischer Untersuchungen argumentieren wir dafür, dass der Einsatz von generellen problemunspezifischen Methoden aus dem Bereich des Evolutionary Computings bereits für das Optimierungsproblem ausreicht. Die Arbeit schließt damit, dass GAs tatsächlich dazu in der Lage sind starke Lotterietickets zu finden, was sie zu einer aussichtsreichen Alternative zum Training macht. Zusätzlich haben wir herausgefunden, dass für das gegebene Klassifikationsproblem das Sampling der Weights und der Biases aus einer Gleichverteilung sowie die Überparameterisierung des Netzwerks mit einem Faktor nahe 5 in Relation zu dem trainierten Netzwerk die höchsten Accuracies erbrachte. Aufbauend auf diesen Ergebnissen konnten beinahe 100% Acuraccies auf dem moons dataset von Scikit-learn erzielt werden

Betreuer: Thomas Gabor, Thomy Phan, Claudia Linnhoff-Popien

Quantum-Multi-Agent-Reinforcement-Learning mit Evolutionärer Optimierung

Bachelorarbeit (April 2023)

Autor: Felix Topp

Abstract:

Multi-Agent-Reinforcement-Learning gewinnt in Zeiten des autonomen Fahrens und anderer intelligenter industrieller Anwendungen zunehmend an Bedeutung. Gleichzeitig entsteht ein vielversprechender neuer Ansatz für Reinforcement-Learning, nämlich das Quantum-Reinforcement-Learning: Dieser nutzt die inhärenten Eigenschaften der Quantenmechanik und kann dadurch die trainierbaren Parameter eines Modells reduzieren. Allerdings haben gradientenbasierte Quantum-Multi-Agent-Reinforcement-Learning-Methoden oft mit Barren-Plateaus zu kämpfen, die sie daran hindern, die Leistung klassischer Ansätze zu erreichen. Die vorliegende Arbeit basiert auf dem Ansatz von Chen et al. (2022) für gradientenfreies Quantum-Reinforcement-Learning und präsentiert einen Ansatz mit Variational-Quantum-Circuits für Multi-Agent-Reinforcement-Learning unter Verwendung von evolutionärer Optimierung. Der Ansatz wird in dem Environment Coin-Game mit klassischen Ansätzen verglichen. Es wird gezeigt, dass der Variational- Quantum-Circuit-Ansatz im Vergleich zu einem neuronalen Netz mit einer ähnlichen Anzahl von trainierbaren Parametern deutlich besser abschneidet. Verglichen mit dem größeren neuronalen Netz erzielt der hier präsentierte Ansatz ähnliche Ergebnisse mit 98, 88% weniger Parametern.

Betreuer: Michael Kölle, Thomy Phan, Claudia Linnhoff-Popien

Anomaly Detection using Quantum Circuit Born Machines

Bachelorarbeit (April 2023)

Autor: Ahmad Almohamad Alissa

Abstract:

Die Erkennung von Anomalien ist eine wichtige Komponente in verschiedenen Bereichen, z. B. im Finanzwesen, in der medizinischen Diagnose und bei der Betrugserkennung. Da die Datensätze immer komplexer und größer werden, stoßen herkömmliche Computer an die Grenzen ihrer Verarbeitungsleistung. Im Gegensatz dazu bieten Quantencomputer dank der physikalischen Eigenschaften ihrer Qubits, wie Verschränkung und Überlagerung, vielversprechende Lösungen. Die Entwicklung des maschinellen Lernens auf der Basis von Quantencomputern, insbesondere von Quantenschaltkreisen (Quantum Circuit Born Machines, QCBMs), wird als vielversprechender Ansatz zur Bewältigung solch komplexer Probleme vorgestellt. QCBMs sind parametrisierte Quantenschaltungen, die trainiert werden können, um Stichproben aus einer Zielverteilung zu erzeugen. Ziel dieser Arbeit ist es, diese Fähigkeit zur Erkennung von Anomalien zu nutzen, deren Verteilung sich von der normaler Datenpunkte unterscheidet. Die Wirksamkeit von QCBMs für die Erkennung von Anomalien wird anhand eines Datensatzes untersucht, der mit der make_blobs-Methode aus dem Scikit-learn-Paket in Python generiert wurde und bei dem einige Ausreißer deutlich von den Clustern unterschieden werden können. Seine Leistung wird mit einem Autoencoder-Modell anhand der ROC-Kurve und des Matthews-Korrelationskoeffizienten (MCC) verglichen. Diese Metriken werden verwendet, um die Fähigkeit der Modelle zur Erkennung von Anomalien und zur Vermeidung falsch positiver Ergebnisse zu bewerten. Die Ergebnisse zeigen, dass QCBMs den Autoencoder übertreffen, wenn sie mit einem kleineren Datensatz trainiert werden, was darauf hindeutet, dass QCBMs effektiver im Umgang mit Daten sind und die zugrunde liegende Verteilung effizienter lernen können als der Autoencoder. Beide Modelle können jedoch die Verteilung lernen, wenn sie mit dem gesamten Datensatz trainiert werden.

Betreuer: Jonas Stein, Daniëlle Schuman, Claudia Linnhoff-Popien

Efficient Quantum Circuit Architecture for Coined Quantum Walks on many Bipartite Graphs

Bachelorarbeit (Juli 2023)

Autor: Viktoryia Patapovich

Abstract:

Quantum-Walks, ein Quantenanalogon der klassischen Random-Walks, haben sich als leistungsfähiges Paradigma für Quantenberechnungen und -simulationen erwiesen. Während klassische Random Walks auf stochastischen Prozessen beruhen, um Systeme zu erforschen, nutzen Quantenwalks die einzigartigen Eigenschaften der Quantenmechanik, um diese Aufgaben effizienter zu erfüllen. Insbesondere zeitdiskrete Quantenwanderungen (DTQWs) wurden ausgiebig für ihre Anwendungen in der Graphentheorie untersucht, wie z. B. Graphenisomorphismus, Graphenkonnektivität und graphbasierte Suchprobleme. Trotz ihres Potenzials bleibt die Implementierung von DTQWs auf zeitnahen Quantengeräten eine Herausforderung. Während sich frühere Arbeiten auf die Implementierung von Quantenschaltkreisen für DTQWs mit einheitlichen Münzoperatoren konzentrierten, ist die Implementierung von inhomogenen Münzsätzen eine komplexe Aufgabe, die neue Ansätze erfordert. In dieser Arbeit wird eine effiziente Quantenschaltungsarchitektur zur Implementierung von DTQWs mit inhomogenen, positionsabhängigen Münzsätzen auf einer großen Teilmenge von bipartiten Graphen vorgestellt. Es wird ein neuartiges Kantenbeschriftungsschema, Gray Code Directed Edges encoding, eingeführt, das die Vorteile des Gray Codes für die Positionskodierung und die bipartite Struktur des zugrundeliegenden Graphen nutzt, um die Komplexität der Quantenschaltungen zu minimieren, die die Münz- und Verschiebeoperatoren darstellen. Diese Optimierung führt zu weniger Gatteroperationen, wodurch die Auswirkungen von Rauschen und Fehlern in zukünftigen Quantengeräten reduziert werden. Es wird ein Beschriftungsschema für verschiedene Graphentopologien entwickelt, darunter Zyklusgraphen, verkettete Zylindergraphen und quadratische Gittergraphen, die besonders für Anwendungen des Verstärkungslernens relevant sind. Diese Erkenntnisse bieten eine neue Perspektive auf die Implementierung von geprägten Quantenspaziergängen und bilden die Grundlage für zukünftige Forschungen zu Quantenspaziergängen mit inhomogenen Münzmengen.

Betreuer: Jonas Stein, Michael Kölle, Maximilian Balthasar Mansky, Claudia Linnhoff-Popien