The difficulty of a generated instance is measured by the number of sweeps it takes for the simulated annealing (SA) algorithm (see Appendix ) summed over all runs, \(N_{tot}\) , to find the ground state configuration. A sweep is defined as an update over all the spins in the RBM, and a run is defined as a sequence of sweeps before the spin configuration is reset. The spins are reset if the solver fails to find the planted solution within the maximum allocated number of sweeps in a given run, which we denote as \(N_{sweep}\) . For each generated instance, the solver is run on a single core of an AMD EPYC 7401 24-core processor. Since we are only interested in the scaling behavior instead of the actual computation time required to solve the instances, we choose the number of sweeps as a difficulty measure over the walltime to reduce timing inconsistencies caused by various unrelated factors such as CPU idle time [1]}, inefficiency of the interpretive language [2]}, and parallel efficiency [3]}. If one wishes to obtain an estimate of the scaling behavior of the number of arithmetic operations required for SA to find the ground state, one can simply rescale the number of sweeps by a factor of \(n^2\)  [4]}, since the number of arithmetic operations required for a single SA iteration scales as \(O(n^2)\)  (see Appendix ).
