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

By Maliheh Aramon, Gili Rosenberg, Elisabetta Valiante, Toshiyuki Miyazawa, Hirotaka Tamura, Helmut G. Katzgraber. Frontiers of Physics, 2018

446 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/2167700b8dbc3d56abc364a020bb65f8b554c8ce

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Quantum annealing for industry applications: introduction and review (2021, unknown): “In this case, comparison of the QA performance to alternative approaches using the Fujitsu digital annealer [11] and Gurobi software solver [73] did not show a clear benefit of utilizing the QA hardware.”
Ising machines as hardware solvers of combinatorial optimization problems (2022, background): “…small difference in the exponent can make a large difference in runtimes for large problem sizes, and the fast clock speeds of various physical implementations, which give rise to constant-factor improvements, could lead to signiﬁcant practical speedups versus conventional state-of-the-art solvers.”
Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems (2019, methodology): “…– 12 ) implemented with superconducting circuits ( 13 , 14 ), coherent Ising machines (CIMs) implemented with laser pulses ( 15 – 20 ), and Ising machines based on simulated annealing (SA) ( 1 , 21 , 22 ) implemented with digital circuits such as field-programmable gate arrays (FPGAs) ( 23 – 29 ).”
100,000-spin coherent Ising machine (2021, unknown): “These algorithms include those influenced by SA and quantum annealing ( 38 , 45 ), ones based on the simulation of a classical model of a quantum bifurcation machine ( 46 , 47 ), and ones based on the modification of stochastic differential equations for describing CIM behavior ( 48 , 49 ).”
Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models (2019, methodology): “Still more recently, Aramon et al. (2019) have investigated and tested the Fujitsu Digital Annealer approach, which is also designed to solve fully connected QUBO problems, implemented on application-speciﬁc CMOS hardware and solved problems of 1024 variables.”
Practical quantum advantage in quantum simulation (2022, unknown): “7 ).”