How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs

Abstract

A recent 3-XORSAT challenge required to minimize a very complex and rough energy function, typical of glassy models with a random first order transition and a golf course like energy landscape. We present the ideas beyond the quasi-greedy algorithm and its very efficient implementation on GPUs that are allowing us to rank first in such a competition. We suggest a better protocol to compare algorithmic performances and we also provide analytical predictions about the exponential growth of the times to find the solution in terms of free-energy barriers.

arXiv comment7 pages, 7 figure, EPL format + SM (2 pages)

References in corpus (13)

• Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
• The Bethe lattice spin glass revisited
• Spin-Glass Theory for Pedestrians
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Architectural considerations in the design of a superconducting quantum annealing processor
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• A ferromagnet with a glass transition
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Equation Planting: A Tool for Benchmarking Ising Machines
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Circumventing spin glass traps by microcanonical spontaneous symmetry breaking

Cited by in corpus (9)

• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• All-to-all reconfigurability with sparse and higher-order Ising machines
• Simulated bifurcation for higher-order cost functions
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Energy landscapes of combinatorial optimization in Ising machines
• Optimal control of a quantum sensor: A fast algorithm based on an analytic solution
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• The solution space structure of planted constraint satisfaction problems with growing domains
• Tensor networks for $p$-spin models