Optimization by quantum annealing: Lessons from hard satisfiability problems

The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem $(N=10000)$. The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.

Figure 1

The comparison between optimal linear-schedule classical (CA) and quantum annealing (QA) for a 3-SAT problem with $N={10}^4$ and $\alpha =M∕N=4.24$. CA always performs better than QA simulated with $P=50$ Trotter replicas. The average performance of linear QA is worse than that of CA, even if an improvement in the results can be obtained by introducing global moves (G) and by increasing $P$. (In the inset the final average energy found by QA after 2000 iterations for increasing $P$ is plotted and compared with the average result of a CA of the same length, dashed line.) The solid triangles are the data obtained by the field-cycling QA hybrid strategy described in Sec. 7.

Figure 2

The energy evolution during quantum annealing, compared to simulated annealing. The variation of the averages $⟨E⟩$ (average best replica) and $⟨⟨E⟩⟩$ (average of the average replica) is shown as a function of the simulation time, for a set of experiments with $P=50$ and 2000 annealing iterations. The inset shows the time-dependent value of the coupling $J_{\Gamma }$. Three different regimes can be distinguished, which will be called quenching, search (driven by quantum fluctuations), and target selection.

Figure 3

The autocorrelation function $K(t^{*},\tau )$ for CA. The different curves represent the decay with $\tau$ of several fixed-simulation-time snapshots of the autocorrelation function for a CA experiment; $t^{*}$ is varying in the plot at fixed intervals between 200 and 2000, from bottom to top.

Figure 4

The autocorrelation function $K(t^{*},\tau )$ for QA. The different curves represent the decay with $\tau$ of several fixed-simulation-time snapshots of the autocorrelation function, for QA experiments with and without global moves; $t^{*}$ is varying at fixed intervals between 200 and 2000, from bottom to top. The target selection phase is characterized by a complete collapse into a single configuration, while damped classical oscillations around the equilibrium position are allowed if global moves are introduced.

Figure 5

The local geometry of the visited regions of the phase space is probed by counting the fraction of directions in which the energy variation is negative, null, or positive. Although both CA and QA get trapped in a local minimum, the quantum evolution tends to visit “valleys” that, at the same energies as CA, are more flat and have a larger number of downhill directions.

Figure 6

The energy evolution during a field-cycling hybrid strategy. The strength of the transverse coupling $J_{\Gamma }$ is varied cyclically between the values 0.001 and 5, by adjusting the value of the magnetic field. The effective temperature $T_q$ is kept constant during each field ramp, but is reduced in a stepwise way among different ramps, from the initial value of 0.3 down to 0.05. Each ascending field-ramp unfreezes the system from a previously reached target state and, after a short transient regime, a new search phase is entered. The starting plateaus have energy values increasingly smaller than the quenching level at the new simulation temperature (the arrows in the graphs indicate the quenching level and the hybrid strategy plateau at a given value of the temperature). Each new target state has a better energy than the preceding one, and the final average energy is better than the value reachable by large classical fluctuations.