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

Abstract

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.

16 pages, 11 Figures, 2 tables

References in corpus (42)

• Ising formulations of many NP problems
• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Parallel Tempering: Theory, Applications, and New Perspectives
• Quantum annealing with more than one hundred qubits
• Defining and detecting quantum speedup
• What is the Computational Value of Finite Range Tunneling?
• Feedback-optimized parallel tempering Monte Carlo
• Quantum Optimization of Fully-Connected Spin Glasses
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
• Quantum annealing versus classical machine learning applied to a simplified computational biology problem
• Probing for quantum speedup in spin glass problems with planted solutions
• Quantum Variational Autoencoder
• Optimized simulated annealing for Ising spin glasses
• A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Quantum Annealing Implementation of Job-Shop Scheduling
• An introduction to Monte Carlo methods
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
• Reexamining classical and quantum models for the D-Wave One processor
• Domain-Wall Free-Energy of Spin Glass Models:Numerical Method and Boundary Conditions
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• Population annealing: Theory and application in spin glasses
• A deceptive step towards quantum speedup detection
• Unraveling Quantum Annealers using Classical Hardness
• Building an iterative heuristic solver for a quantum annealer
• Enhancing Quantum Annealing Performance for the Molecular Similarity Problem
• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
• Practical engineering of hard spin-glass instances
• Exact Ground States of Large Two-Dimensional Planar Ising Spin Glasses
• The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
• Leveraging Adiabatic Quantum Computation for Election Forecasting
• A Novel Graph-based Approach for Determining Molecular Similarity
• Free energy-based reinforcement learning using a quantum processor
• Reinforcement Learning Using Quantum Boltzmann Machines
• borealis - A generalized global update algorithm for Boolean optimization problems
• A small-world search for quantum speedup: How small-world interactions can lead to improved quantum annealer designs
• Efficient Bayesian inference in stochastic chemical kinetic models using graphical processing units
• Parallel kinetic Monte Carlo simulation of Coulomb glasses

Cited by in corpus (123)

