Student-Abstracts

a:3:{s:6:"locale";s:5:"de_DE";s:3:"rtl";i:0;s:9:"flag_code";s:2:"de";}
Verwendung evolutionärer Algorithmen zur Optimierung von Quantenschaltkreisen unter der Berücksichtigung von Noise

Verwendung evolutionärer Algorithmen zur Optimierung von Quantenschaltkreisen unter der Berücksichtigung von Noise

Abstract:

Noise stellt eine allgegenwärtige Herausforderung in der NISQ-Ära des Quantum Computings dar. Seine starke Auswirkung auf die Hardware eines Quantencomputers verfälscht die Ergebnisse von Quantenschaltkreisen, insbesondere bei steigender Qubitanzahl und Schaltkreistiefe. Verschiedene Schaltkreisarchitekturen, die ähnliche Zustände erzeugen, können allerdings unterschiedlich starkem Noise ausgesetzt sein. Diese Arbeit präsentiert einen evolutionären Algorithmus, dessen Ziel es ist, für einen gegebenen Schaltkreis einen äquivalenten, weniger noisy Schaltkreis zu finden. Die Fitnessfunktion des Algorithmus bewertet dabei die Schaltkreise anhand ihrer unter Noise betrachteten Fidelität im Vergleich zum Noise-freien Zustand des Zielschaltkreises. So wird der Evolutionsverlauf in Richtung einer Noise-reduzierten Lösung gelenkt. Die Ergebnisse der durchgeführten Experimente zeigen, dass der Algorithmus die parallel erstellte Random Baseline überwiegend übertraf und in einigen Fällen einen optimierten Schaltkreis im Vergleich zum Zielschaltkreis finden konnte. Dadurch zeigt sich das Potential evolutionärer Algorithmen zur Noise-Reduktion. Die Skalierbarkeit des vorgestellten Algorithmus ist jedoch stark begrenzt.

Autor/in:

Maria Trainer

Betreuer:

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

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


Emergente Kooperation in Quantum Multi-Agenten Reinforcement Learning mittels Kommunikation

Emergente Kooperation in Quantum Multi-Agenten Reinforcement Learning mittels Kommunikation

Abstract:

Emergente Kooperation im klassischen Multi-Agent Reinforcement Learning hat große Aufmerksamkeit erlangt, insbesondere im Zusammenhang mit sequenziellen sozialen Dilemmas. Während klassische Reinforcement Learning Ansätze gezeigt haben, dass sie zu emergenter Kooperation fähig sind, ist die Forschung zur Erweiterung dieser Methoden auf das aufstrebende Gebiet des Quantum Multi-Agent Reinforcement Learning noch begrenzt, insbesondere mit dem Einsatz von Kommunikation. In dieser Arbeit wenden wir das zweistufige Kommunikationsprotokoll Mutual Acknowledgment Token Exchange (MATE), seine Erweiterung Mutually Endorsed Distributed Incentive Acknowledgment Token Exchange (MEDIATE), den Peer-Rewarding Mechanismus Gifting und Reinforced Inter-Agent Learning (RIAL), einen Ansatz zum Erlernen eines diskreten Kommunikationsprotokolls, auf Quantum Q-Learning an. Wir bewerten die resultierenden acht Ansätze hinsichtlich ihrer Auswirkungen auf emergente Kooperation in drei sequenziellen sozialen Dilemmas, nämlich dem iterierten Prisoner’s Dilemma, der iterierten Stag Hunt und dem iterierten Game of Chicken. Unsere experimentellen Ergebnisse zeigen, dass die Ansätze MATETD, AutoMATE, MEDIATE-I and MEDIATE-S ein hohes Maß an Kooperation in allen drei sequenziellen sozialen Dilemmas erreichten, was beweist, dass Kommunikation eine mögliche Methode ist, um emergente Kooperation in Quantum Multi-Agent Reinforcement Learning zu erreichen.

Autor/in:

Christian Reff

Betreuer:

Michael Kölle, Leo Sünkel, Claudia Linnhoff-Popien

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


Analyse der Parameteranpassung des Transfer Lernens in Variationellen Quanten-Eigensolvern

