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.
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 Ising machine (IM) has emerged as a promising tool for tackling nondeterministic polynomial-time hard combinatorial optimization problems in real-world applications. Among various types of IMs, optoelectronic IMs based on electro-optical (EO) modulators stand out as an impressive platform for Ising computations. They offer a simple and stable architecture, with the EO modulator providing a natural inline nonlinear transfer function for the Ising model. However, integrated optoelectronic IMs have not been demonstrated until now, and exploring large-scale computations within the constraints of digital hardware resources remains an open challenge for these systems. In this paper, an integrated optoelectronic IM based on a thin-film lithium niobate (TFLN) photonic chip is presented, in conjunction with a sparse matrix–vector multiplication algorithm embedded in a field-programmable gate array that optimizes hardware resource utilization and minimizes computational latency. This setup allows us to solve multiple types of MAX-CUT problems with up to 2048 spins and achieve a remarkably low iteration latency of 1.78 μs. To further address the constraints posed by digital devices when tackling larger-scale Ising problems, we extend the application of the TFLN chip to yet another new scheme in which the single, compact on-chip modulator concurrently performs operations of linear multiplication and nonlinear transformation. This scheme demonstrates the capability to address large-scale MAX-CUT problems involving up to 16,384 spins, which, to the best of our knowledge, are the largest-scale problems solved on an on-chip IM, highlighting its potential to overcome digital limitations. The TFLN-based optoelectronic IMs provide a compact solution with high scalability for potentially practical applications in addressing complex combinatorial optimization problems.
With the growing demand for efficient computing to tackle complex real-world challenges like combinatorial optimization, both academia and industry are exploring alternative computing paradigms. The Ising machine (IM) is one such approach, solving optimization problems by mapping their cost functions onto the Ising model. In this framework, finding the optimal solution equates to determining the Ising spin configuration corresponding to the ground state of the Ising Hamiltonian. Analog IMs, relying on artificial spins that can take analogue rather than binary values, have shown great potential in reaching this ground at high speeds. Optical implementations, such as the opto-electronic IM developed within our research group, are particularly promising due to their higher bandwidth, energy efficiency, and lower latency compared to electronic IMs. However, scaling remains a challenge for large problems. To overcome this, we propose a novel analog optical IM utilizing a spatial light modulator (SLM). Our design differs from other IMs relying on SLMs by employing analog spin variables instead of binary ones and leveraging gradient descent-based feedback rather than a computer-driven Metropolis–Hastings sampling process. By exploiting the inherent parallelism of light, this SLM-based IM is expected to efficiently handle optimization problems with millions of spins while still maintaining high energy efficiency. At the conference, we will also offer more insight into the performance of these analogue IMs and will delve deeper in the bit resolution required for the different optical components such as the employed SLM. Based on the dynamical evolution of the IM, we will discuss strategies to further improve the problem-solving capacity and speed of these optical IMs.
Abstract Ising machines can efficiently solve real-world combinatorial optimization problems. Among them, photonic Ising machines (PIMs) exploit the parallelism and broadband bandwidth of optical systems to outperform digital computers in certain metrics. However, the bulky footprint of conventional discrete components imposes significant limitations on the miniaturization of current PIMs. Meanwhile, the scalability of problem size and spin connectivity density is constrained by limited computational resources. To address these challenges, we proposed and demonstrated an integrated PIM (IPIM) based on a hybrid architecture on a silicon-based photonic platform with an optical component footprint of 0.065 mm², achieved success rates exceeding 90% in finding global optimal solutions across all three benchmark tests. To tackle the common challenge in PIMs, where large-scale and high-connectivity-density problems naturally incur high computational complexity, we developed a joint algorithm with sparsity, inverse sparsity, and decomposition operations (JA-SID). Using this approach, we successfully solved Ising problems with sparse and dense spin connectivity, involving 102,400 spins. In addition, we introduced an optimized parameter configuration scheme (OPCS), which reduced the iteration count by over 50% for slowly converging problems, thereby lowering time complexity and power consumption. In practice, we used the IPIM to successfully partition a Facebook social network with over 60,000 users, demonstrating its capability to handle ultra-large-scale real-world problems. Our research substantially extended the applicability of IPIM, offering a promising solution to the increasing global demand for computational resources.
Ising machines (IMs) are hardware solvers designed to tackle computationally complex combinatorial optimization problems (COPs), harnessing physical processes such as quantum annealing to simulate the Ising model, enabling these specially designed solvers to tackle a wide range of computationally complex NP-hard problems in real-world applications, such as portfolio optimization and logistics planning. While prior works propose to fabricate dedicated integrated circuits for building IMs, we leverage off-the-shelf Graphics Processing Unit (GPU) chips for implementing Ising algorithms for quick development. In this work, we explore parallel tempering (PT), an Ising algorithm, which shows promise owing to its capability for parallel processing of multiple independent searches for the optimal solution, each with a different amount of randomness that allows escaping local minima. We propose several optimization strategies, including addressing the dependency problem in PT to enhance algorithm parallelism and integrating genetic algorithm (GA)-like operations to increase the diversity of the search process for effective solution discovery. Empirical evaluations demonstrate that our proposed Parallel Quantum-inspired Search (PQS) solver achieves a 2.66× speedup over the state-of-the-art GPU-based solution without sacrificing solution quality.
Oscillator-based Ising machines (OIMs) and oscillator-based Potts machines (OPMs) have emerged as promising hardware accelerators for solving NP-hard combinatorial optimization problems by leveraging the phase dynamics of coupled oscillators. In this work, a GPU-accelerated simulated OIM/OPM digital computation framework capable of solving combinatorial optimization problems is presented. The proposed implementation harnesses the parallel processing capabilities of GPUs to simulate large-scale OIM/OPMs, leveraging the advantages of digital computing to offer high precision, programmability, and scalability. The performance of the proposed GPU framework is evaluated on the max-cut problems from the GSET benchmark dataset and graph coloring problems from the SATLIB benchmarks dataset, demonstrating competitive speed and accuracy in tackling large-scale problems. The results from simulations, reaching up to 11295x speed-up over CPUs with up to 99% accuracy, establish this framework as a scalable, massively parallelized, and high-fidelity digital realization of OIM/OPMs.
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.