Iterative classical superadiabatic algorithm for combinatorial optimization
Takuya Hatomura · Journal of Physics A Mathematical and Theoretical · 2020
Abstract We consider a classical and superadiabatic version of an iterative quantum adiabatic algorithm to solve combinatorial optimization problems. This algorithm is deterministic because it is based on purely classical dynamics, that is, it does not rely on any stochastic approach to mimic quantum dynamics. Moreover, we use the exact shortcut to adiabaticity for stationary states of classical spin systems, and thus the final state of an annealing process does not depend on the annealing time. We apply this algorithm to a certain class of hard instances of the 3-SAT problem, which is specially hard for purely adiabatic algorithms. We find that more than 90% of such 64-bits hard instances, which we try to solve, can be resolved by a few iteration. Our approach can also be used to analyze properties of instances themselves apart from stochastic uncertainty and shortage of adiabaticity.