This paper presents a digital annealing engine capable of high-speed solving the Binary Quadratic Programming Problem (BQP) with equality and inequality constraints. While many Quadratic Unconstrained Binary Optimization (QUBO) solvers have been developed for combinatorial optimization problems, they are specialized for “unconstrained” BQP and struggle to solve “constrained” BQP at high speed. To address this issue, we developed a digital annealing engine on GPUs that leverages constraints to narrow the search space and directly evaluates inequality violations during Markov Chain Monte Carlo based searches. We evaluated the performance of the Digital Annealer (DA) system with the developed engine on benchmark problems with one-hot (a type of equality constraint) and inequality constraints. The results showed that the developed DA system achieved superior solving performance compared to the previous generation of DA. It also showed comparable performance to state-of-the-art dedicated solvers. Our results suggest that this digital annealing engine is a promising solution for high-speed solving constrained BQP.
This paper presents a digital annealing engine capable of high-speed solving the Binary Quadratic Programming Problem (BQP) with equality and inequality constraints. While many Quadratic Unconstrained Binary Optimization (QUBO) solvers have been developed for combinatorial optimization problems, they are specialized for “unconstrained” BQP and struggle to solve “constrained” BQP at high speed. To address this issue, we developed a digital annealing engine on GPUs that leverages constraints to narrow the search space and directly evaluates inequality violations during Markov Chain Monte Carlo based searches. We evaluated the performance of the Digital Annealer (DA) system with the developed engine on benchmark problems with one-hot (a type of equality constraint) and inequality constraints. The results showed that the developed DA system achieved superior solving performance compared to the previous generation of DA. It also showed comparable performance to state-of-the-art dedicated solvers. Our results suggest that this digital annealing engine is a promising solution for high-speed solving constrained BQP.
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 Assignment Problem is a a classical constrained optimization problem used to model many real-life applications. We present experiments in solving the Quadratic Assignment Problem by means of Quantum Annealing and Quantum-inspired Annealing. We describe how to model this classical combinatorial problem in terms of QUBO (Quadratic Unconstrained Binary optimization) for implementing it on hardware solvers based on quantum or quantum-inspired annealing (D-Wave, Fujitsu Digital Annealing Unit and Fixstars Amplify Annealing Engine). We present performance result for these implementations and compare them with well established metaheuristic solvers on classical hardware, such as Robust Tabu Search and External Optimization.
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.
A Digital Annealer (DA) is a dedicated architecture for high-speed solving of combinatorial optimization problems mapped to an Ising model. With fully coupled bit connectivity and high coupling resolution as a major feature, it can be used to express a wide variety of combinatorial optimization problems. The DA uses Markov Chain Monte Carlo as a basic search mechanism, accelerated by the hardware implementation of multiple speed-enhancement techniques such as parallel search, escape from a local solution, and replica exchange. It is currently being offered as a cloud service using a second-generation chip operating on a scale of 8,192 bits. This paper presents an overview of the DA, its performance against benchmarks, and application examples.
Annealers leverage quadratic unconstrained binary optimization (QUBO) formulas to address combinatorial optimization problems (COPs) and have shown potential to outperform classical computers. This paper examines three prominent types of annealers: quantum, digital, and GPU annealers. Quantum annealers (QAs) are exemplified by the D-Wave Advantage, which relies on the quantum tunneling phenomenon to rapidly locate the minimum-energy system state corresponding to the optimal solution to a COP. Digital annealers (DAs) are typified by the Fujitsu Digital Annealing Unit (DAU), which is based on a quantum-inspired digital architecture to perform parallel and real-time optimization calculations to solve a COP. GPU annealers (GPUAs) are exemplified by the Compal Quantix solver, which harnesses graphics processing units (GPUs) to conduct the diverse adaptive bulk search for the optimal COP solution. This paper first provides an introductory overview of the QA, DA, and GPUA, and then proceeds to benchmark their performance on solving various well-known COPs such as the subset sum, maximum cut, vertex cover, 0/1 knapsack, graph coloring, Hamiltonian cycle, traveling salesperson, and job-shop scheduling problems. Their performance is also compared with that of state-of-the-art algorithms running on classical computers. Through comprehensive performance benchmarks in terms of the solution quality and the execution time, we identify the strengths and weaknesses of each annealer. In addition, we also provide recommendations to improve the performance of each annealer. Specifically, we recommend using the genetic algorithm, the improved particle swarm optimization algorithm, and the ant colony optimization algorithm in all annealers, using quantum pausing, quenching, and reverse annealing in the QA, using built-in separated penalty terms, one-way/two-way one-hot constraints, and linear inequality constraints in the DA, and implementing some parallel algorithms in the GPUA for performance improvement.