%0 Conference Paper
%A Hizzani, Mohammad
%A Dobrynin, Dmitri
%A Van Vaerenbergh, Thomas
%A Hutchinson, George
%A Strukov, Dmitri
%A Strachan, John Paul
%T Mapping NP-Complete Problems to Physics-Based QUBO Solvers: Quantitative Comparison and Understanding
%I RWTH Aachen
%M FZJ-2024-00664
%D 2023
%X 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.
%B International conference on neuromorphic, natural and physical computing
%C 25 Oct 2023 - 27 Oct 2023, Hannover (Germany)
Y2 25 Oct 2023 - 27 Oct 2023
M2 Hannover, Germany
%F PUB:(DE-HGF)24
%9 Poster
%R 10.34734/FZJ-2024-00664
%U https://juser.fz-juelich.de/record/1021223