Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo
arXiv:2407.10205 · doi:10.1007/s42484-024-00231-7
Abstract
Ising annealer is a promising quantum-inspired computing architecture for combinatorial optimization problems. In this paper, we introduce an Ising annealer based on the Hamiltonian Monte Carlo, which updates the variables of all dimensions in parallel. The main innovation is the fusion of an approximate gradient-based approach into the Ising annealer which introduces significant acceleration and allows a portable and scalable implementation on the commercial FPGA. Comprehensive simulation and hardware experiments show that the proposed Ising annealer has promising performance and scalability on all types of benchmark problems when compared to other Ising annealers including the state-of-the-art hardware. In particular, we have built a prototype annealer which solves Ising problems of both integer and fraction coefficients with up to 200 spins on a single low-cost FPGA board, whose performance is demonstrated to be better than the state-of-the-art quantum hardware D-Wave 2000Q and similar to the expensive coherent Ising machine. The sub-linear scalability of the annealer signifies its potential in solving challenging combinatorial optimization problems and evaluating the advantage of quantum hardware.
References in corpus (14)
- Ising formulations of many NP problems
- Adiabatic Quantum Computing
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
- QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- Massively Parallel Probabilistic Computing with Sparse Ising Machines
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Annealing by simulating the coherent Ising machine
- Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization
- A deceptive step towards quantum speedup detection
- 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
- Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian