The search for hardware-compatible strategies for solving nondeterministic polynomial time (NP)-hard combinatorial optimization problems (COPs) is an important challenge of today's computing research because of their wide range of applications in real-world optimization problems. Here, we introduce an unconventional scalable approach to face maximum-satisfiability (MAX-SAT) problems that combines probabilistic computing with p-bits, parallel tempering, and the concept of invertible logic gates. We theoretically show the spintronic implementation of this approach based on a coupled set of Landau-Lifshitz-Gilbert equations, showing a potential path for energy efficient and very fast (p-bits exhibiting nanosecond timescale switching) architecture for the solution of COPs. The algorithm is benchmarked with hard MAX-SAT instances from the 2016 MAX-SAT competition (e.g., "HG-4SAT-V150-C1350-1.cnf,"which can be described with 2851 p-bits), including weighted MAX-SAT and maximum-cut problems.

Spintronics-compatible Approach to Solving Maximum-Satisfiability Problems with Probabilistic Computing, Invertible Logic, and Parallel Tempering

Andrea Grimaldi
Primo
;
Giovanni Finocchio
Ultimo
2022-01-01

Abstract

The search for hardware-compatible strategies for solving nondeterministic polynomial time (NP)-hard combinatorial optimization problems (COPs) is an important challenge of today's computing research because of their wide range of applications in real-world optimization problems. Here, we introduce an unconventional scalable approach to face maximum-satisfiability (MAX-SAT) problems that combines probabilistic computing with p-bits, parallel tempering, and the concept of invertible logic gates. We theoretically show the spintronic implementation of this approach based on a coupled set of Landau-Lifshitz-Gilbert equations, showing a potential path for energy efficient and very fast (p-bits exhibiting nanosecond timescale switching) architecture for the solution of COPs. The algorithm is benchmarked with hard MAX-SAT instances from the 2016 MAX-SAT competition (e.g., "HG-4SAT-V150-C1350-1.cnf,"which can be described with 2851 p-bits), including weighted MAX-SAT and maximum-cut problems.
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/3230241
 Attenzione

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

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