Please use this identifier to cite or link to this item:
http://hdl.handle.net/2122/16222
Authors: | Grimaldi, Andrea* Sánchez-Tejerina San José, Luis* Aadit, Muhammad Navid Anjum* Chiappini, Stefano* Carpentieri, Mario* Camsari, Kerem* Finocchio, Giovanni* |
Title: | Spintronics-compatible approach to solving maximum satisfiability problems with probabilistic computing, invertible logic and parallel tempering | Journal: | Physical Review Applied | Series/Report no.: | /17 (2022) | Publisher: | American Physical Society | Issue Date: | 18-Feb-2022 | DOI: | 10.1103/PhysRevApplied.17.024052 | Keywords: | Physics - Mesoscopic Systems and Quantum Hall Effect; Physics - Mesoscopic Systems and Quantum Hall Effect | Abstract: | The search of hardware-compatible strategies for solving 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 problems (Max-SAT) which 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 ns time scale 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 Max-Cut problems. | Description: | 7 Figures, 20 pages |
Appears in Collections: | Article published / in press |
Files in This Item:
File | Description | Size | Format | Existing users please Login |
---|---|---|---|---|
2022 - Probabilistic computing.pdf | Restricted Paper | 1.29 MB | Adobe PDF | |
2201.12858.pdf | 5.89 MB | Adobe PDF | View/Open |
Page view(s)
67
checked on Apr 27, 2024
Download(s)
2
checked on Apr 27, 2024