Analyse der Parameteranpassung des Transfer Lernens in Variationellen Quanten-Eigensolvern

Abstract:

Mit der Verbreitung öffentlich verfügbarer, wenn auch rauschanfälliger Quantenprozessoren wurden viele Machine-Learning Ansätze entwickelt, um die neu aufgekommenen Möglichkeiten optimal zu nutzen. Peruzzo et al. entwickelten einen hybriden Algorithmus, der einen Variational-Quantum-Eigensolver (VQE) implementiert, um den Grundzustand eines Hamiltonians zu finden. Während VQEs anfänglich im Bereich der Quantenchemie eingesetzt wurden, können sie für verschiedene Optimierungsprobleme verwendet werden, wie zum Beispiel das Finden eines maximalen Schnitts (Max-Cut) in einem Graphen. Da das Training rechenintensiv ist, wurden Transfer-Learning Ansätze vorgeschlagen, um die Trainingszeit für ähnliche Probleminstanzen zu reduzieren. Rohe et al. stellen einen VQE-Algorithmus vor, der TL nutzt, um die Konvergenz im Max-Cut- Problem zu beschleunigen. Es wurde gezeigt, dass TL in der frühen Optimierungsphase deutlich schneller konvergiert, obwohl Training ohne TL über die Zeit leicht bessere Ergebnisse liefert. Wenn jedoch die Trainingszeit drastisch reduziert wird, kann TL gute Ergebnisse erzielen und dabei die Rechenkosten des Trainings erheblich senken. Darüber hinaus wurde gezeigt, dass die Ähnlichkeit der erzielten Lösung mit dem optimum positiv mit dem Erfolg von TL korrelierte. Die Ähnlichkeit wurde durch Berechnung der minimalen Hamming-Distanz (HD) zwischen der VQE-Lösung des Quellgraphen und den optimalen Lösungen des Zielgraphen gemessen. Diese Bachelorarbeit baut auf den Ansatz von Rohe et al. auf. Konkret ist das Ziel der Arbeit, die Qualität des Parametertransfers zur Lösung von Max-Cut-Graphenproblemen zu analysieren. Anstatt die Anwendbarkeit von TL für den VQE zu analysieren, soll untersucht werden, wo TL zu Über- oder Ünteranpassung des Algorithmus führt und wie diese Ergebnisse zustande kommen. Die Quell und Zielgraphen werden sowohl aus dem öffentlich zugänglichen kalifornischen Straßennetz als auch aus Facebook Social Circle Daten entnommen. Dabei wird der Quellgraph genutzt, um Parameter zu trainieren, die zum initialisieren des Trainings des Zielgraphen genutzt werden. Um die Ähnlichkeit des Quell- und Zielgraphen bezüglich des Max-Cut-Problems zu bewerten, werden die optimalen Max-Cut-Lösungen durch Brute Force berechnet. Anschließend wird die minimale HD zwischen optimalen Lösungen der Quell-und Zielgraphen berechnet. Da TL nicht immer eine der optimalen Lösungen findet, wird die HD zwischen der Quelllösung und der durch TL gefundenen Ziellösung berechnet. Dadurch werden daten gesammelt, die zeigen, unter welchen Umständen TL den VQE zu Über- oder Unteranpassung veranlasst. Da die Qualität der trainierten Lösungen mit zunehmender HD zwischen Quell- und Zielgraphenlösungen in den Ergebnissen von Rohe et al. abzunehmen scheint, ist es von großem Interesse, Wege zu finden, mit solchen Problemen umzugehen. Eine mögliche Erklärung für Über- oder Unteranpassung ist, dass die vortrainierten Parameter den VQE in einem lokalen Optimum gefangen halten und dadurch weitere Erkundungen der Lösungslandschaft verhindern. Durch die Analyse des Einflusses von TL auf den Trainingsprozess des VQE sowie der Unter- und Überanpassung zielt diese Arbeit darauf ab, die Rolle und Qualität des Parametertransfers in der NISQ-Ära besser zu bewerten.

Autor/in:

Julio Amaru Nicolas Brocca Alvarado

Betreuer:

Tobias Rohe, Sebastian Woelkert, Thomas Gabor, Claudia Linnhoff-Popien

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


Erforschung der Verschränkungsintensität in Variationellen Quanten-Eigensolver-Algorithmen für kombinatorische Optimierung

Erforschung der Verschränkungsintensität in Variationellen Quanten-Eigensolver-Algorithmen für kombinatorische Optimierung

Abstract:

Variationale Quantenalgorithmen (VQAs), darunter der Quantum Approximate Optimization Algorithm (QAOA), der Variational Quantum Eigensolver (VQE) und Quantum Neuronale Netze (QNNs), haben sich als vielversprechende Ansätze in der verrauschten Intermediate-scale quantum (NISQ) Ära gezeigt. Diese hybriden quantenklassischen Algorithmen zielen darauf ab Optimierungs- und Simulationsprobleme zu lösen, die durch die Qubit-Konzentration, Konnektivität, Gatterfehlern und Dekohärenz eingeschränkt sind. Ein zentrales Merkmal der Quanteninformatik, und ein Unterscheidungsmerkmal zu klassischen Methoden ist die Verschränkung – die Quantenkorrelation zwischen Qubits, die bestimmte rechnerische Vorteile ermöglicht. Während Verschränkung weithin als wesentlich für den Erfolg von VQAs angesehen wird, haben neuere Studien die Annahme in Frage gestellt, dass mehr Verschränkung immer die Leistung des Algorithmus verbessert. Stattdessen kann eine übermäßige Verschränkung unfruchtbare Plateaus einführen, die Optimierung und Konvergenz erschwert.
Diese Arbeit untersucht die Rolle der Verschränkung bei der Leistung des VQE, einem führenden Algorithmus zur Annäherung der Grundzustandsenergien von Quanten-Hamiltonians. Insbesondere wird untersucht, ob die Begrenzung der Verschränkung durch strukturierte Reduktionen die Trainierbarkeit und Lösungsqualität verbessert. Um diese Beziehung systematisch zu analysieren, werden zwei Strategien zur Verschränkungsmanipulation eingesetzt: (1) Dropout-basierte Verschränkungssparsifizierung, bei der verschränkende Gatter zufällig auf der Grundlage einer gegebenen Wahrscheinlichkeit entfernt werden, und (2) parametrisierte Verschränkungsabstimmung, bei der die Stärke der kontrollierten Verschränkungsoperationen durch einen variablen Rotationsparameter eingeschränkt wird. Die Auswirkung dieser Strategien wird für drei Schaltungsansätze durch die Bewertung des Konvergenzverhaltens sowie die Messung von drei Schlüsselmetriken evaluiert: Verschränkungsfähigkeit, Ausdrucksfähigkeit und Approximationsverhältnis.
Die Ergebnisse zeigen, dass die Verringerung der Verschränkung durch Dropout die Optimierungsdynamik verbessert, indem sie möglicherweise unfruchtbare Plateaus abschwächt und die Gradientenvarianz erhöht, was zu schnellerer Konvergenz und niedrigeren Endenergien führt, ohne die Lösungsqualität zu beeinträchtigen. Die unterschiedlichen Reaktionen bei den verschiedenen Ansätzen legen jedoch nahe, dass die Verschränkungsreduktion auf die Schaltungstopologie und die Problemstruktur zugeschnitten und nicht einheitlich angewendet werden sollte. Im Gegensatz dazu zeigt die parametrisierte Verschränkungsabstimmung einen schwächeren Einfluss sowohl auf die Trainierbarkeit als auch auf die endgültige Lösungsqualität, insbesondere in tieferen Schaltungen, in denen die kumulative Verschränkung lokale Anpassungen auf Gatterebene kompensiert. Die Studie zeigt, dass das Konvergenzverhalten ein zuverlässigerer Indikator für die Leistung der VQE ist als die Ausdrucksfähigkeit oder die Verschränkungsfähigkeit allein, was unterstreicht, dass die Verschränkung aktiv verwaltet und nicht wahllos maximiert werden sollte.

