August 2023

a:3:{s:6:"locale";s:5:"de_DE";s:3:"rtl";i:0;s:9:"flag_code";s:2:"de";}
Anwendung von Graphpartitionierungsalgorithmen und Genetischen Algorithmen zur Optimierung der Teleportationskosten in verteilten Quantenschaltkreisen

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

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.

Autor/in:

Teodor Slaveykov

Betreuer:

Leo Sünkel Thomas Gabor, Claudia Linnhoff-Popien

Studentische Abschlussarbeit | Veröffentlicht {Monat Jahr} | Copyright © QAR-Lab
Anfragen zu dieser Arbeit an die Betreuer


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

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

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.

Autor/in:

Dominik Ott

Betreuer:

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

Studentische Abschlussarbeit | Veröffentlicht August 2023 | Copyright © QAR-Lab
Anfragen zu dieser Arbeit an die Betreuer


Einfluss von Embedding Methoden auf Generalisierbarkeit in Quantum Machine Learning

Einfluss von Embedding Methoden auf Generalisierbarkeit in Quantum Machine Learning

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.

Autor/in:

Steffen Brandenburg

Betreuer:

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

Studentische Abschlussarbeit | Veröffentlicht August 2023 | Copyright © QAR-Lab
Anfragen zu dieser Arbeit an die Betreuer