We introduce a new input class called clause problems, that can be used to study local constraint structures, which occur in inputs translated from general NP-hard problems to the D-Wave native topology. We describe a small family of clause problems that are contrived to create significant challenges for two classical competition solvers, simulated annealing (SA) and the Hamze–de Frietas–Selby solver (HFS). We identify key properties of these inputs that lead to poor performance by the classical solvers, and consider whether these properties might naturally arise in problems from real-world applications.

DOWNLOAD