Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Supercomputing India (SCI)

GPU-Based Digital Annealing for Accelerating Large-Scale Combinatorial Optimization

Nistala Krishna Vamsi, Ashutosh Kumar Singh, A K Prabhakar

Published Dec 9, 2025• 0 citations
Publisher

Abstract

We present a GPU-based digital annealer (DA) implementation to efficiently solve large-scale combinatorial optimization problems mapped onto Ising spin models. Our implementation employs Metropolis-Hastings dynamics with simulated annealing on NVIDIA A-100 GPUs, achieving up to 40-fold speedup over sequential CPU implementations for 32,000 -spin problems and scaling to 65,025 spins. Comprehensive benchmarking on the standard maxcut “Gset” dataset reveals that our DA consistently outperforms the commercial Gurobi optimiser across most of density-topology classes, achieving superior solution quality (lower optimality gaps), computational efficiency ($2.4 \times$ to $40.8 \times$ speedup), and high success rates ($83.3 \%$ average, with perfect performance on sparse Erdős-Rényi and moderatedensity skewed graphs). For cryptographic bent function discovery, our DA successfully identifies solutions up to 12 variables within minutes, significantly outperforming D-Wave’s quantum annealer, which fails to report results beyond 4 variables due to hardware connectivity constraints.

DOI
10.1109/sci68648.2025.11333858

Related papers

Digital Annealer for High-Speed Solving of Combinatorial optimization Problems and Its Applications

Satoshi Matsubara, Motomu Takatsu, Toshiyuki Miyazawa +4 more

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.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2020•176 citations

Benchmarks and Recommendations for Quantum, Digital, and GPU Annealers in Combinatorial Optimization

Jehn‐Ruey Jiang, Yu‐Chen Shu, Qiao-Yi Lin

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.

IEEE Access•Jan 1, 2024•18 citations

A comprehensive benchmark of an Ising machine on the Max-Cut problem

Salwa Shaglel, Markus Kirsch, Mårten Winkler +4 more

Abstract Quadratic unconstrained binary optimization (QUBO) formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu’s Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum–classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.

arXiv:2507.22117•New Journal of Physics•Jun 5, 2026•2 citations

Oscillator-based Ising machine applied for Max-Cut in massively large and sparse graphs

Luciano Mazza, Eleonora Raimondo, Mario Carpentieri +2 more

Solving large-scale combinatorial optimization problems, such as Max-Cut, is crucial for a variety of applications such as network analysis and finance. Ising machines are emerging as unconventional computing paradigms for facing those problems while promising to reduce energy consumption and time-to-solution as compared to traditional methods such as the Goemans-Williamson algorithm. Here, we implement and benchmark a Graphics Processing Unit (GPU)-native software-based implementation of oscillator-based Ising machine (OIM) which can solve Max-Cut problems up to 20 million spins within a regular graph with degree 25. The benchmarked implementation is running on a single GPU, but it is scalable to multi-GPU platforms. Additionally, we identify an annealing strategy that searches the ground state with the help of dynamical checkpoints as bifurcation points in the dynamical phase space of the Max-Cut problems mapped into the Ising Hamiltonian, enabling the algorithm for a fast local search. The OIM consistently achieves accuracy averaging above 99.5% (up to 99.9%) for G-set problems.

Scientific Reports•Aug 26, 2026•0 citations

Binary optimization by momentum annealing

Takuya Okuyama, Tomohiro Sonobe, Ken‐ichi Kawarabayashi +1 more

One of the vital roles of computing is to solve large-scale combinatorial optimization problems in a short time. In recent years, methods have been proposed that map optimization problems to ones of searching for the ground state of an Ising model by using a stochastic process. Simulated annealing (SA) is a representative algorithm. However, it is inherently difficult to perform a parallel search. Here we propose an algorithm called momentum annealing (MA), which, unlike SA, updates all spins of fully connected Ising models simultaneously and can be implemented on GPUs that are widely used for scientific computing. MA running in parallel on GPUs is 250 times faster than SA running on a modern CPU at solving problems involving 100 000 spin Ising models.

Physical review. E•Jul 10, 2019•102 citations

Accelerating the Max-Cut Problems via Distributed Ising Machine Solvers

Xing-Yu Wu, Yi-Xin Zhang, Chen-rui Fan +1 more

