Title: Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods,
Abstract: We present and apply a general-purpose, multi-start algorithm for improving
the performance of low-energy samplers used for solving optimization problems.
The algorithm iteratively fixes the value of a large portion of the variables
to values that have a high probability of being optimal. The resulting problems
are smaller and less connected, and samplers tend to give better low-energy
samples for these problems. The algorithm is trivially parallelizable, since
each start in the multi-start algorithm is independent, and could be applied to
any heuristic solver that can be run multiple times to give a sample. We
present results for several classes of hard problems solved using simulated
annealing, path-integral quantum Monte Carlo, parallel tempering with
isoenergetic cluster moves, and a quantum annealer, and show that the success
metrics as well as the scaling are improved substantially. When combined with
this algorithm, the quantum annealer's scaling was substantially improved for
native Chimera graph problems. In addition, with this algorithm the scaling of
the time to solution of the quantum annealer is comparable to the Hamze--de
Freitas--Selby algorithm on the weak-strong cluster problems introduced by
Boixo et al. Parallel tempering with isoenergetic cluster moves was able to
consistently solve 3D spin glass problems with 8000 variables when combined
with our method, whereas without our method it could not solve any.