• Perspectives of quantum annealing: Methods and implementations
• Quantum Annealing for Industry Applications: Introduction and Review
• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• A Tutorial on Formulating and Using QUBO Models
• A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms
• Nanophotonic spin-glass for realization of a coherent Ising machine
• Demonstration of nanosecond operation in stochastic magnetic tunnel junctions
• Probabilistic computing with p-bits
• Traffic Signal Optimization on a Square Lattice with Quantum Annealing
• Roadmap for Unconventional Computing with Nanotechnology
• Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization
• Autonomous Probabilistic Coprocessing with Petaflips per Second
• Penalty Weights in QUBO Formulations: Permutation Problems
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Ising Machines' Dynamics and Regularization for Near-Optimal Large and Massive MIMO Detection
• High-accuracy Ising machine using Kerr-nonlinear parametric oscillators with local four-body interactions
• Data-Driven Optimal Sensor Placement for High-Dimensional System Using Annealing Machine
• Quantitative Evaluation of Hardware Binary Stochastic Neurons
• A novel design update framework for topology optimization with quantum annealing: Application to truss and continuum structures
• Simulated bifurcation assisted by thermal fluctuation
• Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks
• Simulated bifurcation for higher-order cost functions
• Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
• All-to-all reconfigurability with sparse and higher-order Ising machines
• Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning
• Tackling the challenge of a huge materials science search space with quantum-inspired annealing
• Physics-Inspired Heuristics for Soft MIMO Detection in 5G New Radio and Beyond
• Harnessing Intrinsic Noise in Memristor Hopfield Neural Networks for Combinatorial Optimization
• On-demand Photonic Ising Machine with Simplified Hamiltonian Calculation by Phase encoding and Intensity Detection
• Effects of setting the temperatures in the parallel tempering Monte Carlo algorithm
• Memristor-based hardware and algorithms for higher-order Hopfield optimization solver outperforming quadratic Ising machines
• Equation Planting: A Tool for Benchmarking Ising Machines
• Computational Overhead of Locality Reduction in Binary Optimization Problems
• Quantum Computing: Vision and Challenges
• Computational hardness of spin-glass problems with tile-planted solutions
• Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems
• Explainable AI using expressive Boolean formulas
• Effective electromagnetic actions for Lorentz violating theories exhibiting the axial anomaly
• Partitioning Dense Graphs with Hardware Accelerators
• Algorithmic QUBO Formulations for k-SAT and Hamiltonian Cycles
• Quantum Annealing Approach for the Optimal Real-time Traffic Control using QUBO
• Guiding Principle for Minor-Embedding in Simulated-Annealing-Based Ising Machines
• Energy landscapes of combinatorial optimization in Ising machines
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
• How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
• Discrete Polynomial Optimization with Coherent Networks of Condensates and Complex Coupling Switching
• Spatial-photonic Ising machine by space-division multiplexing with physically tunable coefficients of a multi-component model
• An Optimization Case Study for solving a Transport Robot Scheduling Problem on Quantum-Hybrid and Quantum-Inspired Hardware
• Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
• Multi-objective QUBO Solver: Bi-objective Quadratic Assignment
• Transit facility allocation: Hybrid quantum-classical optimization
• Uplink MIMO Detection using Ising Machines: A Multi-Stage Ising Approach
• Towards an Automatic Framework for Solving Optimization Problems with Quantum Computers
• Scalable Connectivity for Ising Machines: Dense to Sparse
• Hybrid Optimization Method Using Simulated-Annealing-Based Ising Machine and Quantum Annealer
• Image Analysis Based on Nonnegative/Binary Matrix Factorization
• Emulating Quantum Interference with Generalized Ising Machines
• A QUBO Algorithm to Compute Eigenvectors of Symmetric Matrices
• Computing Graph Edit Distance with Algorithms on Quantum Devices
• Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem
• Using continuation methods to analyse the difficulty of problems solved by Ising machines
• Efficient quantum and simulated annealing of Potts models using a half-hot constraint
• OIM: Oscillator-based Ising Machines for Solving Combinatorial Optimisation Problems
• Clustering Method for Time-Series Images Using Quantum-Inspired Computing Technology
• GPU-accelerated simulated annealing based on p-bits with real-world device-variability modeling
• Approaching Collateral Optimization for NISQ and Quantum-Inspired Computing
• Dynamical process of a bit-width reduced Ising model with simulated annealing
• PyQUBO: Python Library for Mapping Combinatorial Optimization Problems to QUBO Form
• Separability gap and large deviation entanglement criterion
• Two-dimensional Parallel Tempering for Constrained Optimization
• Binary matrix factorization on special purpose hardware
• Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems
• Ising-Based Louvain Method: Clustering Large Graphs with Specialized Hardware
• Accelerating Optimal Elemental Configuration Search in Crystal using Ising Machine
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Market Graph Clustering Via QUBO and Digital Annealing
• Quantum Integer Programming (QuIP) 47-779: Lecture Notes
• Graph clustering with Boltzmann machines
• Restricted Boltzmann Machines for galaxy morphology classification with a quantum annealer
• General Oscillator-Based Ising Machine Models with Phase-Amplitude Dynamics and Polynomial Interactions
• Linearizing Binary Optimization Problems Using Variable Posets for Ising Machines
• Quantum annealing in the NISQ era: railway conflict management
• Deep Unfolded Local Quantum Annealing
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Parallel Tempering-Inspired Distributed Binary Optimization with In-Memory Computing
• Optimization via Quantum Preconditioning
• Analysis of the Hopfield Model with Discrete Coupling
• Solving the Optimal Trading Trajectory Problem Using Simulated Bifurcation
• Multi-Community Detection in Signed Graphs Using Quantum Hardware
• Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo
• Derivation of QUBO formulations for sparse estimation
• Collaborative filtering based on nonnegative/binary matrix factorization
• Graph Clustering Via QUBO and Digital Annealing
• A Study of Scalarisation Techniques for Multi-Objective QUBO Solving
• Efficient correlation-based discretization of continuous variables for annealing machines
• Triple decomposition and sparse representation for noisy pressure-sensitive paint data
• Pattern Formation Simulated by an Ising Machine
• It's Quick to be Square: Fast Quadratisation for Quantum Toolchains
• Self-Adaptive Ising Machines for Constrained Optimization
• Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
• QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver Surrogates
• Improving the convergence of an iterative algorithm for solving arbitrary linear equation systems using classical or quantum binary optimization
• Graph Distances and Clustering
• Characterization of Locality in Spin States and Forced Moves for Optimizations
• Subsampling Factorization Machine Annealing
• Koopman analysis of combinatorial optimization problems with replica exchange Monte Carlo method
• Routing and Wavelength Assignment with Protection: A Quadratic Unconstrained Binary Optimization Approach
• CAIM: Cooperative Angle of Arrival Estimation using the Ising Method
• Performance of the Extended Ising Machine for the Quadratic Knapsack Problem
• A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization
• Accelerating Hybrid XOR$-$CNF Boolean Satisfiability Problems Natively with In-Memory Computing
• Quantum-inspired search method for low-energy states of classical Ising Hamiltonians
• Surrogate Modeling via Factorization Machine and Ising Model with Enhanced Higher-Order Interaction Learning
• Large-scale portfolio optimization with variational neural annealing
• Quantum-inspired Ising machine using sparsified spin connectivity
• Quantum annealing and condensed matter physics
• 2022 Roadmap on Neuromorphic Computing and Engineering
• Energy-Efficient p-Bit-Based Fully-Connected Quantum-Inspired Simulated Annealer with Dual BRAM Architecture
• Minor-embedding heuristics for large-scale annealing processors with sparse hardware graphs of up to 102,400 nodes
• Polaritonic XY-Ising Machine