Designing a K-state P-bit Engine
<|reference_start|>Designing a K-state P-bit Engine: Probabilistic bit (p-bit)-based compute engines utilize the unique capability of a p-bit to probabilistically switch between two states to solve computationally challenging problems. However, when solving problems that require more than two states (e.g., problems such as Max-3-Cut, verifying if a graph is K-partite (K>2) etc.), additional pre-processing steps such as graph reduction are required to make the problem compatible with a two-state p-bit platform. Moreover, this not only increases the problem size by entailing the use of auxiliary variables but can also degrade the solution quality. In this work, we develop a unique framework for implementing a K-state (K>2) p-bit engine. Furthermore, from an implementation standpoint, we show that such a K-state p-bit engine can be implemented using N traditional (2-state) p-bits, and one multi-state p-bit -- a novel concept proposed here. Augmenting traditional p-bit platforms, our approach enables us to solve an archetypal combinatoric problem class requiring multiple states, namely Max-K-Cut (K=3, 4 shown here), without using any additional auxiliary variables. Thus, our work fundamentally advances the functional capability of p-bit engines, enabling them to solve a broader class of computationally challenging problems more efficiently.<|reference_end|>
@article{bashar2024designing,
    title={Designing a K-state P-bit Engine},
    author={Mohammad Khairul Bashar, Abir Hasan, Nikhil Shukla},
    journal={arXiv preprint arXiv:2403.06436},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.06436},
    primaryClass={cs.ET math.OC physics.app-ph}
}