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
The Fujitsu Digital Annealer (DA) 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 DA’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 DA exploits the massive parallelization that custom application-specific CMOS hardware allows. We compare the performance of the DA 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 DA 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 DA 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 DA. 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 DA 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.
PDF ARXIV PREPRINT
Most Recent Papers
Scaling Overhead of Locality Reduction in Binary Optimization Problems
By Elisabetta Valiante, Maritza Hernandez, Amin Barzegar, & Helmut G. Katzgraber Recently, there has been considerable interest in solving optimization problems by mapping these onto a binary representation, sparked mostly by the use of quantum annealing machines....
Quantum Multiple Kernel Learning
By Seyed Shakib Vedaie, Moslem Noori, Jaspreet S. Oberoi, Barry C. Sanders, & Ehsan Zahedinejad Kernel methods play an important role in machine learning applications due to their conceptual simplicity and superior performance on numerous machine learning tasks....
Quantum Annealing Approaches to the Phase-Unwrapping Problem in Synthetic-Aperture Radar Imaging
By Khaled A. Helal Kelany, Nikitas Dimopoulos, Clemens P. J. Adolphs, Bardia Barabadi, & Amirali Baniasadi The focus of this work is to explore the use of quantum annealing solvers for the problem of phase unwrapping of synthetic aperture radar (SAR) images....
Finding the Ground State of Spin Hamiltonians with Reinforcement Learning
By Kyle Mills, Pooya Ronagh, & Isaac Tamblyn Reinforcement learning (RL) has become a proven method for optimizing a procedure for which success has been defined, but the specific actions needed to achieve it have not. Using a method we call "controlled online...
Variationally Scheduled Quantum Simulation
By Shunji Matsuura, Samantha Buck, Valentin Senicourt, & Arman Zaribafiyan Eigenstate preparation is ubiquitous in quantum computing, and a standard approach for generating the lowest-energy states of a given system is by employing adiabatic state preparation...