The Ising machine, as a quantum-inspired computing system, can be used to efficiently solve combinatorial optimization problems. Ongoing studies have positioned it to potentially surpass the performance limitations of traditional computers. However, such Ising machines also suffer from scalability as the solution quality becomes sub-optimal when the problem size increases. In this work, we propose an Ising-based framework that uses a distributed Ising algorithm to find the near-optimal solution for large-scale Max-Cut problems through parallel processing via graph segmentation and reassembly. We selected the coherent Ising machine as the hardware solver and successfully found the solution for a 2000-node instance utilizing 20 computational bits on the Gset standard dataset. Additionally, we investigated the key factors influencing the system's performance and discovered that setting the number of reorganizations to one results in higher accuracy. Building on this configuration, we utilized a 100-bit CIM hardware platform (CPQC-1) to solve instances with varying numbers of nodes. The experimental results agree well with the theoretical simulations, confirming the practical feasibility of our method. Moreover, compared to existing Ising-based solvers, our algorithm significantly reduces computational resource requirements while achieving superior performance on large-scale combinatorial optimization problems, highlighting its effectiveness on quantum-inspired hardware.

IEEE Transactions on Quantum Engineering•Jan 1, 2026•0 citations
We present a GPU-based digital annealer (DA) implementation to efficiently solve large-scale combinatorial optimization problems mapped onto Ising spin models. Our implementation employs Metropolis-Hastings dynamics with simulated annealing on NVIDIA A-100 GPUs, achieving up to 40-fold speedup over sequential CPU implementations for 32,000 -spin problems and scaling to 65,025 spins. Comprehensive benchmarking on the standard maxcut “Gset” dataset reveals that our DA consistently outperforms the commercial Gurobi optimiser across most of density-topology classes, achieving superior solution quality (lower optimality gaps), computational efficiency (2.4×2.4 \times2.4× to 40.8×40.8 \times40.8× speedup), and high success rates (83.3%83.3 \%83.3% average, with perfect performance on sparse Erdős-Rényi and moderatedensity skewed graphs). For cryptographic bent function discovery, our DA successfully identifies solutions up to 12 variables within minutes, significantly outperforming D-Wave’s quantum annealer, which fails to report results beyond 4 variables due to hardware connectivity constraints.
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.
Abstract Quadratic unconstrained binary optimization (QUBO) formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu’s Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum–classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.
Solving large-scale combinatorial optimization problems, such as Max-Cut, is crucial for a variety of applications such as network analysis and finance. Ising machines are emerging as unconventional computing paradigms for facing those problems while promising to reduce energy consumption and time-to-solution as compared to traditional methods such as the Goemans-Williamson algorithm. Here, we implement and benchmark a Graphics Processing Unit (GPU)-native software-based implementation of oscillator-based Ising machine (OIM) which can solve Max-Cut problems up to 20 million spins within a regular graph with degree 25. The benchmarked implementation is running on a single GPU, but it is scalable to multi-GPU platforms. Additionally, we identify an annealing strategy that searches the ground state with the help of dynamical checkpoints as bifurcation points in the dynamical phase space of the Max-Cut problems mapped into the Ising Hamiltonian, enabling the algorithm for a fast local search. The OIM consistently achieves accuracy averaging above 99.5% (up to 99.9%) for G-set problems.
One of the vital roles of computing is to solve large-scale combinatorial optimization problems in a short time. In recent years, methods have been proposed that map optimization problems to ones of searching for the ground state of an Ising model by using a stochastic process. Simulated annealing (SA) is a representative algorithm. However, it is inherently difficult to perform a parallel search. Here we propose an algorithm called momentum annealing (MA), which, unlike SA, updates all spins of fully connected Ising models simultaneously and can be implemented on GPUs that are widely used for scientific computing. MA running in parallel on GPUs is 250 times faster than SA running on a modern CPU at solving problems involving 100 000 spin Ising models.
The Ising machine, as a quantum-inspired computing system, can be used to efficiently solve combinatorial optimization problems. Ongoing studies have positioned it to potentially surpass the performance limitations of traditional computers. However, such Ising machines also suffer from scalability as the solution quality becomes sub-optimal when the problem size increases. In this work, we propose an Ising-based framework that uses a distributed Ising algorithm to find the near-optimal solution for large-scale Max-Cut problems through parallel processing via graph segmentation and reassembly. We selected the coherent Ising machine as the hardware solver and successfully found the solution for a 2000-node instance utilizing 20 computational bits on the Gset standard dataset. Additionally, we investigated the key factors influencing the system's performance and discovered that setting the number of reorganizations to one results in higher accuracy. Building on this configuration, we utilized a 100-bit CIM hardware platform (CPQC-1) to solve instances with varying numbers of nodes. The experimental results agree well with the theoretical simulations, confirming the practical feasibility of our method. Moreover, compared to existing Ising-based solvers, our algorithm significantly reduces computational resource requirements while achieving superior performance on large-scale combinatorial optimization problems, highlighting its effectiveness on quantum-inspired hardware.