Research ArticlePHYSICS

High-performance combinatorial optimization based on classical mechanics

See allHide authors and affiliations

Science Advances  03 Feb 2021:
Vol. 7, no. 6, eabe7953
DOI: 10.1126/sciadv.abe7953
  • Fig. 1 Dynamics in three SB algorithms.

    Two-spin ferromagnetic Ising problem (J1,2 = J2,1 = 1) is solved by aSB, bSB, and dSB with a(t) = 0.01t, a0 = 1, and c0 = 0.2. (A) Time evolutions of x1 and x2 in aSB. (B) Potential energies VaSB in aSB at the initial (top), intermediate (middle), and final (bottom) times. The vertical dotted line in (A) indicates the intermediate time. Curves in white are trajectories between the initial and intermediate times (middle) and between the intermediate and final times (bottom). Local minima of VaSB are shown by + in red. (C to F) Corresponding results for bSB (C and D) and dSB (E and F). (G to I) Time dependences of potential energy and total energy in aSB (G), bSB (H), and dSB (I). In each panel, the inset magnifies the part in the red dashed square. The dashed arrow in the inset in (I) indicates tunneling-like behavior in dSB. The red bold curve in the middle of (F) shows the trajectory corresponding to this inset.

  • Fig. 2 Comparison of performance for a 2000-spin Ising problem with all-to-all connectivity (K2000).

    (A) Average (lines) and maximum (symbols) cut values for 1000 trials. Nstep is the number of time steps. The time step Δt is set to 0.5 (aSB) or 1 (bSB and dSB). (See Methods for other settings.) (B) Computation times for our bSB and dSB machines (bSBM and dSBM) implemented with single FPGAs and three previously developed machines: CIM (11), aSB machine (aSBM) (30), and STATICA (27). (The results by STATICA are predicted ones by a simulator. The other results are measured ones using real machines.) The cut values are final ones in each trial, where the computation times of bSBM and dSBM are controlled by Nstep. Lines show average cut values for bSBM (blue) and dSBM (red). Crosses show average cut values for the other three machines. Bars show maximum and minimum cut values. The average, maximum, and minimum values are evaluated by 100 trials. The time step Δt is set to 1.25 for both the bSBM and dSBM. (See Methods for other settings.)

  • Fig. 3 TTS and TTT benchmarking.

    (A) Machines compared in this benchmarking. Superscripts represent reference numbers for data sources. (B) Comparison of TTTs for two instances of 2000-spin size, K2000 and G22. (C) Comparison of TTSs. The values of the first six problems are medians for 100 (10 for CIM and 20 for QA) random instances. The bar graphs compare all TTTs and TTSs in log scale. For this benchmarking, the time step Δt for bSBM and dSBM is set to the best value for each problem among five values (0.25, 0.5, 0.75, 1, and 1.25). [The same value of Δt is used for 100 random instances of each of the first to sixth problems in (C).] The number of time steps, Nstep, is also optimized for TTT or TTS separately. See Methods and table S1 for the values of Δt and Nstep and other detailed information.

  • Fig. 4 Results for ultralarge-scale Ising problems.

    (A) Computation times of aSB, bSB, dSB, and our best SA implemented on a 16-GPU cluster, aSB and SA (25) running on a CPU core, and MA implemented on a four-GPU cluster (26) for a 100,000-spin Ising problem with all-to-all connectivity. Each coupling coefficient Ji,j was a randomly chosen 10-bit integer in {−29 + 1,…,29 – 1} (26). Lines and symbols represent average and best values, respectively, for 100 trials (one trial for aSB and SA running on a CPU). (B) Magnification of (A) around the estimated optimal value. (C and D) Corresponding results for a 1,000,000-spin Ising problem with a sparse connectivity of 1%. Each 1% nonzero Ji,j was a randomly chosen 10-bit integer in {−29 + 1,…,29 – 1}.

Supplementary Materials

  • Supplementary Materials

    High-performance combinatorial optimization based on classical mechanics

    Hayato Goto, Kotaro Endo, Masaru Suzuki, Yoshisato Sakai, Taro Kanao, Yohei Hamakawa, Ryo Hidaka, Masaya Yamasaki, Kosuke Tatsumura

    Download Supplement

    This PDF file includes:

    • Sections S1 to S10
    • Figs. S1 to S7
    • Tables S1 to S4
    • References

    Files in this Data Supplement:

Stay Connected to Science Advances

Navigate This Article