    Also in the Article

Sample problems

Procedure

For fully connected SK and MAX-CUT on dense graphs, 20 random instances were created of each size N = 2,3, … ,61 for the D-Wave. Of these, the N = 2,10,20, … ,60 instances were also used for the CIM. An additional set of random instances were created for N = 70,80, … ,150 for the CIM using the same algorithm.

For the sparse-graph analysis, we computed regular graphs of size N = 2,4, … ,300 and degree d = 3,4, … 20, with 20 instances for each pair (N, d). The algorithm randomly assigns edges to eligible vertices until all reach the required degree (and backtracks if it gets stuck). The same algorithm was also used for the variable-density graphs: d = 1,2, … , (N − 2) for N = 20,30,40,50,60, creating 20 instances per pair (N, d).

Exact SK ground states were found with the Spin Glass Server (59), which uses BiqMac (60), an exact branch-and-bound algorithm. For SK instances of size N ≤ 100, the algorithm obtained proven ground states. For N > 100, the solver timed out before exhausting all branches (runtime T = 3000 s), so the result is not a guaranteed ground state; however, we believe that it reaches the ground state with high probability for N ≤ 150 because multiple runs of the algorithm give the same state energy and none of the CIM runs found an Ising energy lower than the Spin Glass Server result. MAX-CUT ground states for N ≤ 30 were found by brute-force search on a personal computer; for 20 ≤ N ≤ 150, a BLS algorithm was used (5). Although BLS is a heuristic solver, for N ≤ 150, it finds the ground state with nearly 100% probability, giving us high confidence that the BLS solutions are ground states. While the brute-force solver, D-Wave, and the CIM found states of equal energy to the BLS solution (if run long enough), they never found states of lower energy.

Q&A