Fujitsu Digital Annealer
On large-scale Max-Cut problems, Fujitsu Digital Annealer performs admirably, surpassing classical heuristics and competing with quantum-inspired solvers.
Fujitsu’s Digital Annealer (DA), a dedicated quantum-inspired computer, has been positioned as a very competitive solution for large-scale combinatorial optimization challenges, especially the Max-Cut issue, according to a recent thorough examination.
You can also read Model Based Optimization For Superconducting Qubit
Along with colleagues from Hamburg University of Technology and Fujitsu Germany, researchers Salwa Shaglel, Markus Kirsch, and Marten Winkler thoroughly benchmarked the DA against top classical heuristics, hybrid quantum-classical solvers, and other quantum-inspired methods. Their results demonstrate the DA’s capacity to produce convincing outcomes on problems with up to 53,000 variables, meeting a pressing need for effective solvers in domains ranging from machine learning to finance and logistics.
Combinatorial optimization issues are common and can be found in a wide range of applications, including RNA folding, product assembly, finance portfolio optimization, and automobile routing. Since many of these issues are NP-hard that is, their worst-case runtime scales exponentially with problem size finding optimal solutions to them continues to be a considerable difficulty. Because of this intrinsic complexity, heuristic algorithms and specialized hardware have been developed, purposefully sacrificing optimality guarantees in favor of increased speed and scalability.
Formulating these issues as Quadratic Unconstrained Binary Optimization (QUBO) problems is a popular method to make them amenable to Quantum Computing or quantum-inspired heuristics. Such hardware is referred described as “Ising machines” because QUBO problems, which entail minimizing a quadratic objective function with binary variables (0 or 1), are closely related to determining the ground state of the Ising Hamiltonian.
You can also read Coupled Cluster, DFT: Accuracy Cost Paradox In Drug Design
Dedicated QUBO solvers, such as the Digital Annealer, can handle tens of thousands of bits without experiencing the noise and severe connection limits that are typical of quantum hardware, which currently functions with an order of 1,000 noisy qubits. Because of its simple QUBO formulation and applicability in many fields, the Max-Cut problem, an NP-hard issue in graph theory and combinatorial optimization, is a perfect benchmark. The goal is to maximize the sum of edge weights between two disjoint subsets created by splitting a graph’s vertices.
A CMOS-based Application-Specific Integrated Circuit (ASIC) called the Digital Annealer Unit (DAU), which is the central component of the Fujitsu Digital Annealer, is made to effectively carry out an improved simulated annealing method. In contrast to certain hardware architectures that need particular graph topologies, this quantum-inspired technology may operate natively on any graph and is immediately compatible with any connectivity. In order to avoid local minima, the DA uses a Markov chain Monte Carlo technique called simulated annealing, which probabilistically accepts new configurations, even if they are worse, in order to explore the solution space.
You can also read Quantum Multi Wavelength Holography Approach to Imaging
The DA improves this by using parallel tempering (replica exchange) to boost energy landscape exploration, applying dynamic energy offsetting to raise acceptance probabilities at low temperatures, and conducting parallel searches over numerous independent runs. With an extra software layer, DAv3 can manage instances with up to 100,000 variables, whereas DAv2 can support up to 8,192 variables. Since the DAU works with integer values, floating-point coefficients in QUBO matrices must be automatically scaled and rounded.
Following strict guidelines for benchmark set selection, runtime selection, and performance reporting, the benchmark study was painstakingly carried out to guarantee openness and equity. The researchers employed a heterogeneous subset of 2,125 Max-Cut instances with up to 53,000 variables from the MQLib, which is the largest test suite among relevant papers. Based on hardware advancements and computational difficulties, instance-specific time restrictions were established. Along with reporting actual runtimes, the study also took tuning times into consideration, including the DA’s internal, automatic hyperparameter adjustment.
Key Findings from the Benchmarking:
- DA vs. Classical Heuristics (MQLib): The DAv2 outperformed the best-performing classical heuristics in terms of cut values on roughly 69.2% of the benchmarked instances, with ties in roughly 11.92% of cases. On sparse instances, DAv2 demonstrated its greatest advantage. Additionally, the DAv3 continued to perform competitively, producing better cuts in roughly 60.81% of cases and ties in 17.33%. When converting floating-point coefficients to integers, DAv3 was more susceptible to rounding errors, which could reduce accuracy.
- DAv3 vs. D-Wave’s Hybrid Solver (HS): DAv3 beat D-Wave’s HS on instances with integer weights on 45 Max-Cut instances chosen by D-Wave, performing better in 8 cases, equal in 5, and worse in 1. DAv3 exceeded HS on 13 examples but underperformed on 18 instances for float-valued instances, frequently locating solutions in a matter of seconds. Its practical promise for time-sensitive settings is shown by the speed at which DAv3 converges to its optimal solution, often matching or exceeding D-Wave’s HS.
- DA vs. QIS3 Heuristic: One or both Digital Annealer versions outperformed or produced outcomes that were comparable to those of the recently developed quantum-inspired metaheuristic QIS3 on 14 out of 16 examples, frequently with reduced runtimes. This suggests that the DA can outperform QIS3 and, consequently, the eight other cutting-edge solvers against which QIS3 was evaluated. The partitioning needed for DAv3 when problem sizes surpassed a single DAU’s capacity was the reason why QIS3 continued to perform best in the two large G-set instances (G66 and G72) that were the only exceptions. The DA’s quick convergence behavior, which frequently yields high-quality solutions in the first few seconds of runtime, was also seen in the study.
You can also read Quantum Portfolio Optimizer: Global Data Quantum, IBM Qiskit
The thorough benchmarking analysis confirms that the Fujitsu Digital Annealers are reliable and competitive solution providers for difficult Max-Cut issues. According to the findings, the DA can be a useful instrument for investigating and resolving challenging optimization issues, opening the door for further developments in quantum-inspired computing. In order to further improve the DA’s performance for particular issue classes, future work will attempt to extend this analysis to other constrained NP-hard problems and investigate hybrid workflows that use several solvers depending on instance features.
Authors and Affiliations: Markus Kirsch, Christian Münch, Stefan Walter, Fritz Schinkel, and Martin Kliesch from Fujitsu Germany GmbH, along with Salwa Shaglel and Marten Winkler from the Institute for Quantum Inspired and Quantum Optimization, Hamburg University of Technology, carried out the study.
You can also read Karnataka Funds ₹48 Crore for Quantum Research Park phase 2
