Extended-variable probabilistic computing with probabilistic d-dimensional bits

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 (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): (A) isotropic p-dits, which simplify the
implementation of categorical variables resulting in ~34x performance
improvement compared to a p-bit implementation on an example 3-partition
problem. (B) Probabilistic integers (p-ints), which simplify the
representation of numeric values and provide ~5x improvement compared to 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 ~64x
faster time-to-solution compared to 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.