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 imple-mentations 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.

Evaluating Spintronics-Compatible Implementations of Ising Machines

Andrea Grimaldi;Eleonora Raimondo;Vincenza Crupi;Mario Carpentieri;Vito Puliafito
;
Giovanni Finocchio
2023-01-01

Abstract

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 imple-mentations 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11570/3272750
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact