Nikhar Srijan, Kannan Sidharth, Aadit Navid Anjum, Chowdhury Shuvro, Camsari Kerem Y
Department of Electrical and Computer Engineering, University of California, Santa Barbara, Santa Barbara, CA, 93106, USA.
Nat Commun. 2024 Oct 17;15(1):8977. doi: 10.1038/s41467-024-53270-w.
Domain-specific hardware to solve computationally hard optimization problems has generated tremendous excitement. Here, we evaluate probabilistic bit (p-bit) based Ising Machines (IM) on the 3-Regular 3-Exclusive OR Satisfiability (3R3X), as a representative hard optimization problem. We first introduce a multiplexed architecture that emulates all-to-all network functionality while maintaining highly parallelized chromatic Gibbs sampling. We implement this architecture in a single Field-Programmable Gate Array (FPGA) and show that running the adaptive parallel tempering algorithm demonstrates competitive algorithmic and prefactor advantages over alternative IMs by D-Wave, Toshiba, and Fujitsu. We also implement higher-order interactions that lead to better prefactors without changing algorithmic scaling for the XORSAT problem. Even though FPGA implementations of p-bits are still not quite as fast as the best possible greedy algorithms accelerated on Graphics Processing Units (GPU), scaled magnetic versions of p-bit IMs could lead to orders of magnitude improvements over the state of the art for generic optimization.
用于解决计算困难的优化问题的特定领域硬件引发了极大的关注。在此，我们将基于概率比特（p比特）的伊辛机（IM）应用于3正则3异或可满足性问题（3R3X），这是一个具有代表性的困难优化问题。我们首先介绍一种复用架构，该架构在保持高度并行化的彩色吉布斯采样的同时，模拟全对全网络功能。我们在单个现场可编程门阵列（FPGA）中实现了这种架构，并表明运行自适应并行回火算法相较于D-Wave、东芝和富士通的其他IM，展现出了具有竞争力的算法和前置因子优势。我们还实现了高阶相互作用，在不改变异或可满足性问题算法缩放比例的情况下，带来了更好的前置因子。尽管p比特的FPGA实现仍不如在图形处理单元（GPU）上加速的最佳贪心算法快，但p比特IM的缩放磁版本可能会在通用优化方面比现有技术提高几个数量级。
