Quantum annealing and its variants: application to quadratic unconstrained binary optimization

Mehta, Vrinda; Di Vincenzo, David; Michielsen, Kristel Francine

doi:42747

Quantum annealing and its variants: application to quadratic unconstrained binary optimization

Mehta, Vrinda^RWTH*

2023

Verantwortlichkeitsangabevorgelegt von Vrinda Mehta, M.Sc.

ImpressumAachen : RWTH Aachen University 2023

Umfang1 Online-Ressource : Illustrationen, Diagramme

Dissertation, RWTH Aachen University, 2023

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Michielsen, Kristel Francine (Thesis advisor)^RWTH* ; Di Vincenzo, David (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2023-11-06

Online
DOI: 10.18154/RWTH-2023-10741
URL: https://publications.rwth-aachen.de/record/973357/files/973357.pdf

Einrichtungen

Thematische Einordnung (Klassifikation)
DDC: 530

Kurzfassung
In dieser Arbeit untersuchen wir die Leistung der numerischen Implementierung von Quanten-Annealing sowie der physikalischen Quanten-Annealing-Systeme von D-Wave Quantum Systems Inc. zur Lösung von 2-Satisfiability (2-SAT) und anderen quadratischen uneingeschränkten binären Optimierungsproblemen (QUBO).Um die Eignung von Quanten-Annealing für die Lösung dieser Probleme zu beurteilen, verwenden wir drei Hauptmetriken: Die Wahrscheinlichkeit, dass der Algorithmus das Problem löst, seine Fähigkeit, alle Lösungen für das Problem zu finden, falls es mehr als eine Lösung gibt, und die Skalierung der Zeit bis zur Lösung in Abhängigkeit von der Problemgröße. Dabei vergleichen wir die Leistung des numerisch simulierten idealen Quanten-Annealings mit seiner tatsächlichen physikalischen Umsetzung. Wir stellen fest, dass der ideale Standard-Quanten-Annealing-Algorithmus die in dieser Arbeit betrachteten 2-SAT-Problemsätze lösen kann, wenn auch mit einer geringen Erfolgswahrscheinlichkeit für schwierige Probleme, und dass er Stichproben über die entarteten Grundzustände der 2-SAT-Probleme mit mehreren erfüllenden Zuordnungen in Übereinstimmung mit der Störungstheorie liefern kann. Allerdings führt der ideale Standard-Annealing-Algorithmus im Grenzwert langer Zeiten zu einer schlechteren Skalierung der Zeit bis zur Lösung als selbst die einfache Aufzählung aller möglichen Zustände. Andererseits stellen wir fest, dass Rauschen und Temperatureffekte eine aktive Rolle bei der Entwicklung des Systemzustands auf den D-Wave-Quanten-Annealern spielen. Diese Systeme können einen Großteil der untersuchten Probleme mit einer relativ großen Erfolgswahrscheinlichkeit lösen, und die Skalierung der Zeit bis zur Lösung ist, wenn auch stets exponentiell wachsend in der Systemgröße deutlich verbessert. Als Nächstes führen wir mit Hilfe von Simulationen zwei Modifikationen in den Standard-Quanten-Annealing-Algorithmus ein und messen die Leistung der modifizierten Algorithmen. Die Modifikationen sind das Hinzufügen eines Trigger-Hamiltonians zum Standard-Quanten-Annealing-Hamiltonian oder die Änderung des Anfangs-Hamiltonians im Annealing-Hamiltonian. Wir wählen den Trigger-Hamiltonian so, dass er entweder ferromagnetische oder antiferromagnetische transversale Kopplungen hat, während die zusätzlichen Kopplungen höherer Ordnung, die dem typischerweise gewählten Anfangs-Hamiltonians hinzugefügt werden, ferromagnetisch sind. Wir stellen fest, dass diese Modifikationen zu signifikanten Verbesserungen in der Leistung des Quanten-Annealing-Algorithmus führen können, auch wenn das Skalierungsverhalten immer noch exponentiell ist.

In this thesis, we study the performance of the numerical implementation of quantum annealing, as well as of physical quantum annealing systems from D-Wave Quantum Systems Inc., for solving 2-Satisfiability (2-SAT) and other quadratic unconstrained binary optimization (QUBO) problems. For gauging the suitability of quantum annealing for solving these problems, we use three main metrics: the probability of the algorithm to solve the problem, its ability to find all the solutions to the problem if the problem has more than one solution, and the scaling of the time to solution as a function of the problem size. In doing so, we compare the performance of the numerically simulated ideal quantum annealing with its actual physical realization. We find that the ideal, standard quantum annealing algorithm can solve the sets of 2-SAT problems considered in this work, even if with a low success probability for hard problems, and can sample the degenerate ground states of the 2-SAT problems with multiple satisfying assignments in accordance with perturbation theory. However, in the long annealing time limit, the ideal standard annealing algorithm leads to a scaling of the time to solution that is worse compared to even the simple enumeration of all the possible states. On the other hand, we find noise and temperature effects to play an active role in the evolution of the state of the system on the D-Wave quantum annealers. These systems can solve a majority of the studied problems with a relatively large success probability, and the scaling of the time to solution, though still growing exponentially in the system size, is significantly improved.Next, by means of simulations, we introduce two modifications in the standard quantum annealing algorithm, and gauge the performance of the modified algorithms. These modifications are the addition of a trigger Hamiltonian to the standard quantum annealing Hamiltonian, or a change in the initial Hamiltonian of the annealing Hamiltonian. We choose the trigger Hamiltonian to have either ferromagnetic or antiferromagnetic transverse couplings, while the additional higher-order couplings added to the typically chosen initial Hamiltonian are ferromagnetic. We find that these modifications can lead to significant improvements in the performance of the annealing algorithm, even if the scaling behavior is still exponential.

OpenAccess:
PDF
(additional files)