Restoring Sparsity in Potts Machines via Mean-Field Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910241785905152 |
|---|---|
| author | Callahan-Coray, Kevin Lee, Kyle Jiang, Kyle Camsari, Kerem Y. |
| author_facet | Callahan-Coray, Kevin Lee, Kyle Jiang, Kyle Camsari, Kerem Y. |
| contents | Ising machines and related probabilistic hardware have emerged as promising platforms for NP-hard optimization and sampling. However, many practical problems involve constraints that induce dense or all-to-all couplings, undermining scalability and hardware efficiency. We address this constraint-induced density through two complementary approaches. First, we introduce a hardware-aware native formulation for multi-state probabilistic digits (p-dits) that avoids the locally dense intra-variable couplings required by binary Ising encodings. We validate p-dit dynamics by reproducing known critical behavior of the 2D Potts model. Second, we propose mean-field constraints (MFC), a hybrid scheme that replaces dense pairwise constraint couplings with dynamically updated single-node biases. Applied to balanced graph partitioning, MFC achieves solution quality comparable to exact all-to-all constraint formulations while dramatically reducing graph density. Finally, we demonstrate the practical impact of restored sparsity through an FPGA implementation that accelerates partitioning by more than an order of magnitude over CPU probabilistic solvers and by over two orders of magnitude over a Tabu Ising baseline. Together, these results outline a pathway for scaling constrained optimization on probabilistic hardware. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_04200 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Restoring Sparsity in Potts Machines via Mean-Field Constraints Callahan-Coray, Kevin Lee, Kyle Jiang, Kyle Camsari, Kerem Y. Statistical Mechanics Emerging Technologies Ising machines and related probabilistic hardware have emerged as promising platforms for NP-hard optimization and sampling. However, many practical problems involve constraints that induce dense or all-to-all couplings, undermining scalability and hardware efficiency. We address this constraint-induced density through two complementary approaches. First, we introduce a hardware-aware native formulation for multi-state probabilistic digits (p-dits) that avoids the locally dense intra-variable couplings required by binary Ising encodings. We validate p-dit dynamics by reproducing known critical behavior of the 2D Potts model. Second, we propose mean-field constraints (MFC), a hybrid scheme that replaces dense pairwise constraint couplings with dynamically updated single-node biases. Applied to balanced graph partitioning, MFC achieves solution quality comparable to exact all-to-all constraint formulations while dramatically reducing graph density. Finally, we demonstrate the practical impact of restored sparsity through an FPGA implementation that accelerates partitioning by more than an order of magnitude over CPU probabilistic solvers and by over two orders of magnitude over a Tabu Ising baseline. Together, these results outline a pathway for scaling constrained optimization on probabilistic hardware. |
| title | Restoring Sparsity in Potts Machines via Mean-Field Constraints |
| topic | Statistical Mechanics Emerging Technologies |
| url | https://arxiv.org/abs/2602.04200 |