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

Asilomar Conference on Signals, Systems and Computers (ACSSC)

Digital Annealing with Parallel Flip Dynamics

George Higgins Hutchinson, Tinish Bhattacharya, Arne Heittmann, Dmitri B. Strukov

Published Oct 26, 2025• 0 citations
Publisher

Abstract

Digital Annealing (DA) is an enhancement of the simulated annealing (SA) algorithm, achieved through a paralleltrial update scheme that boosts the flip acceptance rate, and a dynamic escape mechanism that helps overcome narrow energy barriers. In each parallel-trial iteration of the DA algorithm, every variable of the problem is independently proposed ("tried") for a flip. If any such candidate flips are accepted, a single candidate flip is then selected at random and applied. The primary contribution of this work is an improvement of the DA algorithm through parallel-flip dynamics, in which multiple candidate variable flips are applied within a single parallel-trial iteration. By utilizing computations of a parallel-trial scheme more efficiently, the enhanced algorithm exhibits faster convergence and a more favorable scaling exponent with respect to the number of parallel-trial iterations. This is demonstrated by benchmarking uniform random-SAT problems, where the algorithm outperforms other local search methods. To further motivate these results, we show that the proposed algorithm is well-suited for an efficient implementation on recently developed in-memory-computing parallel-gradient hardware, highlighting its potential for next-generation optimization solver accelerators.

DOI
10.1109/ieeeconf67917.2025.11443515

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•163 citations

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

Nistala Krishna Vamsi, Ashutosh Kumar Singh, A K Prabhakar

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.

Supercomputing India (SCI)•Dec 9, 2025•0 citations

A Parallel Hardware Architecture For Quantum Annealing Algorithm Acceleration

Evelina Forno, Andrea Acquaviva, Yuki Kobayashi +2 more

Quantum Annealing (QA) is an emerging technique, derived from Simulated Annealing, providing metaheuristics for multivariable optimisation problems. Studies have shown that it can be applied to solve NP-hard problems with faster convergence and better quality of result than other traditional heuristics, with potential applications in a variety of fields, from transport logistics to circuit synthesis and optimisation. In this paper, we present a hardware architecture implementing a QA-based solver for the Multidimensional Knapsack Problem, designed to improve the performance of the algorithm by exploiting parallelised computation. We synthesised the architecture using as a target an Altera FPGA board and simulated the execution for solving a set of benchmarks available in the literature. Simulation results show that the proposed implementation is about 100 times faster than a single-thread general-purpose CPU without impact on the accuracy of the solution.

IFIP/IEEE International Conference on Very Large Scale Integration•Oct 1, 2018•9 citations

Quantum Simulated Annealing Algorithm

Rana Fareed Ghani

Simulated annealing (SA) has been considered as a good tool for searchand optimization problems which represent the abstraction of obtaining thecrystalline structure through a physical process. This algorithm works sequentiallythat the current state will produce only one next state. That will make the search tobe slower and the important drawback is that the search may fall in local minimumwhich represent the best solution in only part of the solution space. In this workwe present the transformation of Simulated Annealing algorithm into quantumversion which will be called Quantum Simulated Annealing (QSA). Thisalgorithm will overcome the drawbacks of slowness and local minimum falling byproduce as much as possible of the neighbor states and work on in parallel byexploiting the massive parallelism feature in quantum computation. The resultsshow that QSA can find the optimal path in smaller number of iterations than thesequential simulated annealing algorithm and the time complexity of QSA isbetter than any other parallel simulated annealing algorithm.

Engineering and Technology Journal•May 1, 2010•1 citation

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•92 citations

Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer

Maliheh Aramon, Gili Rosenberg, Elisabetta Valiante +3 more

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.

arXiv:1806.08815•Frontiers in Physics•Apr 5, 2019•439 citations
Digital Annealing (DA) is an enhancement of the simulated annealing (SA) algorithm, achieved through a paralleltrial update scheme that boosts the flip acceptance rate, and a dynamic escape mechanism that helps overcome narrow energy barriers. In each parallel-trial iteration of the DA algorithm, every variable of the problem is independently proposed ("tried") for a flip. If any such candidate flips are accepted, a single candidate flip is then selected at random and applied. The primary contribution of this work is an improvement of the DA algorithm through parallel-flip dynamics, in which multiple candidate variable flips are applied within a single parallel-trial iteration. By utilizing computations of a parallel-trial scheme more efficiently, the enhanced algorithm exhibits faster convergence and a more favorable scaling exponent with respect to the number of parallel-trial iterations. This is demonstrated by benchmarking uniform random-SAT problems, where the algorithm outperforms other local search methods. To further motivate these results, we show that the proposed algorithm is well-suited for an efficient implementation on recently developed in-memory-computing parallel-gradient hardware, highlighting its potential for next-generation optimization solver accelerators.
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.
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.
Quantum Annealing (QA) is an emerging technique, derived from Simulated Annealing, providing metaheuristics for multivariable optimisation problems. Studies have shown that it can be applied to solve NP-hard problems with faster convergence and better quality of result than other traditional heuristics, with potential applications in a variety of fields, from transport logistics to circuit synthesis and optimisation. In this paper, we present a hardware architecture implementing a QA-based solver for the Multidimensional Knapsack Problem, designed to improve the performance of the algorithm by exploiting parallelised computation. We synthesised the architecture using as a target an Altera FPGA board and simulated the execution for solving a set of benchmarks available in the literature. Simulation results show that the proposed implementation is about 100 times faster than a single-thread general-purpose CPU without impact on the accuracy of the solution.
Simulated annealing (SA) has been considered as a good tool for searchand optimization problems which represent the abstraction of obtaining thecrystalline structure through a physical process. This algorithm works sequentiallythat the current state will produce only one next state. That will make the search tobe slower and the important drawback is that the search may fall in local minimumwhich represent the best solution in only part of the solution space. In this workwe present the transformation of Simulated Annealing algorithm into quantumversion which will be called Quantum Simulated Annealing (QSA). Thisalgorithm will overcome the drawbacks of slowness and local minimum falling byproduce as much as possible of the neighbor states and work on in parallel byexploiting the massive parallelism feature in quantum computation. The resultsshow that QSA can find the optimal path in smaller number of iterations than thesequential simulated annealing algorithm and the time complexity of QSA isbetter than any other parallel simulated annealing algorithm.
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 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.