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.

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

References in corpus (2)

• 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