All-to-all reconfigurability with sparse and higher-order Ising machines

Abstract

Domain-specific hardware to solve computationally hard optimization problems has generated tremendous excitement. Here, we evaluate probabilistic bit (p-bit) based Ising Machines (IM) on the 3-regular 3-Exclusive OR Satisfiability (3R3X), as a representative hard optimization problem. We first introduce a multiplexed architecture that emulates all-to-all network functionality while maintaining highly parallelized chromatic Gibbs sampling. We implement this architecture in single Field-Programmable Gate Arrays (FPGA) and show that running the adaptive parallel tempering algorithm demonstrates competitive algorithmic and prefactor advantages over alternative IMs by D-Wave, Toshiba, and Fujitsu. We also implement higher-order interactions that lead to better prefactors without changing algorithmic scaling for the XORSAT problem. Even though FPGA implementations of p-bits are still not quite as fast as the best possible greedy algorithms accelerated on Graphics Processing Units (GPU), scaled magnetic versions of p-bit IMs could lead to orders of magnitude improvements over the state of the art for generic optimization.

S.N, S. K, N.A.A are equally contributing first authors

References in corpus (8)

• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Accelerated Quantum Monte Carlo with Probabilistic Computers
• Simulated bifurcation for higher-order cost functions
• Memristor-based hardware and algorithms for higher-order Hopfield optimization solver outperforming quadratic Ising machines
• How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
• Benchmarking the Operation of Quantum Heuristics and Ising Machines: Scoring Parameter Setting Strategies on Optimization Applications

Cited by in corpus (14)

• Noise-augmented Chaotic Ising Machines for Combinatorial Optimization and Sampling
• Scalable Connectivity for Ising Machines: Dense to Sparse
• Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
• SUANPAN: Scalable Photonic Linear Vector Machine
• The First Hardware Demonstration of a Universal Programmable RRAM-based Probabilistic Computer for Molecular Docking
• Many-body computing on Field Programmable Gate Arrays
• Tunable Random Telegraph Noise in Stable Perpendicular Magnetic Tunnel Junctions for Unconventional Computing
• Superparamagnetic and Stochastic-Write Magnetic Tunnel Junctions for High-Speed True Random Number Generation in Advanced Computing
• Overcoming Quadratic Hardware Scaling for a Fully Connected Digital Oscillatory Neural Network
• Generalized Probabilistic Approximate Optimization Algorithm
• A Statistical Analysis for Per-Instance Evaluation of Stochastic Optimizers: Avoiding Unreliable Conclusions
• Metrics for spin-based computing
• An improved update rule for probabilistic computers
• Accelerating Hybrid XOR$-$CNF Boolean Satisfiability Problems Natively with In-Memory Computing