Autor/in:

Joel Friedrich

Betreuer:

Tobias Rohe, Philipp Altmann, Thomas Gabor, Claudia Linnhoff-Popien

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


Ermittlung von Verknüpfungen in Produktdaten mittels Quantum Restricted Boltzmann Machines

Ermittlung von Verknüpfungen in Produktdaten mittels Quantum Restricted Boltzmann Machines

Abstract:

Der steigende Softwareanteil in Produkten treibt nicht nur Innovationen voran, sondern erhöht auch die Komplexität. Um das Risiko von Fehlfunktionen in softwarelastigen Produkten zu minimieren und die Rückverfolgbarkeit zu gewährleisten, sind Verknüpfungen zwischen Entwicklungsschritten und Produktionsdaten notwendig. Diese werden durch Regularien wie ISO/IEC 15288 und DIN/ISO 26262 vorgeschrieben. Der Standard Digital Data Package ermöglicht die Verwaltung solcher Verknüpfungen. Jedoch können implizite Verknüpfungen derzeit nur manuell erstellt werden, was aufgrund des Umfangs und der zahlreichen Produktänderungen zu Problemen führt. Ein vielversprechender Ansatz zur automatischen Ermittlung von Verknüpfungen ist der Einsatz von Klassifikatoren. Insbesondere Quantum Restricted Boltzmann Machines bieten aufgrund der geringen Verfügbarkeit verknüpfter Entwicklungsdaten und deren hoher Störanfälligkeit einen vielversprechenden Ansatz. Zur Evaluierung werden klassische neuronale Netze und vortrainierte Klassifikatoren herangezogen. Sie sind etablierte Methoden in der Mustererkennung und dienen als Vergleichsgrundlage für neue Klassifikatoren.

Autor/in:

Simon Hehnen

Betreuer:

Michael Kölle, Jonas Stein, Dr. Fabrice Mogo Nem (PROSTEP AG), Claudia Linnhoff-Popien

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


Problem-Spezifisches Entanglement in Variationellen Quantum Circuits

Problem-Spezifisches Entanglement in Variationellen Quantum Circuits

Abstract:

In den letzten zehn Jahren haben sich Variationale Quanten Algorithmen (VQAs), insbesondere der Variational Quantum Eigensolver (VQE), als vielversprechender Kandidat für das Finden von annähernden Lösungen von Optimierungsproblemen auf den derzeit verfügbaren Noisy Intermediate-Scale Quantum (NISQ) Geräten, die anfällig für Fehler und Quantenrauschen sind, herausgestellt. In der Optimierungsschleife des VQE wird ein Versuchs-Quantenzustand durch einen parametrisierten Quantenschaltkreis erzeugt. Ein klassischer Optimierer passt die Parameter des Schaltkreises an, während die Kostenfunktion des Problems in einem Ising-Hamiltonian formuliert wird. Das globale Minimum der Kostenfunktionslandschaft wird durch die iterative parametrisierte Erzeugung eines Versuchs-Quantenzustands, die Messung dieses Zustands sowie die anschließende klassische Anpassung der Parameter angenähert. Vorausgegangenen Forschungsarbeiten haben gezeigt, dass die Architektur des parametrisierten Schaltkreises, des so genannten Ansatz, einen großen Einfluss auf die Optimierungsleistung des VQE hat.

