The Fujitsu Digital Annealer is designed to solve fully connected quadratic unconstrained binary optimization (QUBO) problems. It is implemented on application-specific CMOS hardware and currently solves problems of up to 1024 variables. The Digital Annealer's algorithm is currently based on simulated annealing; however, it differs from it in its utilization of an efficient parallel-trial scheme and a dynamic escape mechanism. In addition, the Digital Annealer exploits the massive parallelization that custom application-specific CMOS hardware allows. We compare the performance of the Digital Annealer to simulated annealing and parallel tempering with isoenergetic cluster moves on two-dimensional and fully connected spin-glass problems with bimodal and Gaussian couplings. These represent the respective limits of sparse versus dense problems, as well as high-degeneracy versus low-degeneracy problems. Our results show that the Digital Annealer currently exhibits a time-to-solution speedup of roughly two orders of magnitude for fully connected spin-glass problems with bimodal or Gaussian couplings, over the single-core implementations of simulated annealing and parallel tempering Monte Carlo used in this study. The Digital Annealer does not appear to exhibit a speedup for sparse two-dimensional spin-glass problems, which we explain on theoretical grounds. We also benchmarked an early implementation of the Parallel Tempering Digital Annealer. Our results suggest an improved scaling over the other algorithms for fully connected problems of average difficulty with bimodal disorder. The next generation of the Digital Annealer is expected to be able to solve fully connected problems up to 8192 variables in size. This would enable the study of fundamental physics problems and industrial applications that were previously inaccessible using standard computing hardware or special-purpose quantum annealing machines.
The Fujitsu Digital Annealer is designed to solve fully connected quadratic unconstrained binary optimization (QUBO) problems. It is implemented on application-specific CMOS hardware and currently solves problems of up to 1024 variables. The Digital Annealer's algorithm is currently based on simulated annealing; however, it differs from it in its utilization of an efficient parallel-trial scheme and a dynamic escape mechanism. In addition, the Digital Annealer exploits the massive parallelization that custom application-specific CMOS hardware allows. We compare the performance of the Digital Annealer to simulated annealing and parallel tempering with isoenergetic cluster moves on two-dimensional and fully connected spin-glass problems with bimodal and Gaussian couplings. These represent the respective limits of sparse versus dense problems, as well as high-degeneracy versus low-degeneracy problems. Our results show that the Digital Annealer currently exhibits a time-to-solution speedup of roughly two orders of magnitude for fully connected spin-glass problems with bimodal or Gaussian couplings, over the single-core implementations of simulated annealing and parallel tempering Monte Carlo used in this study. The Digital Annealer does not appear to exhibit a speedup for sparse two-dimensional spin-glass problems, which we explain on theoretical grounds. We also benchmarked an early implementation of the Parallel Tempering Digital Annealer. Our results suggest an improved scaling over the other algorithms for fully connected problems of average difficulty with bimodal disorder. The next generation of the Digital Annealer is expected to be able to solve fully connected problems up to 8192 variables in size. This would enable the study of fundamental physics problems and industrial applications that were previously inaccessible using standard computing hardware or special-purpose quantum annealing machines.
Combinatorial optimization problems are ubiquitous in various disciplines and applications. Many heuristic algorithms have been devoted to solve these types of problems. In order to increase the efficiency for finding the optimal solutions, an application-specific hardware, called digital annealer (DA) has been developed for solving combinatorial optimization problems using quadratic unconstrained binary optimization (QUBO) formulations. In this study, we formulated the number partitioning problem and the graph partitioning problem into QUBO forms and solved such problems with the DA developed by Fujitsu Ltd. The QUBO formulation of the number partitioning problem is fully connected. The DA found the overall runtime for the optimal solution to be less than 30 seconds for 6500 binary variables. For the graph partitioning problem, we adopted modularity as the metric for determining the quality of the partitions. For Zachary's Karate Club graph, the modularity obtained was 0.445, a 6% increase against D-wave Quantum Annealer and Simulated Annealing. Moreover, to explore the DA's potential applications to real-world problems, we used the search for communities or virtual microgrids in a power distribution network as an example. The problem was formulated into graph partitioning. It is shown that the DA effectively identified community structures in the IEEE 33-bus and IEEE 118-bus network.
In more recent years, there has been increasing research interest in exploiting the use of application specific hardware for solving optimisation problems. Examples of solvers that use specialised hardware are IBM's Quantum System One and D-wave's Quantum Annealer (QA) and Fujitsu's Digital Annealer (DA). These solvers have been developed to optimise problems faster than traditional meta-heuristics implemented on general purpose machines. Previous research has shown that these solvers (can optimise many problems much quicker than exact solvers such as GUROBI and CPLEX. Such conclusions have not been made when comparing hardware solvers with classical evolutionary algorithms. Making a fair comparison between traditional evolutionary algorithms, such as Genetic Algorithm (GA), and the DA (or other similar solvers) is challenging because the later benefits from the use of application specific hardware while evolutionary algorithms are often implemented on general-purpose machines. Moreover, quantum or quantum-inspired solvers are limited to solving problems in a specific format. A common formulation used is Quadratic Unconstrained Binary Optimisation (QUBO). Many optimisation problems are however constrained and have natural representations that are non-binary. Converting such problems to QUBO can lead to more problem difficulty and/or larger search space. The question addressed in this paper is whether quantum or quantum-inspired solvers can optimise QUBO transformations of combinatorial optimisation problems faster than classical evolutionary algorithms applied to the same problems in their natural representations. We show that the DA often present better average objective function values than GA on Travelling Salesman, Quadratic Assignment and Multi-dimensional Knapsack Problem instances.
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.
Graph partitioning, or community detection, is the cornerstone of many fields, such as logistics, transportation and smart power grids. Efficient computation and efficacious evaluation of communities are both essential, especially in commercial and industrial settings. However, the solution space of graph partitioning increases drastically with the number of vertices and subgroups. With an eye to solving large scale graph partitioning and other optimization problems within a short period of time, the Digital Annealer (DA), a specialized CMOS hardware also featuring improved algorithms, has been devised by Fujitsu Ltd. This study gauges Fujitsu DA's performance and running times. The modularity was implemented as both the objective function and metric for the solutions. The graph partitioning problems were formatted into Quadratic Unconstrained Binary Optimization (QUBO) structures so that they could be adequately imported into the DA. The DA yielded the highest modularity among other studies when partitioning Karate Club, Les Miserables, American Football, and Dolphin. Moreover, the DA was able to partition the Case 1354pegase power grid network into 45 subgroups, calling for 60,930 binary variables, whilst delivering optimal modularity results within a solving time of roughly 80 seconds. Our results suggest that the Fujitsu DA can be applied for rapid and efficient optimization for graph partitioning.
Quadratic Unconstrained Binary Optimization (QUBO) problems are NP-hard problems and many real-world problems can be formulated as QUBO. Currently there are no algorithms known that can solve arbitrary instances of NP-hard problems efficiently. Therefore special-purpose hardware such as Digital Annealer, other Ising machines, as well as quantum annealers might lead to benefits in solving such problems. We study a particularly hard class of problems which can be formulated as QUBOs, namely Boolean satisfiability (SAT) problems, and specifically 3-SAT. One intriguing aspect about 3-SAT problems is that there are different transformations from 3-SAT to QUBO. We study the transformations' influence on the problem solution, using Digital Annealer as a special-purpose solver. Besides well-known transformations we investigate a novel in this context not yet discussed transformation, using less auxiliary variables and leading to very good performance. Using exact diagonalization, we explain the differences in performance originating from the different transformations. We envision that this knowledge allows for specifically engineering transformations that improve a solvers capacity to find high quality solutions. Furthermore, we show that the Digital Annealer outperforms a quantum annealer in solving hard 3-SAT instances.
Recent hardware developments in quantum technologies have inspired a myriad of special-purpose hardware devices tasked to solve optimization problems. In this paper, we explore the application of Fujitsu's quantum-inspired CMOS-based Digital Annealer (DA) in solving constrained routing problems arising in transportation and logistics. More precisely in this paper, we study the vehicle sharing problem and show that the DA as a QUBO solver can potentially fill the gap between two common methods: exact solvers like Cplex and heuristics. We benchmark the scalability and quality of solutions obtained by DA with Cplex and with a greedy heuristic. Our results show that the DA is a general QUBO solver that is more robust than heuristics, and more scalable than Cplex. Our methodology and framework which focus on QUBO problems is also applicable to other quantum-inspired and fully quantum devices that are undergoing development.