Abstract

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.

Date

March 4, 2015

Authors

Joshua Job, Itay Hen, Tameem Albash, Matthias Troyer, Daniel Lidar

Journal

Bulletin of the American Physical Society

Volume

60

Publisher

American Physical Society