Scholarlink

<p>The spatial photonic Ising machine (SPIM) is a promising optical hardware solver for large-scale combinatorial optimization problems with dense interactions. As the SPIM can represent Ising problems with rank-one coupling matrices, multiplexed versions have been proposed to enhance applicability to higher-rank interactions. However, the multiplexing cost reduces implementation efficiency, and even without multiplexing, the SPIM can represent coupling matrices beyond rank-one. To clarify the intrinsic representation power of the SPIM, we propose spatial quadratic unconstrained binary optimization (spQUBO), a formulation of Ising problems with spatially convolutional structures. We prove that any spQUBO reduces to a two-dimensional spQUBO with the convolutional structure preserved, which can be efficiently implemented on the SPIM without multiplexing. We demonstrate its applicability to distance-based combinatorial optimization, including placement problems and clustering problems. These results advance our understanding of the class of optimization problems where SPIMs exhibit unique advantage in efficiency and scalability. Furthermore, the convolutional structure of spQUBO also enables efficient computation using Fast Fourier Transforms.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Convolutional formulation of large-scale quadratic unconstrained binary optimization with dense interactions

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年7月29日

查看全文
  • Hiroshi Yamashita,
  • Hideyuki Suzuki

摘要

The spatial photonic Ising machine (SPIM) is a promising optical hardware solver for large-scale combinatorial optimization problems with dense interactions. As the SPIM can represent Ising problems with rank-one coupling matrices, multiplexed versions have been proposed to enhance applicability to higher-rank interactions. However, the multiplexing cost reduces implementation efficiency, and even without multiplexing, the SPIM can represent coupling matrices beyond rank-one. To clarify the intrinsic representation power of the SPIM, we propose spatial quadratic unconstrained binary optimization (spQUBO), a formulation of Ising problems with spatially convolutional structures. We prove that any spQUBO reduces to a two-dimensional spQUBO with the convolutional structure preserved, which can be efficiently implemented on the SPIM without multiplexing. We demonstrate its applicability to distance-based combinatorial optimization, including placement problems and clustering problems. These results advance our understanding of the class of optimization problems where SPIMs exhibit unique advantage in efficiency and scalability. Furthermore, the convolutional structure of spQUBO also enables efficient computation using Fast Fourier Transforms.