Entropic barriers as a reason for hardness in both classical and quantum algorithms

We study both classical and quantum algorithms to solve a hard optimization problem, namely 3-XORSAT on 3-regular random graphs. By introducing a new quasi-greedy algorithm that is not allowed to jump over large energy barriers, we show that the problem hardness is mainly due to entropic barriers. We study, both analytically and numerically, several optimization algorithms, finding that entropic barriers affect in a similar way classical local algorithms and quantum annealing. For the adiabatic algorithm, the difficulty we identify is distinct from that of tunneling under large barriers, but does, nonetheless, give rise to exponential running (annealing) times.

Figure 1

Schematic picture for the energy relaxation in hard optimization problems. On short times the energy relaxes to a threshold value, while the ground state (solution) is reached only for times growing exponentially with the system size. The first regime can be described by ordinary differential equations taking the large $N$ limit at $t/N$ fixed, while the second requires the estimation of rare and large fluctuations.

Figure 2

Simulated annealing is not able solve the 3-regular 3-XORSAT problem, since it converges in the long time limit to a positive energy (close to the marginal energy $e_{\text{marg}}$). The four curves have annealing rates $\mathrm{\Delta }T={10}^{-3},{10}^{-4},{10}^{-5},{10}^{-6}$ (from top to bottom). The blue (dark gray) curve represents the energy above the dynamical transition in the large $N$ limit.

Figure 3

Evolution of the energy for several greedy versions ($w_1=0$) of the algorithm. Points are numerical data and lines are the analytic description.

Figure 4

The actual evolution of fraction of variables in a greedy version ($w_1=0$) of the algorithm (data points) are well described by the analytic solution (full curves). The algorithm stops when $f_2=f_3=0$.

Figure 5

Evolution of the energy and fraction of variables during the WalkSAT algorithm. The analytic description of the relaxation to the threshold energy is almost perfect.

Figure 6

Evolution of the energy for WalkSAT and several (quasi-)greedy versions of the algorithm. The vector of weights $(w_0,w_1,w_2,w_3)$ appears in the legend. The analytic description under the assumption of lack of correlations is reported with a full curve and fails to describe the algorithms at the lowest energies, when correlations arise.

Figure 7

Comparison to the numerics for 3-XORSAT. The vertical axis is the logarithm of the probability of solution in linear time divided by $N$. The black dots are the numerical data reported in [52] and the blue (lower) line is the analytic approximation derived in that reference, based on large deviation theory. The red (upper) line is our approximation [see Eq.(15)].

Figure 8

Equilibrium distribution of the density of UNSAT clauses ${\alpha }_u$ for the Fokker-Planck equation (12). A solution is found when a rare fluctuation reaches the value ${\alpha }_u=0$, which occurrs with probability exponentially small in $N$.

Figure 9

Mean times to reach a solution measured as spin flips per variable. The exponential growth of the time to reach a solution by the quasi-greedy version of the algorithm has a rate ${\mu }_{\text{QG}}\approx 0.0835$, much smaller than the one of WalkSAT and comparable to the one of “parallel tempering” (which is however much slower because of the prefactor).

Figure 10

Annealing time $T$ as a function of instance size $N$ and solution probability $\varepsilon$. Every dot corresponds to an instance, with darker color indicating a more degenerate ground state. Notice how the rate $\mu$ is insensitive to the target probability, as expected from the restart argument given in the main text. The red line is a linear fit performed on the median value of the annealing time, using the standard deviation of $log\left(T\right)$ as error bar.

Figure 11

Lowest 30 levels in the spectrum as a function of transverse field strength $t/T$ for an instance with nondegenerate ground state. Compare to Fig. 20 in [48].

Figure 12

Lowest 30 levels in the spectrum as a function of transverse field strength $t/T$ for an instance with eightfold degenerate ground state.

Figure 13

Mean energy of the stopping configurations for the greedy dynamics as a function of the ratio $w_3/w_2$.

Figure 14

Entropy $S_0$ of blocked configurations as a function of the energy $\rho$.

Figure 15

The size of the basin of attraction grows exponentially with the size and the depth of the energy minimum. Finite size effects are evident only for the lowest energies.

Figure 16

A schematic picture of the energy landscape in the 3-regular 3-XORSAT problem. Most energy minima (including the solutions to the problem) have a basin of attraction, which is likely to be connected to the energy level $e_{\text{max}}$ where the dynamics starts. However the entropic barrier makes very unlikely to choose the pit leading to a solution.

Figure 17

Combining the entropy of blocked configurations $S_0$ and the log size of the basins of attractions $b$ we can compute the rate of the large deviation probability of finding a block configuration of a given energy [shifted by $log\left(2\right)$ because it is not normalized]. The maximum is achieved at an energy close to 0.11 (marked by a vertical-dotted line) where the greedy algorithm converges in the large $N$ limit.