We demonstrates large-scale solving of the 0-1 knapsack problem using a spatially multiplexed optoelectronic Ising machine (SMOIM). The system achieves a significant scaling from previously reported 13 variables to 1,592 variables. Experimental results show that the optical solver reaches an average solution accuracy of 91.09%, closely matching computer-based simulated annealing performance (93.58%). The work confirms the effectiveness of SMOIM in handling high-rank combinatorial optimization problems and provides a foundation for solving extremely large-scale instances in the future.
We demonstrates large-scale solving of the 0-1 knapsack problem using a spatially multiplexed optoelectronic Ising machine (SMOIM). The system achieves a significant scaling from previously reported 13 variables to 1,592 variables. Experimental results show that the optical solver reaches an average solution accuracy of 91.09%, closely matching computer-based simulated annealing performance (93.58%). The work confirms the effectiveness of SMOIM in handling high-rank combinatorial optimization problems and provides a foundation for solving extremely large-scale instances in the future.
Combinatorial optimization problems are challenging for classical computing architectures, motivating the development of specialized hardware like Ising machines. The Spatial Photonic Ising Machine (SPIM) and its enhanced versions have shown promise in solving such problems by mapping them to the Ising model and leveraging optical parallelism to compute Hamiltonian energies efficiently. However, the 0-1 knapsack problem, as a representative combinatorial optimization problem, has only been reported to be solved effectively in small-scale SPIM. In this work, we analyze the factors that limit the spin scalability and propose a novel hardware-aware Hamiltonian mapping scheme to overcome this limitation. Based on this enhanced SPIM, the scheme is validated through simulated annealing experiments on a 102400-spin 0-1 knapsack problem, achieving high solution accuracy. Our method not only enables efficient solutions to large-scale 0-1 knapsack problems but also offers generalizability to other combinatorial optimization problems with similar coupling configurations. This work demonstrates the potential of SPIMs as scalable and adaptable solvers for real-world optimization challenges.
A spatial photonic Ising machine (SPIM) handles large-scale combinatorial optimization problems due to optical processing with spatial parallelism. However, iterative feedback in the search for an optimal solution limits processing speed, even though the Ising Hamiltonian is computed optically. We propose a parallel spatial photonic Ising machine (pSPIM) utilizing spatial multiplexing to search for an optimal solution efficiently. By employing grating patterns and encoding multiple configurations of Ising spins in a phase distribution, several Ising Hamiltonians are computed simultaneously. We demonstrated that the optimal solutions of max-cut problems with 100 Ising spins were obtained more frequently as the number of processing units increased. In addition, combining the multicomponent model with parallel processing provides an efficient search for optimal solutions to problems represented by using interaction matrices with a rank greater than one. The spin-update strategy of pSPIM offers an effective approach for efficiently solving large-scale combinatorial optimization problems.
ABSTRACT Many real‐world applications can be categorized as combinatorial optimization problems (COPs), yet their inherent NP‐hardness and exponential computational complexity pose significant barriers to efficient solutions. Designed specifically for solving COPs, the Ising machine (IM) demonstrates superior performance over traditional Von Neumann‐based computing architectures. Among different IM implementations, optical IMs (OIMs) are especially promising due to their inherent high‐speed and energy efficiency properties. Nevertheless, current OIMs are constrained by serial processing architectures, posing significant challenges for solving large‐scale COPs. To address this challenge, we propose and experimentally demonstrate a multiplexed parallel OIM architecture spanning the optical and electrical domains. The system solved a square lattice MAX‐CUT instance with over 100,000 spins and achieved a fourfold speedup with four‐channel parallelism. In addition, channel‐wise calibration mitigated device mismatch and aligned the nonlinear responses across channels, enabling the four‐channel system to maintain solution quality comparable to the single‐channel system across small benchmark problems of varying difficulty. We also explored a method combining hierarchical clustering and noise injection, which identified the known optimal route within the clustering‐constrained search space of the 14‐city TSP. These results demonstrate the potential of the proposed architecture for larger and more complex optimization problems.
The spatial photonic Ising machine (SPIM) [13D. Pierangeli et al., Large-Scale Photonic Ising Machine by Spatial Light Modulation, Phys. Rev. Lett. 122, 213902 (2019).PRLTAO0031-900710.1103/PhysRevLett.122.213902] is a promising optical architecture utilizing spatial light modulation for solving large-scale combinatorial optimization problems efficiently. The primitive version of the SPIM, however, can accommodate Ising problems with only rank-one interaction matrices. In this Letter, we propose a new computing model for the SPIM that can accommodate any Ising problem without changing its optical implementation. The proposed model is particularly efficient for Ising problems with low-rank interaction matrices, such as knapsack problems. Moreover, it acquires the learning ability of Boltzmann machines. We demonstrate that learning, classification, and sampling of the MNIST handwritten digit images are achieved efficiently using the model with low-rank interactions. Thus, the proposed model exhibits higher practical applicability to various problems of combinatorial optimization and statistical learning, without losing the scalability inherent in the SPIM architecture.
Ising machines based on analog systems have the potential to accelerate the solution of ubiquitous combinatorial optimization problems. Although some artificial spins to support large-scale Ising machines have been reported, e.g., superconducting qubits in quantum annealers and short optical pulses in coherent Ising machines, the spin stability is fragile due to the ultra-low equivalent temperature or optical phase sensitivity. In this paper, we propose to use short microwave pulses generated from an optoelectronic parametric oscillator as the spins to implement a large-scale Ising machine with high stability. The proposed machine supports 25,600 spins and can operate continuously and stably for hours. Moreover, the proposed Ising machine is highly compatible with high-speed electronic devices for programmability, paving a low-cost, accurate, and easy-to-implement way toward solving real-world optimization problems.
Abstract 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.