Equation Planting: A Tool for Benchmarking Ising Machines
Itay Hen · Physical Review Applied · 2019
Recent years have witnessed the flourishing of experimental $I\phantom{\rule{0}{0ex}}s\phantom{\rule{0}{0ex}}i\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}g$ $m\phantom{\rule{0}{0ex}}a\phantom{\rule{0}{0ex}}c\phantom{\rule{0}{0ex}}h\phantom{\rule{0}{0ex}}i\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}e\phantom{\rule{0}{0ex}}s$, special-purpose computational devices that promise to solve the world's toughest optimization problems in record times. Evaluating an Ising machine's performance is problematic, though, as it poses two seemingly contradictory requirements: On the one hand, the generated problem instances should be hard to solve, yet on the other hand they should have verifiable solutions. This study provides a methodology for generating random optimization-problem sets from linear systems of equations that possess both desired properties, thereby allowing direct, unbiased benchmarking of these physical optimization devices.