Obwohl Verschränkung eine Schlüsseleigenschaft der Quantenmechanik ist, ist nicht gut erforscht, ob sie eine koordinierende Rolle im Ansatz-Schaltkreis von hybriden Quantenoptimierungsalgorithmen spielen kann. Während frühere Forschungsarbeiten gezeigt haben, dass Verschränkung keine allgemeinen Vorteile für die Optimierung bietet, wenn sie auf generische, problem-agnostische Weise implementiert wird, untersucht diese Arbeit die Rolle von problemspezifischer Verschränkung in variablen Quantenschaltkreisen und konzentriert sich dabei auf das Max-Cut-Problem, das in diesem Bereich häufig für Benchmarking-Zwecke verwendet wird und praktische Anwendungen in Bereichen wie dem Design von sehr großen integrierten Schaltkreisen (VLSI), sozialen Netzwerken und maschinellem Lernen hat. Das Ziel ist es, zu beurteilen, ob problemspezifische Verschränkungsstrukturen gegenüber problemagnostischen Strukturen Vorteile im Optimierungsverhalten bieten können. Um diese Frage zu beantworten, vergleichen wir systematisch verschiedene Schaltkreisarchitekturen, einschließlich problemspezifischer, generischer und randomisierter Verschränkungsstrategien, um ihre Auswirkungen auf die Optimierungsleistung zu analysieren. Für das problemspezifische Schaltkreisdesign bilden wir die Kanten des zugrundeliegenden Max-Cut-Graphen als Zwei-Qubit-Gatter auf den Schaltkreis ab. Die Ergebnisse zeigen, dass unsere problemspezifische Verschränkungsstruktur zwar über die drei betrachteten Problemgrößen hinweg im Vergleich zum generischen Design langsamer konvergiert, aber durchweg ähnliche angenäherte Kostenfunktionsminima erreicht und eine deutlich schnellere Konvergenzgeschwindigkeit aufweist als die randomisierten Designs. Zukünftige Arbeiten könnten diesen Effekt mit größeren Problemgrößen untersuchen. Darüber hinaus zeigen Experimente in einer Umgebung mit simulierten Rauschen, dass Quantenrauschen die Konvergenz in einem frühen Stadium beschleunigen kann, möglicherweise aufgrund zusätzlicher stochastischer Parameterabweichungen, die dem Optimierer helfen, lokale Minima zu umgehen. Dieser Effekt setzt sich nicht lange fort und das Rauschen verschlechtert letztlich die Optimierung in den späteren Phasen. Darüber hinaus haben wir festgestellt, dass mit zunehmender Anzahl von Verschränkungsschichten die Optimierungsgeschwindigkeit abnimmt, was möglicherweise auf eine Überparametrisierung und damit verbundene, geringere Trainierbarkeit zurückzuführen ist.

Autor/in:
Benjamin Nicolas Joseph Ring

Betreuer:

Tobias Rohe, Julian Hager, Thomas Gabor, Claudia Linnhoff-Popien

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


Emergente Kooperation durch Quanten Verschränkung in Multi-Agenten-Systemen

Emergente Kooperation durch Quanten Verschränkung in Multi-Agenten-Systemen

Abstract:

Diese Arbeit untersucht die Durchführbarkeit der Quantenverschränkung zur Verbesserung der Kooperation im Multi-Agenten Reinforcement Learning. Unter Verwendung des iterierten Gefangenendilemmas als Benchmark, schlagen wir ein dezentralisiertes Multi-Agenten Reinforcement Learning (MARL) vor in dem zwei Agenten, die mit variablen Quantenschaltungen ausgestattet sind, sich gegenseitig durch Quantenverschränkung beeinflussen können. Im Gegensatz zu existierenden Ansätzen, die sich auf dedizierte Quanten-Kommunikationskanäle angewiesen sind, wird in dieser Arbeit untersucht, ob die Verschränkung allein kooperative Gleichgewichte ermöglichen kann. Daher evaluieren wir die Auswirkungen verschiedener Verschränkungs-Architekturen, um kooperative Strategien zu entwickeln, die dem Nash-Gleichgewicht entgehen. Die Ergebnisse unserer Experimente zeigen, dass Verschränkung zwar Strategien ermöglichen kann Verschränkung zwar Strategien ermöglicht, die besser sind als die gegenseitige Defekt-Strategie, aber langfristig kooperatives Verhalten nicht möglich ist. Das deutet darauf hin, dass Quantenkorrelationen allein nicht ausreichen, um kooperative Strategien in Multi-Agenten Reinforcement Learning aufrechtzuerhalten.

Autor/in:

Marvin Heinrich

Betreuer:

Michael Kölle, Leo Sünkel, Claudia Linnhoff-Popien

Studentische Abschlussarbeit | Veröffentlicht März 2025 | Copyright © QAR-Lab
Anfragen zu dieser Arbeit an die Betreuer


