Equation Planting: A Tool for Benchmarking Ising Machines

We introduce a method for generating benchmark problem sets for Ising machines—devices designed to solve discrete-optimization problems cast as Ising models. In our approach, linear systems of equations are cast as Ising cost functions. While linear systems are easily solvable, the corresponding optimization problems are known to exhibit some of the salient features of nondeterministic polynomial-time hardness, such as strong exponential scaling of heuristic solvers’ runtimes and extensive distances between ground and low-lying excited states. We show how the proposed technique, which we refer to as “equation planting,” can serve as a useful tool for evaluating the utility of Ising solvers functioning either as optimizers or as ground-state samplers. We further argue that equation-planted problems can be used to probe the mechanisms underlying the operation of Ising machines.

Figure 1

The two-body 3-XORSAT gadget. The gadget is a fully connected spin quadruplet with parameter values $(h,\tilde{h},J,\tilde{J})$ as described in the main text. The four minimizing configurations of the 3-XORSAT clause are encoded in the ground states of the Ising cost function of the gadget restricted to spins $s_{i_1},s_{i_2},s_{i_3}$. The spin $s_a$ serves as an auxiliary spin.

Figure 2

Runtime scaling of two parallel tempering variants on random 3R3X-planted Ising instances on a log-linear scale (top). Typical runtimes (median over 100 instances) as a function of problem size are given for PT and PT-H. Both exhibit similarly strong exponential scaling. Fits to $e^{\alpha n}$ are shown. Error bars correspond to $1\sigma$ statistical confidence. The shaded areas correspond to the interquartile ranges for each problem size. Typical Hamming distances $⟨D⟩$ (normalized by problem size) of local minima from the global minimum as a function of normalized residual energy are also shown (bottom). The plot demonstrates that low-lying excited states are typically $O(n)$ spin flips away from the global minimum.

Figure 3

Fraction of ground-state occurrences for a random $64$-spin 3R3X instance with an eightfold ground-state degeneracy as found by 1000 parallel tempering runs (left). The horizontal dashed line corresponds to uniform sampling. Also shown are the normalized Hamming distances $⟨D⟩$ between each ground state and all other states. Typical $p$ values obtained from a one-sided ${\chi }^2$ test performed on the ground-state occurrences of randomly generated instances with twofold, fourfold, and eightfold ground-state degeneracies as a function of problem size $n$ (middle). Typical normalized Hamming distances between the ground states of degenerate instances as a function of problem size $n$ for different nullities (right).