Research ArticleAPPLIED PHYSICS

Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems

See allHide authors and affiliations

Science Advances  19 Apr 2019:
Vol. 5, no. 4, eaav2372
DOI: 10.1126/sciadv.aav2372
  • Fig. 1 Dynamics in SB with two oscillators for the two-spin Ising problem with ferromagnetic coupling.

    (A) Time-dependent pumping amplitude, p(t) = εptp = 0.01), in the simulation (top) and time evolutions of x and y (oscillating thin lines in middle and bottom panels). Bold lines represent x of stable fixed points (potential energy minima): x1 = x2 = 0 (p ≤ Δ − ξ0 = 0.4), x1=x2=±(pΔ+ξ0)/K (p > Δ − ξ0 = 0.4), and x1=x2=±(pΔξ0)/K (p > Δ + ξ0 = 0.6). (B) Trajectories (circulating lines in white) in three time intervals, (0, 40) (top), (40, 60) (middle), and (60, 200) (bottom) and potential energy V(x, t) measured from the total energy E(t) = H(x(t), y(t), t) at the final times of the intervals. The boundaries of the time intervals are indicated in (A) by the dotted (t = 40) and dashed (t = 60) vertical lines. The loops (magenta) show the boundaries of the energetically allowable regions defined by V(x, t) − E(t) ≤ 0 at the final times. Other parameters are set as K = 1, Δ = 0.5, ξ0 = 0.1, x1(0) = x2(0) = y1(0) = 0, and y2(0) = 0.1. (C and D) Similar results for p(t) given in the top panel in (C) are shown. The boundaries of the time intervals are indicated in (C) by the dotted (t = 100) and dashed (t = 131.2) vertical lines.

  • Fig. 2 Performance of SB machine implemented with an FPGA for K2000.

    (A) Time evolutions of Ising energies. (The computation times do not include the loading of data and the output of the results; see the Supplementary Materials.) Constants in SB are set as K = Δ = 1 and ξ0=0.7ΔσN (σ = 1 is the SD of the elements of J.) p(t) is linearly increased from 0 to 1, while the number of time steps is increased from 1 to Nstep. Bold lines: 100-trial average energies of SB with Nstep = 40 (left), CIM from (17, 19) (middle), and SA from (19) (right). [The CIM data are the 26-trial average eliminating 74 trials because of the instability of optical parametric oscillators (17, 19).] Dashed thin and dotted thin lines sandwiching the bold lines: lower (best case) and upper (worst case) envelopes of the 100 traces. Dotted thin horizontal line: GW-SDP (17). Dashed thin horizontal line: 100-trial average energy of HNN after convergence at a local minimum. Table: computation times to reach the HNN and GW-SDP energies. N/A, not applicable. (B) Histograms of 100 cut values obtained by SB with Nstep = 186 in 0.5 ms (top), CIM in 5 ms from (17) (middle), and SA in 50 ms from (17) (bottom). The numbers in the panels are the average cut values of the 100 trials.

  • Fig. 3 Performance of SB machines implemented with a GPU cluster and a PC cluster for M100000.

    (A) Computation times of SB (Nstep = 100) and SA (Nsweep = 100) for M100000. (The computation times do not include the loading of data and the output of the results; see the Supplementary Materials.) Constants in SB are set as K = Δ = 1 and ξ0=0.7ΔσN (σ=1/3 is the SD of the elements of J.) p(t) is linearly increased from 0 to 1, while the number of time steps is increased from 1 to Nstep. In the SA, the annealing speed is controlled by the total number of “sweeps” Nsweep, and the inverse temperature is increased linearly from 0 to 0.05. Full and empty circles: SB and SA, respectively, using a PC cluster, the number of cores of which is given by the horizontal axis (each node of the PC cluster uses 1 core or 25 cores). Dotted and dashed lines: SB and SA, respectively, using a GPU cluster with eight GPUs. (B) Time evolutions of Ising energies (thin lines). Full and empty circles connected by dotted lines: final values of SB and SA, respectively, with different Nstep and Nsweep (both are 10, 20, 50, 100, 200, 500, and 1000 from left). Dashed horizontal line: 10-trial average of HNN after convergence to a local minimum.

Supplementary Materials

  • Supplementary material for this article is available at http://advances.sciencemag.org/cgi/content/full/5/4/eaav2372/DC1

    Solving MAX-CUT with Ising machines

    First bifurcation in SB

    Setting of ξ0

    HNN of two-state neurons

    Simulated annealing

    FPGA implementation of SB for K2000

    Definition of M100000

    Eight-GPU implementation of SB and SA for M100000

    PC-cluster implementation of SB and SA for M100000

    Fig. S1. Computation times of our best SA and the SA software provided by (22) for M100000.

  • Supplementary Materials

    This PDF file includes:

    • Solving MAX-CUT with Ising machines
    • First bifurcation in SB
    • Setting of ξ0
    • HNN of two-state neurons
    • Simulated annealing
    • FPGA implementation of SB for K2000
    • Definition of M100000
    • Eight-GPU implementation of SB and SA for M100000
    • PC-cluster implementation of SB and SA for M100000
    • Fig. S1. Computation times of our best SA and the SA software provided by (22) for M100000.

    Download PDF

    Files in this Data Supplement:

Stay Connected to Science Advances

Navigate This Article