Verteiltes Quantum Machine Learning – Training und Auswertung eines ML Modells auf einem verteilten Quantencomputer Simulator

Verteiltes Quantum Machine Learning – Training und Auswertung eines ML Modells auf einem verteilten Quantencomputer Simulator

Abstract:

Die Anzahl der Qubits, die auf einem Quantencomputer zur Verfügung stehen, stellt in der Regel eine Einschränkung für das Training und die Ausführung von Quantum-Machine-Learning-Modellen dar. Eine mögliche Lösung dieses Problems besteht darin, das Modell auf mehrere Quantumcomputer aufzuteilen und verteilt auszuführen. Dieser Ansatz wird als Distributed Quantum Machine Learning (DQML) bezeichnet. Dadurch kann eine größere Anzahl von Qubits verwendet werden, was das Training größerer Modelle ermöglicht oder die Klassifikationsleistung verbessern kann. Allerdings erfordert die Kommunikation zwischen den einzelnen Quantencomputern erhebliche klassische und quantenmechanische Ressourcen, was zu einem hohen Rechenaufwand und verlängerten Trainingszeiten führt. Um diesen Ansatz und seine Grenzen zu untersuchen, wird in dieser Arbeit ein DQML-Modell vorgestellt, das unter Verwendung des verteilten Quanten-Frameworks NetQASM implementiert wurde und dessen Architektur aus einem klassischen Server sowie zwei Quanten-Clients besteht. Das Modell wurde auf Datensätzen mit zwei und vier Merkmalen auf einem Quantennetzwerk-Simulator trainiert und evaluiert. Es erreichte eine vergleichbare Klassifikationsleistung wie ein zentralisiertes Quanten- Baseline-Modell. Um den Kommunikationsaufwand, der zu Trainingszeiten von 50 bis 500 Minuten pro Trainingsepisode führte, zu verringern, wurden Optimierungen an der Schaltungsarchitektur, der Erzeugung verschränkter Zustände und der verteilten Quantengatterausführung implementiert und evaluiert. Dadurch konnte die Laufzeit des Modells bei vergleichbarer Klassifikationsgenauigkeit um bis zu 60% reduziert werden.

Autor/in:

Kian Izadi

Betreuer:

Leo Sünkel, Michael Kölle, Thomas Gabor, Claudia Linnhoff-Popien

Studentische Abschlussarbeit | Veröffentlicht März 2025 | Copyright © QAR-Lab
Anfragen zu dieser Arbeit an die Betreuer


QUBO-Generierung für (MAX-)3SAT mittels generativer KI-Methoden

QUBO-Generierung für (MAX-)3SAT mittels generativer KI-Methoden

Abstract:

Das Erstellen von QUBOs für 3-SAT Formeln mittels Pattern QUBOs bringt einige Herausforderungen. Das generieren der Pattern QUBOs und die Erstellung der QUBO ist aufgrund des Brute-Force Ansatzes technisch aufwendig. In dieser Arbeit werden zwei Machine Learning Ansätze für die QUBO Generierung gegeben einer 3-SAT Formel getestet. Für das Encoden der Formeln und Matrizen wurden verschiedene Encodings untersucht. Zu den Formel Encodings zählen Vektor, Word2Vec und BERT. Auf QUBOs wurden latent Repräsentationen getestet. Als Startmodell dient ein conditional Autoencoder. Variationen wie 2-Encoder, vortrainierte Encoder basierend auf einem RESNET18 wurden ebenso getestet. Für 1 Klausel Formeln konnten akkurate QUBOs generiert werden, für untersuchte Formeln mit bis zu 4 Klauseln überschneiden sich die Energien der Lösung- und Restzustände. Letztens wurde ein conditional Diffusion Modell aufgesetzt und mit Vektor, Word2Vec und BERT Formel Embeddings auf 5 und 7 random Klauseln trainiert. Mit BERT Formel Embeddings konnten mit den erstellten QUBOs durchschnittlich die meisten Klauseln einer Formel erfüllt werden. Die Formeln blieben aber zum Großteil ungelöst. Mit maskierten Training für Diffusion kann das Training noch verbessert werden. Es konnte im Durchschnitt mit Masken generierten QUBOs eine Klausel mehr erfüllt werden. Dies verlangt als Input eine vordefinierte Maske in der Datengeneration. Als Hauptgrund für die Ergebnisse kann die spärliche QUBO Datenstruktur und die Schwierigkeit für das Erstellen einer 3-SAT Formel Kodierung verantwortlich gemacht werden.

