Digital Annealer Benchmarks Show Competitive Performance on Large-Scale Max-Cut Problems

Combinatorial optimisation problems underpin many areas of modern technology, from logistics and finance to machine learning, and finding efficient solutions remains a significant challenge. Salwa Shaglel, Markus Kirsch, and Marten Winkler, along with colleagues from Hamburg University of Technology and Fujitsu Germany, present a comprehensive evaluation of Fujitsu’s Digital Annealer, a specialised computer designed to tackle these complex problems. The team benchmarks the machine’s performance on the Max-Cut problem, a representative example of such challenges, using graphs with an impressive 53,000 variables. By comparing the Digital Annealer’s speed and accuracy against established heuristic algorithms and other quantum-inspired approaches, the researchers demonstrate its potential to deliver competitive results on large-scale problems, and highlight the current limits of heuristic solvers for these computationally intensive tasks.

Quantum and Classical Approaches to Optimization

This research explores the landscape of combinatorial optimization, a field dedicated to finding the best solutions from a vast number of possibilities. The study focuses on comparing different approaches, including quantum-inspired computing, traditional classical algorithms, and dedicated quantum hardware, to tackle challenging problems like Max-Cut, Steiner Trees, and the Traveling Salesperson. Researchers investigate how these methods perform on various problem instances, aiming to identify strengths and weaknesses of each approach. The study encompasses a wide range of techniques, from established classical methods like simulated annealing and genetic algorithms to more sophisticated approaches such as branch-and-cut and semidefinite programming.

Quantum and quantum-inspired methods, including quantum annealers and digital annealers, are also evaluated as potential solutions for complex optimization challenges. A key focus is benchmarking these methods against each other, using standardized problem instances and performance metrics. Researchers utilize established libraries and generators to create diverse test cases, ensuring a comprehensive evaluation of each algorithm. The study also explores hybrid approaches, combining the strengths of different techniques to achieve improved performance. This research provides valuable insights into the current state-of-the-art in combinatorial optimization, paving the way for future advancements in both classical and quantum computing.

Digital Annealer Benchmarking for Max-Cut Problems

Researchers rigorously assessed Fujitsu’s Digital Annealer (DA), a quantum-inspired computer, for its ability to solve complex optimization problems, specifically the Max-Cut problem. Recognizing the limitations of current quantum hardware, the study focused on evaluating a practical approach that can be implemented on classical computers. The methodology involved a direct comparison of the DA against established classical heuristics, quantum systems, and other emerging quantum-inspired platforms, ensuring a robust and fair evaluation of its performance. To establish a rigorous benchmark, the team constructed a large test suite comprising over 2,125 Max-Cut instances, carefully selecting the most powerful classical heuristics for comparison.

These heuristics were chosen based on their demonstrated performance across a range of problem sizes and densities, ensuring a challenging and representative test environment. The study adopted a time-limit methodology, assigning tailored computational budgets to each instance based on its inherent difficulty and accounting for expected improvements in hardware capabilities. Beyond comparing against classical algorithms, the researchers also evaluated the DA against D-Wave’s hybrid quantum-classical solver and a recently proposed quantum-inspired metaheuristic. This multi-faceted approach allowed for a nuanced understanding of the DA’s strengths and weaknesses relative to different computational paradigms. The study meticulously tracked not only the quality of the solutions obtained, but also the computational resources required, providing a comprehensive performance profile for each solver.

Digital Annealer Excels at Large Max-Cut Problems

Fujitsu’s Digital Annealer (DA), a quantum-inspired computer, demonstrates competitive performance in solving complex optimization problems, specifically the Max-Cut problem. Researchers benchmarked the DA against leading classical and quantum-inspired algorithms, including D-Wave’s hybrid system and a recently developed heuristic, using graphs containing up to 53,000 variables. The study reveals that the DA can effectively tackle these large instances, yielding results comparable to other state-of-the-art solvers. This research addresses a critical need for evaluating the capabilities of quantum-inspired hardware before fully functional quantum computers become available.

While current quantum hardware is limited by the number of qubits and susceptibility to noise, the DA offers a dedicated platform for exploring QUBO problems at scale, without these limitations. The DA’s performance was assessed using over 2,000 graphs from a standard benchmark library, and compared to results obtained from D-Wave’s system and the heuristic. The study highlights the importance of rigorous benchmarking in evaluating optimization algorithms and hardware. Researchers meticulously documented the benchmark setup, runtime limits, and performance details, ensuring transparency and comparability. The results suggest that the DA represents a valuable tool for exploring and solving complex optimization problems, paving the way for future advancements in quantum-inspired computing.

Digital Annealer Excels at Max-Cut Problems

This study presents a comprehensive benchmark of Fujitsu’s Digital Annealers, comparing their performance on the Max-Cut problem against leading classical heuristics, a hybrid quantum-classical solver, and a recently proposed quantum-inspired heuristic. Evaluating over 2,000 graphs with up to 53,000 variables, the results demonstrate that the Digital Annealer consistently finds better solutions than classical heuristics in approximately 69% of tested instances. Furthermore, the Digital Annealer outperformed the hybrid quantum-classical solver on specific instances with integer weights, while maintaining competitive performance overall. Researchers meticulously documented the benchmark setup, runtime limits, and performance details, ensuring transparency and comparability. The study provides valuable insights into the capabilities of quantum-inspired computing for solving complex optimization problems.