Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs

In this paper we study the performance of the quantum adiabatic algorithm on random instances of two combinatorial optimization problems, 3-regular 3-XORSAT and 3-regular max-cut. The cost functions associated with these two clause-based optimization problems are similar as they are both defined on 3-regular hypergraphs. For 3-regular 3-XORSAT the clauses contain three variables and for 3-regular max-cut the clauses contain two variables. The quantum adiabatic algorithms we study for these two problems use interpolating Hamiltonians which are amenable to sign-problem free quantum Monte Carlo and quantum cavity methods. Using these techniques we find that the quantum adiabatic algorithm fails to solve either of these problems efficiently, although for different reasons.

Figure 1

Factor graph of a small part of an instance of the 3-regular 3-XORSAT problem. In the full factor graph, each clause ($\square$) is connected to exactly three bits ($◯$) and each bit is connected to exactly three clauses, so there are no leaves and the graph closes up on itself.

Figure 2

First four energy levels of the interpolating Hamiltonian for a 16-bit instance of the 3-regular 3-XORSAT problem. The energy curves for this instance are close to being symmetric about $s=1/2$. Our duality transformation means that sending $s\to (1-s)$ we obtain the spectrum of the interpolating Hamiltonian for a different instance from the same ensemble, obtained by interchanging the clauses and bits.

Figure 3

Median minimum gap as a function of problem size of the 3-regular 3-XORSAT problem on a log-linear scale. The straight-line fit is good, indicating an exponential dependence which, in turn, leads to an exponential complexity of the QAA for this problem. Triangles indicate exact-diagonalization results while the circles are the results of QMC simulations.

Figure 4

Mean energy (averaged over 50 sample instances per size) of the 3-regular 3-XORSAT problem as a function of the adiabatic parameter $s$ for different sizes (QMC results) compared with the RS quantum cavity calculations. Because of the duality of the model, the true curve (averaged over all instances at a given value of $N$) is symmetric about $s=1/2$. The main panel shows a magnification near the symmetry point $s=1/2$. In the inset, the entire range is shown.

Figure 5

Magnetization along the $x$ axis, $M_x=N^{-1}{\sum }_i\langle {\sigma }_i^x\rangle$, as a function of the adiabatic parameter $s$ for the 3-regular 3-XORSAT problem. Results obtained both by QMC and the cavity method are shown. The latter indicates a sharp discontinuity at $s=s_c=1/2$. The slope of the QMC results at $s=1/2$ increases with increasing $N$, consistent with a discontinuity at $N=\infty$.

Figure 6

The spin-glass order parameter $q$ as defined in Eq. (14) as a function of the adiabatic parameter $s$ for the 3-regular 3-XORSAT problem. The rapid change for large sizes around $s=1/2$ indicates a first-order quantum phase transition at this value of $s$.

Figure 7

Extrapolation of the energy values as given by the QMC method (solid line) for different system sizes at $s=1/2$ as compared to the value given by the cavity method (which is for $N=\infty$) for the 3-regular 3-XORSAT problem, assuming a $1/N$ dependence. Extrapolating the QMC results to $N=\infty$ seems to give a result consistent with the cavity value.

Figure 8

The spin-glass order parameter $q^{\prime }$ obtained from Monte Carlo simulations, obtained from Eq. (15) as a function of the adiabatic parameter $s$ for the max-cut problem. Also shown is the value of $\overline{q}$ from the cavity calculation, which is defined differently, as discussed in the text. The inset shows a global view over the whole range of s, indicating large differences between the Monte Carlo and cavity calculations for large $s$. This may be due to the different ensembles used in the two calculations, as discussed in the text.

Figure 9

Magnetization along the $x$ direction, $M_x=N^{-1}{\sum }_i\langle {\sigma }_i^x\rangle$, as a function of the adiabatic parameter $s$ for the max-cut problem.

Figure 10

Energy as a function of the adiabatic parameter $s$ for the max-cut problem. The cavity results computed at inverse temperature $\beta =\frac{8}{s}$ are depicted by the dashed line. The bottom panel is a magnification of the region around the maximum, which illustrates the difference between the Monte Carlo and cavity results. Some of this difference may be due to the different ensembles used, as discussed in the text.

Figure 11

The gap to the first (even) excited state as a function of the adiabatic parameter $s$ for one of the $N=128$ instances of the max-cut problem, showing two distinct minima. The first, higher, minimum is close to $s\approx 0.36$ (the location of the order-disorder phase transition) while the other, lower minimum (global in the range) is well within the spin-glass phase.

Figure 12

Median minimum gap, on log-linear (main panel) and log-log (inset) scales, for the 3-regular max-cut problem for $s$ in the range 0.3 to 0.5. The straight-line fit on the log-linear scale (omitting the two smallest sizes) is a much better fit ($Q=0.57$) than that of the log-log scale ($Q=2.7\times {10}^{-3}$), in which the two smallest sizes are also omitted.

Figure 13

A stretched exponential fit to $A{e}^{-c{N}^{1/2}}$ for data for the median minimum gap for the 3-regular max-cut problem, omitting the two smallest sizes. The fit is satisfactory ($Q=0.31$).

Figure 14

Median minimum gap, on log-linear (main panel) and log-log (inset) scales, as a function of problem size for the 3-regular max-cut problem. Here, the minimum gaps were taken from the vicinity of the quantum phase transition at $s=s_c\simeq 0.36$ and are therefore not necessarily the global minima. The two fits indicate that in this case the polynomial dependence is more probable.

Figure 15

A scatter plot of the minimum gap for all 47 instances for size $N=160$ for the 3-regular max-cut problem. For the 19 instances with two minima in the range of $s$ studied, both are shown, that closer to $s=0.36$ being denoted “local,” and the smaller one, at larger $s$, being denoted “global.” Note the large scatter in the values of the minimum gap for different instances.