Increase of degeneracy improves the performance of the quantum adiabatic algorithm

We propose a strategy to improve the performance of the quantum adiabatic algorithm (QAA) on an NP-hard (nondeterministic-polynomial-time-hard) problem exact cover, by increasing the ground-state degeneracy of the problem Hamiltonian. Our strategy is based on the empirical finding that for the QAA the difficulty of random instances decreases with the degeneracy of the ground state. We increase the degeneracy by adding extra qubits to form additional clauses. Our numerical results show that on average our strategy can provide an increase in the minimum gap size along the linear interpolation path of Hamiltonian for both easy and difficult instances. The success probability at fixed total evolution time is thus increased.

Figure 1

Example of definition of minimum gap. In both cases, the problem Hamiltonian has 2-fold degenerate ground state ($D=2$) and we plot the three lowest eigenstates. The subpanels are the zoom in of the minimum gap point.

Figure 2

(a) The SAT probability with clause density for $n=10/20/50$ variables. Each data point of probability is estimated over 100/500 random samples, as indicated in the legend. (b) Median $1/{\Delta }^2$ with the clause density. The UNSAT does not have large average empirical difficulty. We sample 1000 instances of $n=10$ fixed for each clause density. The dashed line in subfigures (a) and (b) indicates the position of phase transition at $m/n\sim 0.79$. (c) Correlation of $1/{\Delta }^2$ and degeneracy of ground state of $H_P$ ($n=10$ fixed); each data point is the median of 1000 random instances. The subpanel is the corresponding log-log plot, which also includes the minimum and maximum $1/{\Delta }^2$.

Figure 3

(a) Statistics of minimum gap for 200,000 instances with nondegenerate ground states. The joint distribution over $s,{\Delta }_1$. (b1) and (b2) Marginal distribution of each variable. We sample from the 20,0000 instances with gap size in [0,0.5] uniformly to study how adding degeneracy will change the gap size. (c) Average gap change ${\Delta }_2-{\Delta }_1$ and original gap ${\Delta }_1$. Every data point is the average of an interval of $\pm 0.025$, and the error bar is $\pm$ standard deviation in each interval. The subpanel shows the number of samples averaged over; it is fixed as 150 except the rare small gap cases. (d) The distribution of gap change ${\Delta }_2-{\Delta }_1$; the percentage above zero is around $0.78$.

Figure 4

(a) For total running time $T=80$, average success probability change $p_2-p_1$ and original success probability $p_1$. Every data point is the average of an interval of $\pm 0.05$. The error bar is $\pm$ standard deviation. The subpanel shows the number of samples averaged over; at small $p_1$ the number of sample is smaller. (b) The distribution of success probability change $p_2-p_1$. The percentage above zero is around $0.86$. (c) For total running time $T=10$, average success probability change $p_2-p_1$ and original success probability $p_1$. Every data point is the average of an interval of $\pm 0.025$. The error bar is $\pm$ standard deviation. The subpanel shows the number of samples averaged over. At small $p_1$ the number of samples is smaller. (d) The distribution of success probability change $p_2-p_1$. The percentage above zero is around $0.62$.

Figure 5

Correlation between the change of gap ${\Delta }_2^2/{\Delta }_1^2$ and the change of success probability $p_2/p_1$ for cases with $p_1<0.5$. Total running time $T=80$.