A Scalable and Tunable Approach to Plant Spin-Glass Solutions

We present an efficient, scalable approach that allows one to construct spin-glass instances with planted solutions and tunable hardness. Here, we demonstrate our method for square lattices. Frustrated cycles are constructed via corner-sharing spins on lattice building blocks such that they share a common local ground state, which guarantees that the ground state energy of the entire problem is known a priori. Using population annealing Monte Carlo, we compare the computational complexity of planted problems across a multiplicity of instance classes that results from the numerous ways in which the frustrated cycles can be chosen. Our method offers significant advantages over previous approaches for planting solutions in that it is easy to implement, the problems have tunable hardness, and it requires no computational overhead.