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.
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 main contribution of this work is to propose a new fully-pipelined architecture for the QUBO solver on the FPGA. For the fully-pipelined architecture, we propose two local search algorithms based on the simulated annealing with different bit-selection strategies in the local search. The implementation supports a 1024-bit QUBO problem with 16-bit weights. For the problem, we use multiple instances and perform the local search in overlapped execution with pipeline structure. We implemented the proposed circuit on Xilinx UltraScale+ FPGA V09P. The implementation result shows that the circuit can search 3.58×1011solutions per second. In addition, by sharing the block RAM, we implemented a dual annealer architecture that has two QUBO solver into the FPGA. As a result, the dual annealer architecture can search 6.14 × 1011solutions per second.
Summary 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. The main contribution of this article is to propose the bit duplication technique that can specify the number of duplicated bits, so that it can generate hard QUBO problem with adjustable sizes. The idea is to duplicate specified number of bits and then to give constraints so that the corresponding two bits take the same binary values. By this technique, any QUBO problem with bits is converted to a hard QUBO problem with bits . We use random QUBO problems, N‐Queen problems, traveling salesman problem and maximum weight matching problems for experiments. The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D‐Wave samplers with SA, D‐Wave hybrid and ABS2 QUBO solver are evaluated for solving these QUBO problems. The experimental results show that only a small scale of duplicated bits can make QUBO problems harder. Hence, the bit duplication technique is a potent method to generate hard QUBO problems and generated QUBO problems can be used as benchmark problems for evaluating the search performance of QUBO solvers.
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.
As Moore’s Law slows, alternative computing paradigms are essential for tackling complex combinatorial optimization problems. This paper introduces DigiQUBO, a high-performance digital Quadratic Unconstrained Binary Optimization (QUBO) solver designed for quantum-inspired optimization. DigiQUBO leverages a advanced Digital Annealing (DA) approach to efficiently solve large-scale QUBO problems, offering a competitive alternative to traditional annealing methods. To evaluate its effectiveness, DigiQUBO is applied to the Traveling Salesman Problem (TSP), a well-known NP-hard problem with applications in logistics, network design, and computational biology. In solving a 40-city Traveling Salesman Problem (TSP), DigiQUBO achieved an average route distance improvement of 13% compared to Simulated Annealing (SA), and a reduction of 37% compared to D-Wave’s LeapHybridSampler, while maintaining comparable runtime to Fujitsu DA3. DigiQUBO significantly enhances solution quality and computational efficiency by integrating two key advanced techniques: two-way one-hot group encoding for improved constraint satisfaction and Bayesian Optimization for automated annealing parameter tuning. Performance comparisons against Simulated Annealing (SA), Fujitsu DA3, and D-Wave’s LeapHybridSampler demonstrate superior results in balancing accuracy and execution time. The results highlight DigiQUBO as a promising digital annealing technology that bridges the gap between classical and quantum optimization, offering a practical and efficient solution in the post-Moore’s Law era.
The quadratic unconstrained binary optimization (QUBO) is recently gathering attention in conjunction with quantum annealing (QA), since it is equivalent to finding the ground state of an Ising model. Due to the limitation of current QA systems, classical computers may outperform them. Researchers have thus been proposed to solve QUBO on FPGAs, GPUs, and special purpose processors. In this paper, we propose an adaptive bulk search (ABS), a framework for solving QUBO that can perform many searches in parallel on multiple GPUs. It supports fully-connected Ising models with up to 32k spins and 16-bit weights. In our ABS, a CPU host performs genetic algorithm (GA) while GPUs asynchronously perform local searches. A bottleneck for solving QUBO exists in the evaluation of the energy function, which requires computational cost for each solution. We show this can be reduced to in our ABS. The experimental results show that, with four NVIDIA GeForce RTX 2080 Ti GPUs, our framework can search up to 1.24 × 1012 solutions per second. We also show that our system quickly solves maximum cut and traveling salesman problems.
The Steiner Tree Problem (STP) is a well-known NP-hard combinatorial optimization problem, which has wide applications in network design, integrated circuit layout, bioinformatics, and other fields. However, traditional algorithms often struggle to balance efficiency and solution quality when dealing with large-scale STP instances. In this paper, we propose a new quantum annealing-based algorithm for solving the STP: we first model the STP into a quadratic unconstrained binary optimization (QUBO) form suitable for quantum annealing, then design a corresponding encoding strategy, and finally verify the algorithm through experimental tests. The results show that our quantum annealing-based method can obtain high-quality solutions with relatively low computational overhead for moderate-scale STP instances, providing a new feasible path for handling this intractable combinatorial optimization problem.