Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods

摘要

We present and apply a general-purpose, multi-start algorithm for improvingthe performance of low-energy samplers used for solving optimization problems.The algorithm iteratively fixes the value of a large portion of the variablesto values that have a high probability of being optimal. The resulting problemsare smaller and less connected, and samplers tend to give better low-energysamples for these problems. The algorithm is trivially parallelizable, sinceeach start in the multi-start algorithm is independent, and could be applied toany heuristic solver that can be run multiple times to give a sample. Wepresent results for several classes of hard problems solved using simulatedannealing, path-integral quantum Monte Carlo, parallel tempering withisoenergetic cluster moves, and a quantum annealer, and show that the successmetrics as well as the scaling are improved substantially. When combined withthis algorithm, the quantum annealer's scaling was substantially improved fornative Chimera graph problems. In addition, with this algorithm the scaling ofthe time to solution of the quantum annealer is comparable to the Hamze--deFreitas--Selby algorithm on the weak-strong cluster problems introduced byBoixo et al. Parallel tempering with isoenergetic cluster moves was able toconsistently solve 3D spin glass problems with 8000 variables when combinedwith our method, whereas without our method it could not solve any.