Evaluating Spintronics-Compatible Implementations of Ising Machines

The commercial and industrial demand for the solution of hard combinatorial optimization problems pushes forward the development of efficient solvers. One of them is the Ising machine, which can solve combinatorial problems mapped to Ising Hamiltonians. In particular, spintronic hardware implementations of Ising machines can be very efficient in terms of area and performance, and are relatively low cost considering the potential to create hybrid CMOS-spintronic technology. Here, we perform a comparison of oscillator-based and probabilistic paradigms of Ising machines on several hard max-cut instances, analyzing their scalability and performance at software level. We show that probabilistic Ising machines outperform oscillator-based Ising machines in terms of the number of iterations required to achieve the problem’s solution. Nevertheless, high-frequency spintronic oscillators with subnanosecond synchronization times could be very promising as ultrafast Ising machines. In addition, considering that a oscillator-based Ising machine acts better for max-cut problems because of the absence of the linear term in the Ising Hamiltonian, we introduce a procedure to encode max-3SAT to max cut. We foresee potential synergic interplays between the two paradigms.

Figure 1

A visual example of a maximum-cut problem. The graph is encoded into an Ising Hamiltonian with a symmetric matrix J whose values correspond to the weights of the connections. In an optimal solution, the nodes are in one of the two states in such a way that the bipartition “cuts” the highest value of accumulated edges.

Figure 2

(a) A schematic of an MTJ designed to behave as an oscillator for an OIM. The MTJ has three terminals and has an elliptical cross section with the polarizer having its magnetization aligned along the x direction. The self-oscillations are driven by the dc current density and the VCMA signal acts as the injection-locking signal. (b) In the top panel, the VCMA signal acting on the MTJ; in the bottom panel, $m_x$ dynamics from simulations of two distinct devices, showcasing the phase binarization phenomenon due to the injection locking from the VCMA. (c) The same behavior shown in (b) can be achieved by using an ac STT current density as the injection-locking signal. (d) A schematic of an MTJ designed to behave as a p bit for a PIM. The MTJ has three terminals and is a circular cylinder with an out-of-plane polarizer. (e) Schematic showing the three-step process of tunable random number generation (RNG) as described in the text. (f) The dependence of this probability on the signal intensity is sigmoidal. Each point of this plot is the average of ${10}^4$ RNG simulations. The energy landscape of the three main states is shown in the insets.

Figure 3

(a)–(c) Example runs of maximum-cut search of the same randomly generated cubic graph with 100 oscillators simulated using the Kuramoto model (a) and the Slavin model (c). The plots show the phases, used to evaluate the cut value, and the powers of the oscillators in the latter case. The cut values of both models evaluated in each time step (continuous line) are plotted in (b) together with the linear annealing schedule of the respective annealing parameters (dashed line). Both models use a saw-tooth annealing schedule. (d) A comparison between the performance of the Kuramoto model and the Slavin model finding the max cut of randomly generated cubic graphs. For most of the reported values, the max cut has been averaged over the solution of 100 different randomly generated graphs; for a higher number of oscillators only one run is considered.

Figure 4

A comparison of the PIM and the Kuramoto-based OIM model on the instance “g1.rud” from the G-set. The instance has 800 nodes and 19 176 edges. The red (blue) area represents an ensemble of 100 solving attempts using PIM (OIM). For both models, the black line represents the average of all solving attempts. The annealing parameters were chosen after a systematic study to ensure fairness in the comparison.

Figure 5

(a),(b) Two-input and three-input and gate simulation with optimized parameters $K=1$, $K_h=0.5$, $S=1$. Each set of colored bars represents a simulation setup with a different bias h. In orange (blue) the output is clamped to +1 (−1), so $h_3$ is increased (decreased) by 10. The height of the bars is the number of times a randomized simulation has ended its annealing schedule in that state. The truth table states to visit with output clamped to +1 (−1) are highlighted in green (red). Composing circuits seems to affect the probability distribution, hindering scalability. (c) Three-dimensional representation of final state versus initial conditions of the unbiased and gate simulated in (a). (d) Comparison between the Kuramoto model oscillators and attraction model simulations. The similarities suggest that oscillators tend to gravitate toward the closest solution in the phase space.

Figure 6

(a) Graph representation of a single (A $\bigvee$ B $\bigvee$ C) logic clause. The maximum cut is only achieved in states where the clause is satisfied. (b) Graph of a toy max-3SAT instance with an example of a variable shared in more than one logic clause. (c),(d) States reached by the Kuramoto model system of oscillators for the simple max-3SAT instance “uf20-01.cnf”, with 20 variables and 91 clauses. We performed 1000 simulations with random initial state. The solution cost represents the number of logic clauses not satisfied at the last step of each simulation. The red dashed line is a guide to the eye to demonstrate the correlation between the maximum cut and the solution cost of the max SAT.