Scalable Connectivity for Ising Machines: Dense to Sparse

Abstract

In recent years, hardware implementations of Ising machines have emerged as a viable alternative to quantum computing for solving hard optimization problems among other applications. Unlike quantum hardware, dense connectivity can be achieved in classical systems. However, we show that dense connectivity leads to severe frequency slowdowns and interconnect congestion scaling unfavorably with system sizes. As a scalable solution, we propose a systematic sparsification method for dense graphs by introducing copy nodes to limit the number of neighbors per graph node. In addition to solving interconnect congestion, this approach enables constant frequency scaling where all spins in a network can be updated in constant time. On the other hand, sparsification introduces new difficulties, such as constraint-breaking between copied spins and increased convergence times to solve optimization problems, especially if exact ground states are sought. Relaxing the exact solution requirements, we find that the overheads in convergence times are milder. We demonstrate these ideas by designing probabilistic bit Ising machines using ASAP7 (a predictive 7nm FinFET technology model) process design kits as well as Field Programmable Gate Array (FPGA)-based implementations. Finally, we show how formulating problems in naturally sparse networks (e.g., by invertible logic) sidesteps challenges introduced by sparsification methods. Our results are applicable to a broad family of Ising machines using different hardware implementations.

References in corpus (19)

• Ising formulations of many NP problems
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Stochastic p-bits for Invertible Logic
• Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• Quantum Optimization of Fully-Connected Spin Glasses
• A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms
• Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
• Extremal Cuts of Sparse Random Graphs
• CMOS + stochastic nanomagnets: heterogeneous computers for probabilistic inference and learning
• Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
• Efficient CMOS Invertible Logic Using Stochastic Computing
• Scalable Emulation of Sign-Problem$-$Free Hamiltonians with Room Temperature p-bits
• CMOS-compatible Ising and Potts Annealing Using Single Photon Avalanche Diodes
• All-to-all reconfigurability with sparse and higher-order Ising machines
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
• Noise-augmented Chaotic Ising Machines for Combinatorial Optimization and Sampling

Cited by in corpus (3)

• Two-dimensional Parallel Tempering for Constrained Optimization
• Lagrange Oscillatory Neural Networks for Constraint Satisfaction and Optimization
• An improved update rule for probabilistic computers