Improved fair sampling of ground states in Ising spin glasses

Verifying that an optimization approach can sample all solutions that minimize a Hamiltonian is a stringent test for any newly-developed algorithm. While most solvers easily compute the minimum of a cost function for small to moderate input sizes, equiprobable sampling of all ground-state configurations (within Poissonian fluctuations) is much harder to obtain. Most notably, methods such as transverse-field quantum annealing fail in passing this test for certain highly-degenerate problems. Here we present an attempt to sample ground states for Ising spin glasses based on a combination of low-temperature parallel tempering Monte Carlo combined with the cluster algorithm by Houdayer. Because the latter is rejection free and obeys details balance, the ground-state manifold is efficiently sampled. We illustrate the approach for Ising spin glasses on the D-Wave Two quantum annealer topology, known as the Chimera graph, as well as two-dimensional Ising spin glasses.