Benchmarking using Frustrated Ising Problems with Planted Solutions

We introduce a method for generating families of benchmark problems that have a certain degree of tunable ``hardness,'' achieved by adjusting the amount of frustration. We construct such frustrated problems around ``planted solutions,'' representing a known ground state configuration. We construct such problems on the Chimera graph and use them to benchmark various optimization algorithms: simulated annealing (SA), simulated quantum annealing (SQA), the Shin-Smolin-Smith-Vazirani thermal rotor model (SSSV), and the Hamze-Freitas-Selby (HFS) algorithm, as well as the D-Wave device (DW2). We observe a universal hardness peak for all methods, and we observe that the optimal time for the numerical methods scales exponentially with the problem size.