Quantum annealing for hard 2-satisfiability problems: Distribution and scaling of minimum energy gap and success probability

Physical Review A, vol. 105

Abstract

In recent years, quantum annealing has gained the status of being a promising candidate for solving various optimization problems. Using a set of hard 2-satisfiability (2-SAT) problems, consisting of problems of up to 18 variables, we analyze the scaling complexity of the quantum annealing algorithm and study the distributions of the minimum energy gap and the success probability. We extend the analysis of the standard quantum annealing Hamiltonian by introducing an additional term, the trigger Hamiltonian, which can be of two types: ferromagnetic and antiferromagnetic. We use these trigger Hamiltonians to study their influence on the success probability for solving the selected 2-SAT problems. We find that although the scaling of the runtime is exponential for the standard and modified quantum annealing Hamiltonians, the scaling constant in the case of adding the trigger Hamiltonians can be significantly smaller. Furthermore, certain choices for the trigger Hamiltonian and annealing times can result in a better scaling than that for simulated annealing. Finally, we also use the quantum annealers of D-Wave Systems Inc. to study their performance in solving the 2-SAT problems and compare it with the simulation results.

Authors 4

1. Vrinda Mehta Aachen

   Forschungszentrum Jülich · Jülich Supercomputing Centre · RWTH Aachen University

   Affiliation as printed

   Institute for Advanced Simulation, Jülich Supercomputing Centre, Forschungszentrum Jülich, 52425 Jülich, Germany

   RWTH Aachen University, 52056 Aachen, Germany

2. Fengping Jin

   Forschungszentrum Jülich · Jülich Supercomputing Centre

   Affiliation as printed

   Institute for Advanced Simulation, Jülich Supercomputing Centre, Forschungszentrum Jülich, 52425 Jülich, Germany

3. Hans A. De Raedt

   University of Groningen · Forschungszentrum Jülich · Jülich Supercomputing Centre · Zernike Institute for Advanced Materials

   Affiliation as printed

   Institute for Advanced Simulation, Jülich Supercomputing Centre, Forschungszentrum Jülich, 52425 Jülich, Germany

   Zernike Institute for Advanced Materials, University of Groningen, Nijenborgh 4, 9747 AG Groningen, Netherlands

4. Kristel F. L. Michielsen Aachen

   Forschungszentrum Jülich · Jülich Aachen Research Alliance · Jülich Supercomputing Centre · RWTH Aachen University

   Affiliation as printed

   Center for Simulation and Data Science, Jülich Aachen Research Alliance, 52425 Jülich, Germany

   Institute for Advanced Simulation, Jülich Supercomputing Centre, Forschungszentrum Jülich, 52425 Jülich, Germany

   RWTH Aachen University, 52056 Aachen, Germany