TY  - CONF
AU  - Hizzani, Mohammad
AU  - Dobrynin, Dmitri
AU  - Van Vaerenbergh, Thomas
AU  - Hutchinson, George
AU  - Strukov, Dmitri
AU  - Strachan, John Paul
TI  - Mapping NP-Complete Problems to Physics-Based QUBO Solvers: Quantitative Comparison and Understanding
PB  - RWTH Aachen
M1  - FZJ-2024-00664
PY  - 2023
AB  - NP-complete problems like 3-SAT can be mapped and solved by emerging physics-based hardware such as Ising systems, quantum annealers, or Hopfield neural networks. Such systems natively handle quadratic unconstrained binary optimization (QUBO) problems, while higher order and constrained problem classes can be transformed into these simpler QUBO formulations.  However, there are often multiple possible mappings for such transformations, with substantial performance differences.  Here, we compared several different mappings from 3-SAT to a QUBO solver and quantified the differences in resources required (additional auxiliary variables) and final time-to-solution. Notably, while the global minimum of the 3-SAT problem matches the global minimum of the QUBO problem, we find stark differences in other portions of the landscape in terms of gradient directions. We attempt to explain the observed differences between the mappings utilizing a simplified under-sampling metric and showed good predictive capability. Our chosen platform was a Hopfield neural network, with different annealing techniques and neuron update rules compared.
T2  - International conference on neuromorphic, natural and physical computing
CY  - 25 Oct 2023 - 27 Oct 2023, Hannover (Germany)
Y2  - 25 Oct 2023 - 27 Oct 2023
M2  - Hannover, Germany
LB  - PUB:(DE-HGF)24
DO  - DOI:10.34734/FZJ-2024-00664
UR  - https://juser.fz-juelich.de/record/1021223
ER  -