P-dits: Probabilistic d-dimensional bits for extended-variable probabilistic computing

This paper is a contribution to the Physical Review Applied collection titled Physics-Inspired Computing. Ising machines can solve combinatorial optimization problems by representing them as energy minimization problems. A common implementation is the probabilistic Ising machine (PIM), which uses probabilistic bits (P-bits) to represent coupled binary spins. However, many real-world problems have complex data representations that do not map naturally into a binary encoding, leading to a significant increase in hardware resources and time-to-solution. Here, we describe a generalized spin model that supports an arbitrary number of spin dimensions, each with an arbitrary real component. We define the probabilistic d-dimensional bit (P-dit) as the base unit of a P-computing implementation of this model. We further describe two restricted forms of P-dits for specific classes of common problems and implement them experimentally on an application-specific integrated circuit (ASIC): (i) isotropic P-dits, which simplify the implementation of categorical variables, resulting in ∼34× performance improvement compared with a P-bit implementation on an example three-partition problem and (ii) probabilistic integers (P-ints), which simplify the representation of numeric values and provide ∼5× improvement compared with a P-bit implementation of an example integer linear programming (ILP) problem. Additionally, we report a field-programmable gate array (FPGA) P-int-based integer quadratic programming (IQP) solver, which shows ∼64× faster time-to-solution compared with the best of a series of state-of-the-art software solvers. The generalized formulation of probabilistic variables presented here provides a path to solving large-scale optimization problems on various hardware platforms, including digital CMOS.