Autor/in:

Philippe Wehr

Betreuer:

Sebastian Zielinski, Michael Kölle, Claudia Linnhoff-Popien

Studentische Abschlussarbeit | Veröffentlicht März 2025 | Copyright © QAR-Lab
Anfragen zu dieser Arbeit an die Betreuer


Speichereffiziente Quanten-Optimierung für das Traveling Salesman Problem via binäre Kodierung von gültigen Lösungen

Speichereffiziente Quanten-Optimierung für das Traveling Salesman Problem via binäre Kodierung von gültigen Lösungen

Abstract:

Das Traveling Salesperson Problem (TSP) ist eine klassische kombinatorische Optimierungsaufgabe mit zahlreichen Anwendungen in Logistik, Planung und Terminbestimmung. Quantenalgorithmen, insbesondere der Quantum Approximate Optimization Algorithm (QAOA), haben bereits Potenzial gezeigt, um solche NP-schweren Probleme zu lösen und könnten gegenüber klassischen Methoden Vorteile bieten. Bestehende Quantenverfahren für das TSP verwenden üblicherweise eine One-Hot-Kodierung, die für ein TSP mit n Städten O(n^2) Qubits erfordert und constraintspezifische Mixer wie den XY-Mixer einsetzt, um im gültigen Zustandsraum zu bleiben. Diese Ansätze sind jedoch ressourcenintensiv und stoßen bei steigender Qubit-Zahl schnell an praktische Grenzen. In dieser Masterarbeit wird eine neue Kodierung für das TSP unter Nutzung von QAOA vorgestellt, bei der Permutationen in Binärform abgebildet werden und der Qubit-Bedarf so auf O(n log2 n) sinkt. Die größte Schwierigkeit dieser Binärkodierung liegt darin, dass kein einfacher constraintspezifischer Mixer verfügbar ist, um während der Optimierung die Gültigkeit der Zustände sicherzustellen. Zur Lösung dieses Problems wird eine effizient realisierbare unitäre Transformation entwickelt, die jedem binär kodierten Rundweg einen eindeutigen Index zuweist. Durch das Hinzufügen von O(log2(n!)) zusätzlichen Qubits, welche jede mögliche TSP-Permutation in faktorieller Basis repräsentieren, entsteht eine kanonische Isomorphie zwischen Permutationen und faktoriellel kodierten Zahlen. Dadurch kann in diesem zusätzlichen Qubit-Bereich ein einfacher X-Mixer oder ein Grover-Mixer verwendet werden, sodass sich der Optimierungsprozess automatisch auf gültige Zustände beschränkt und die Nebenbedingungen während der gesamten Optimierung eingehalten werden. Dies ermöglicht eine schnellere Konvergenz in Richtung der optimalen Lösung. In Rahmen dieser Masterarbeit werden es drei Varianten dieser Kodierung untersucht: (1) eine direkte unitäre Transformation mithilfe einer vorberechneten Lookup-Tabelle, (2) ein Verfahren auf Basis von Quantenarithmetik sowie (3) ein reines Index-Verfahren, bei dem sowohl Kosten- als auch Mixer-Hamiltonoperatoren in [log2(n!)] Qubits kodiert werden, was allerdings zu tieferen Schaltkreisen führt. Numerische Experimente mit kleinen Problemgrößen zeigen die Realisierbarkeit dieser Ansätze und unterstreichen die möglichen Vorteile des platzsparenden Kodierungsschemas für praktische Quantenoptimierungsaufgaben.

Autor/in:

Viktoria Patapovich

Betreuer:

Jonas Stein, David Bucher, Claudia Linnhoff-Popien

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


Page 1 of 5