Universität zu Köln

Diese Dissertation stellt zwei Hauptprojekte vor, die sich mit hybriden Quanten-Suchalgorithmen befassen. Das erste, Particle-Guided Grover's Search, wendet Bayessche Inferenz auf die Quanten-Suche an, wenn die Anzahl der Loesungen a priori unbekannt ist. Es beginnt mit einer A-Priori-Verteilung, die unsere anfaenglichen Glauben ueber die tatsaechliche Anzahl von Loesungen im Suchraum kodiert, und aktualisiert diese Glauben rekursiv unter Verwendung der Bayesschen Inferenz. Messergebnisse der Quantensuche, die keine Loesung liefern, werden als Evidenz interpretiert, die die Bayessche Aktualisierung bestimmen, um die optimale Anzahl von Grover-Iterationen fuer nachfolgende Runden zu bestimmen. Dieser Ansatz nutzt Partikelfilterung -- eine Bayessche Filtertechnik --, um zu vermeiden, dass bei jedem Schritt die gesamte A-Prior-Verteilung explizit gespeichert werden muss. Anstatt O(N) an Speicher zu benoetigen, zieht die Methode eine Menge von Partikeln aus der A-Priori-Verteilung und aktualisiert deren zugehoerige Gewichte jedes Mal, wenn die Quantensuche erfolglos ist. Die Partikelfilterung bietet auerdem den Vorteil, dass sie Informationen aus allen vorherigen erfolglosen Suchvorgaengen beruecksichtigt und nicht nur aus dem letzten. Die Leistung des Algorithmus wird mit der einer frueheren Resultat in der Literatur verglichen. Das zweite Projekt, Runtime--Coherence Trade-offs for Hybrid SAT Solvers, konzentriert sich auf eine Klasse hybrider k-SAT-Solver. Diese Solver basieren auf einer bekannten Random-Walk-Technik namens Schoenings Algorithmus, die zwei Zufallsquellen verwendet, um eine lokale Suche ueber den Raum aller Zuweisungen eines k-SAT-Problem durchzufuehren. In diesem Projekt gehen wir davon aus, dass diese Zufallsquellen in einer langen Bitkette kodiert sind, sodass der Random Walk als deterministische Funktion interpretiert werden kann, die jede Bitkette entweder auf 0 oder 1 abbildet, je nachdem, ob der Walk erfolgreich eine zufriedenstellende Zuweisung findet. Diese funktionale Perspektive ermoeglicht es uns, die Frage zu stellen: Angesichts einer Begrenzung der Kohrenzzeit eines Quantencomputers, welchen Teil der Bitfolge sollten wir kohaerent durchsuchen und welchen Teil sollten wir der klassischen Suche ueberlassen? Wir gehen dieser Frage nach, indem wir eine Familie von Hybridalgorithmen namens partielle Groverisierungen einfuehren, die Quanten- und klassische Ressourcen strategisch kombinieren. Wir analysieren die Laufzeitleistung dieser Familie als Funktion der verfuegbaren Quantenkohaerenzzeit. Die Ergebnisse dieser Arbeit wurden in IEEE Transactions on Quantum Engineering veroeffentlicht.

German