Limitations in Parallel Ising Machine Networks: Theory and Practice

Abstract

Analog Ising machines (IMs) occupy an increasingly prominent area of computer architecture research, offering high-quality and low latency/energy solutions to intractable computing tasks. However, IMs have a fixed capacity, with little to no utility in out-of-capacity problems. Previous works have proposed parallel, multi-IM architectures to circumvent this limitation. In this work we theoretically and numerically investigate tradeoffs in parallel IM networks to guide researchers in this burgeoning field. We propose formal models of parallel IM excution models, then provide theoretical guarantees for probabilistic convergence. Numerical experiments illustrate our findings and provide empirical insight into high and low synchronization frequency regimes. We also provide practical heuristics for parameter/model selection, informed by our theoretical and numerical findings.

19 pages, 11 figures

References in corpus (12)

• Ising formulations of many NP problems
• Adiabatic Quantum Computing
• Parallel Tempering: Theory, Applications, and New Perspectives
• Perspectives of quantum annealing: Methods and implementations
• Speed Limit for Classical Stochastic Processes
• Minimum entropy production, detailed balance and Wasserstein distance for continuous-time Markov processes
• Order-of-magnitude differences in computational performance of analog Ising machines induced by the choice of nonlinearity
• The Sherrington-Kirkpatrick model: an overview
• Hybrid quantum annealing for larger-than-QPU lattice-structured problems
• Parallel Tempering Simulation of the three-dimensional Edwards-Anderson Model with Compact Asynchronous Multispin Coding on GPU
• Ising-Based Louvain Method: Clustering Large Graphs with Specialized Hardware
• Wasserstein distance in speed limit inequalities for Markov jump processes