Book/Dissertation / PhD Thesis

FZJ-2024-03411

http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png Quantum annealing and its variants: Application to quadratic unconstrained binary optimization

Mehta, V. (Corresponding author)FZJ*

2024
Forschungszentrum Jülich GmbH Zentralbibliothek, Verlag Jülich
ISBN: 978-3-95806-755-4

This record in other databases:

Please use a persistent id in citations: urn:nbn:de:0001-20241209125135062-9549579-4  doi:10.34734/FZJ-2024-03411

Abstract: 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 binaryoptimization (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.

Note: Dissertation, RWTH Aachen University, 2023

---

Contributing Institute(s):

1. Jülich Supercomputing Center (JSC)

Research Program(s):

1. 5111 - Domain-Specific Simulation & Data Life Cycle Labs (SDLs) and Research Groups (POF4-511) (POF4-511)

Appears in the scientific report 2024

---

Database coverage:
;

---