Combinatorial optimization problems are fundamental to many industrial and scientific applications, but are often NP-hard, requiring heuristic and probabilistic approaches to find good solutions fast. This paper presents the first hardware implementation of the neuromorphic-inspired NeuroSA algorithm, for accelerating Quadratic Unconstrained Binary Optimization (QUBO) problems. We show that it is possible to run a standard QUBO benchmark problem with 800 variables on a low-cost FPGA with a clock speed of approximately 144 MHz, which converges to the same solution value found by the numerical solver.
Combinatorial optimization problems are fundamental to many industrial and scientific applications, but are often NP-hard, requiring heuristic and probabilistic approaches to find good solutions fast. This paper presents the first hardware implementation of the neuromorphic-inspired NeuroSA algorithm, for accelerating Quadratic Unconstrained Binary Optimization (QUBO) problems. We show that it is possible to run a standard QUBO benchmark problem with 800 variables on a low-cost FPGA with a clock speed of approximately 144 MHz, which converges to the same solution value found by the numerical solver.
Ising Machines are emerging hardware architectures that efficiently solve NP-Hard combinatorial optimization problems. Generally, combinatorial problems are transformed into quadratic unconstrained binary optimization (QUBO) form, but this transformation often complicates the solution landscape, degrading performance, especially for multi-state problems. To address this challenge, we model spin interactions as generalized boolean logic function to significantly reduce the exploration space. We demonstrate the effectiveness of our approach on graph coloring problem using probabilistic Ising solvers, achieving similar accuracy compared to state-of-the-art heuristics and machine learning algorithms. It also shows significant improvement over state-of-the-art QUBO-based Ising solvers, including probabilistic Ising and simulated bifurcation machines. We also design 1024-neuron all-to-all connected probabilistic Ising accelerator on FPGA with the proposed approach that shows ~10000x performance acceleration compared to GPU-based Tabucol heuristics and reducing physical neurons by 1.5-4x over baseline Ising frameworks. Thus, this work establishes superior efficiency, scalability and solution quality for multi-state optimization problems.
Abstract Quadratic unconstrained binary optimization (QUBO) is a combinatorial optimization problem. Since various NP‐hard problems such as the traveling salesman problem can be formulated as a QUBO instance, QUBO is used with a wide range of applications. The main contribution of this article is to propose high‐throughput FPGA implementations for the QUBO solver. We perform the local search using different bit‐selection strategies based on the simulated annealing in the proposed implementation. The hardware is a pipeline structure with no pipeline hazards using multiple instances, where the bit‐flip operation is always performed every clock cycle. We implemented the proposed circuit on Xilinx UltraScale+ FPGA VU9P. The implementation result shows that the circuit can search solutions per second. Besides, by sharing the block RAM that stores a weight matrix, we implemented a dual annealer architecture that has two QUBO solvers into the FPGA. As a result, the dual annealer architecture can search solutions per second.
The problems of Artificial intelligence (AI) naturally maps to NP-hard optimization problems. This trend has significance to achieve human-level computation capability from machines. This computational ability can be achieved by developing evolutionary algorithms or mapping those evolutionary algorithms onto new generation computing systems: Quantum or Neuromorphic hardware. In this paper, we implemented the NP-hard optimization problem called Quadratic Unconstrained Binary Optimization (QUBO) problem for the solution of graph problems on the IBM's Neurosynaptic TrueNorth System. We have experimented on different types of graph problems with different levels of complexities and achieved encouraging results on IBM's Neuromorphic TrueNorth chip. Moreover, there are a set of potential applications have been discussed based on this proposed QUBO solution. Along with the QUBO on quantum annealing, it is the important first step towards the solutions of QUBO on Neuromorphic computing systems.
Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. As many NP problems can be reduced to QUBO problems, considerable research has gone into developing QUBO solvers running on various computing platforms such as quantum devices, ASICs, FPGAs, GPUs, and optical fibers. For evaluating the performance of QUBO solvers, QUBO problems reduced from combinatorial optimization problems such as MaxCut, Traveling Salesman Problem (TSP), and Quadratic Assignment Problem (QAP) are commonly used. This paper presents a new benchmark QUBO problem inspired by digital halftoning, which aims to find a binary image reproducing an input grayscale image. The characteristics of this QUBO problem reduced from digital halftoning are quite unique. Solutions of the QUBO problem can be converted into binary images, from which we can visually evaluate the solution quality. Good approximation solutions for the QUBO problem can be obtained by a simple heuristic algorithm very quickly. However, it is very hard to find an optimal solution. Moreover, quite interestingly, we can create a QUBO problem for digital halftoning with a known optimal solution for a benchmarking purpose. Thus, we can exactly compute the gap between the optimal solution and an approximate solution obtained by a QUBO solver. We have developed an OpenMP-based sparse QUBO solver that can find good approximate solutions for QUBO problems reduced from digital halftoning. We have evaluated the performance of QUBO solvers including the D-Wave Hybrid solver, Gurobi optimizer, Open.Jij, and our sparse QUBO solver. The experimental results show that our OpenMP-based sparse QUBO solver attains the best performance.
Quadratic Unconstrained Binary Optimization (QUBO) provides a versatile framework for representing NP-hard combinatorial problems, yet existing solvers often face trade-offs among speed, accuracy, and scalability. In this work, we introduce a quantum-inspired solver (QIS) that unites branch-and-bound pruning, continuous gradient-descent refinement, and quantum-inspired heuristics within a fully adaptive control architecture. We benchmark QIS3 against eight state-of-the-art solvers, including genetic algorithms, coherent Ising machines, simulated bifurcation, parallel tempering, simulated annealing, our prior QIS2 version, D-Wave's simulated-annealing (Neal), and Gurobi on three canonical QUBO problem classes: Max-Cut, NAE-3SAT, and Sherrington-Kirkpatrick spin glass problems. Under a uniform runtime budget, QIS3 attains the best solution on nearly all instances, achieving optimality in 94% of max-cut instances. These results establish QIS3 as a robust, high-performance solver that bridges classical exact strategies and quantum-inspired heuristics for scalable QUBO optimization.
Abstract Ising Machines are emerging hardware architectures that efficiently solve NP-hard combinatorial optimization problems. Generally, combinatorial problems are transformed into quadratic unconstrained binary optimization (QUBO) form, but this transformation often complicates the solution landscape, degrading performance, especially for multi-state problems. To address this challenge, we model spin interactions as generalized boolean logic function to significantly reduce the exploration space. We demonstrate the effectiveness of our approach on graph coloring problem using probabilistic Ising solvers, achieving similar accuracy compared to state-of-the-art heuristics and machine learning algorithms. It also shows significant improvement over state-of-the-art QUBO-based Ising solvers, including probabilistic Ising and simulated bifurcation machines. We also design 1024-neuron all-to-all connected probabilistic Ising accelerator on FPGA with the proposed approach that shows ∼ ~ 10000 × × performance acceleration compared to GPU-based Tabucol heuristics and reducing physical neurons by 1.5 − − 4 × × over baseline Ising frameworks. Thus, this work establishes superior efficiency, scalability and solution quality for multi-state optimization problems.