Comparison of D-Wave Quantum Annealing and Classical Simulated Annealing
  for Local Minima Determination
  Restricted Boltzmann Machines trained with different numbers of iterations
were used to provide a diverse set of energy functions each containing many
local valleys (LVs) with different energies, widths, escape barrier heights,
etc. They were used to verify the previously reported possibility of using the
D-Wave quantum annealer (QA) to find potentially important LVs in the energy
functions of Ising spin glasses that may be missed by classical searches. For
classical search, extensive simulated annealing (SA) was conducted to find as
many LVs as possible regardless of the computational cost. SA was conducted
long enough to ensure that the number of SA-found LVs approaches that and
eventually significantly exceeds the number of the LVs found by a single call
submitted to the D-Wave. Even after a prohibitively long SA search, as many as
30-50% of the D-Wave-found LVs remained not found by the SA. In order to
establish if LVs found only by the D-Wave represent potentially important
regions of the configuration space, they were compared to those that were found
by both techniques. While the LVs found by the D-Wave but missed by SA
predominantly had higher energies and lower escape barriers, there was a
significant fraction having intermediate values of the energy and barrier
height. With respect to most other important LV parameters, the LVs found only
by the D-Wave were distributed in a wide range of the parameters' values. It
was established that for large or small, shallow or deep, wide or narrow LVs,
the LVs found only by the D-Wave are distinguished by a few-times smaller size
of the LV basin of attraction (BoA). Apparently, the size of the BoA is not or
at least is less important for QA search compared to the classical search,
allowing QA to easily find many potentially important (e.g., wide and deep) LVs
missed by even prohibitively lengthy classical searches.
