Massively parallel probabilistic computing with sparse Ising machines

Solving computationally hard problems using conventional computing architectures is often slow and energetically inefficient. Quantum computing may help with these challenges, but it is still in the early stages of development. A quantum-inspired alternative is to build domain-specific architectures with classical hardware. Here we report a sparse Ising machine that achieves massive parallelism where the flips per second-the key figure of merit-scales linearly with the number of probabilistic bits. Our sparse Ising machine architecture, prototyped on a field-programmable gate array, is up to six orders of magnitude faster than standard Gibbs sampling on a central processing unit, and offers 5-18 times improvements in sampling speed compared with approaches based on tensor processing units and graphics processing units. Our sparse Ising machine can reliably factor semi-primes up to 32 bits and it outperforms competition-winning Boolean satisfiability solvers in approximate optimization. Moreover, our architecture can find the correct ground state, even when inexact sampling is made with faster clocks. Our problem encoding and sparsification techniques could be applied to other classical and quantum Ising machines, and our architecture could potentially be scaled to 1,000,000 or more p-bits using analogue silicon or nanodevice technologies. Sparsification techniques can be used to create Ising machines prototyped on field-programmable gate arrays that can quickly and efficiently solve combinatorial optimization problems.

Automated summary

Solving hard problems using conventional computing architectures is slow and inefficient, but quantum computing is still in early stages. An alternative is to build domain-specific architectures with classical hardware. A sparse Ising machine is reported here, which achieves massive parallelism and is prototyped on a field-programmable gate array. It is significantly faster than standard methods by six orders of magnitude.