Nonequilibrium Monte Carlo for unfreezing variables near computational phase transitions

Sampling highly complex cost/energy functions over discrete variables is at the heart of many open problems across different scientific disciplines and industries. The major obstacle is the emergence of many-body effects among certain interacting variables leading to critical slowing down or collective freezing for known stochastic local search strategies. An exponential computational effort is generally required to unfreeze such variables and explore other unseen regions of the configuration space. Here, we introduce a quantum-inspired family of nonlocal Nonequilibrium Monte Carlo (NMC) algorithms by developing an adaptive gradient-free strategy that can efficiently learn key instance-wise geometrical features of the cost function. That information is employed on the fly to construct spatially inhomogeneous thermal fluctuations for collectively unfreezing variables at various length scales, circumventing costly exploration versus exploitation trade-offs. We apply our algorithm to two of the most challenging combinatorial optimization problems: random k-satisfiability (k-SAT) near the computational phase transitions and Quadratic Assignment Problems (QAP). We observe significant speedup over both generic local stochastic solvers, such as Adaptive Parallel Tempering (APT), and certain specialized deterministic solvers. In particular, for the 10% of hardest random 4-SAT instances we observe two orders of magnitude improvements in the quality of solutions over state-of-the-art specialized solvers known as Survey Propagation (SP) and Backtracking Survey Propagation (BSP).