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

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.

Figure 1

Median-normalized minimum energy gap distributions $\mathcal{P}\left(x\right)dx$ for (a) the standard quantum annealing Hamiltonian (1), (b) the Hamiltonian (8) with the ferromagnetic trigger Hamiltonian, and (c) the Hamiltonian (8) with the antiferromagnetic trigger Hamiltonian, for the problem set with $N=18$, where $x=\mathrm{\Delta }/{\mathrm{\Delta }}_m$, with ${\mathrm{\Delta }}_m$ the median minimum energy gap of the set.

Figure 2

Median-normalized minimum energy gap distributions $\mathcal{P}\left(x\right)dx$ for the quantum annealing Hamiltonian given by (a) and (b) Eq. (1), (c) and (d) Eq. (8) with the ferromagnetic trigger Hamiltonian, and (e) and (f) Eq. (8) with the antiferromagnetic trigger Hamiltonian, for problem sets with (a), (c), and (e) $N=16$ and (b), (d), and (f) $N=17$, where $x=\mathrm{\Delta }/{\mathrm{\Delta }}_m$, with ${\mathrm{\Delta }}_m$ the median minimum energy gap of the set.

Figure 3

Scaling of median minimum energy gaps for the quantum annealing Hamiltonian given by Eq. (1) (squares), the quantum annealing Hamiltonian given by Eq. (8) with the ferromagnetic trigger Hamiltonian (circles), and the quantum annealing Hamiltonian given by Eq. (8) with the antiferromagnetic trigger Hamiltonian (triangles).

Figure 4

Deciles for the minimum energy gaps for the quantum annealing Hamiltonian given by (a) Eq. (1), (b) Eq. (8) with the ferromagnetic trigger Hamiltonian, and (c) Eq. (8) with the antiferromagnetic trigger Hamiltonian.

Figure 5

Success probability distributions obtained for the quantum annealing algorithm using (a)–(c) the Hamiltonian (1), (d)–(f) the Hamiltonian (8) with the ferromagnetic trigger Hamiltonian, and (g)–(i) the Hamiltonian (8) with the antiferromagnetic trigger Hamiltonian, for the problem set with $N=18$ for (a), (d), and (g) $T_A=10$; (b), (e), and (h) $T_A=100$; and (c), (f), and (i) $T_A=1000$.

Figure 6

Success probability distributions obtained for the quantum annealing given by (a)–(c) Eq. (1), (d)–(f) Eq. (8) with the ferromagnetic trigger Hamiltonian, and (g)–(i) Eq. (8) with the antiferromagnetic trigger Hamiltonian, for the problem set with $N=17$ for (a) and (d) $T_A=10$, (b) and (e) $T_A=100$, and (c) and (f) $T_A=1000$.

Figure 7

Scaling of the median ${\mathcal{T}}_{99}$ for the quantum annealing Hamiltonian given by (a) Eq. (1), (b) Eq. (8) with the ferromagnetic trigger Hamiltonian, and (c) Eq. (8) with the antiferromagnetic trigger Hamiltonian, for $T_A=10$ (squares), $T_A=100$ (circles), and $T_A=1000$ (triangles).

Figure 8

Deciles for ${\mathcal{T}}_{99}$ for the quantum annealing Hamiltonian given by (a)–(c) Eq. (1), (d)–(f) Eq. (8) with the ferromagnetic trigger Hamiltonian, and (g)–(i) Eq. (8) with the antiferromagnetic trigger Hamiltonian for (a), (d), and (g) $T_A=10$; (b), (e), and (h) $T_A=100$; and (c), (f), and (i) $T_A=1000$.

Figure 9

Success probability distributions obtained using (a)–(c) DW2000Q and (d)–(f) DWAdv for the problem set with $N=18$ for (a) and (d) $T_A=4\mu \text{s}$, (b) and (e) $T_A=20\mu \text{s}$, and (c) and (f) $T_A=100\mu \text{s}$.

Figure 10

Success probability distributions obtained using (a)–(c) DW2000Q and (d)–(f) DWAdv for the problem set with $N=17$ for (a) and (d) $T_A=4\mu \text{s}$, (b) and (e) $T_A=20\mu \text{s}$, and (c) and (f) $T_A=100\mu \text{s}$.

Figure 11

Scaling of the median ${\mathcal{T}}_{99}$ for the cases with a native embedding on (a) DW2000Q and (b) DWAdv for $T_A=4\mu \text{s}$ (squares), $T_A=20\mu \text{s}$ (circles), and $T_A=100\mu \text{s}$ (triangles).

Figure 12

Deciles for the ${\mathcal{T}}_{99}$ for the cases with a native embedding on (a)–(c) DW2000Q and (d)–(f) DWAdv for (a) and (d) $T_A=4\mu \text{s}$, (b) and (e) $T_A=20\mu \text{s}$, and (c) and (f) $T_A=100\mu \text{s}$.