SIOM Speeds Up Combinatorial Optimization at Large Spin Scales

Excellent Innovation Brief on Ultra-Intense Laser Science

(Issue 800)

July 21, 2026

Shanghai Institute of Optics and Mechanics Makes Progress in Accelerating the Solution of Large-Spin-Scale Combinatorial Optimization Problems

Recently, a team from the Optoelectronic Cross-Disciplinary Department at the Shanghai Institute of Optics and Fine Mechanics, Chinese Academy of Sciences, made new progress in solving large-scale combinatorial optimization problems with a spatial photonic Ising machine (SPIM). The related results, titled "Multi-channel spatial photonic Ising machine for the 102400-spin 0-1 knapsack problem solving," were published in Optics Letters.

Combinatorial optimization problems are widespread across key fields such as artificial intelligence, resource scheduling, route optimization, and financial investment. Among them, the 0-1 knapsack problem, as a typical NP-hard problem, is one of the benchmarks for testing algorithm performance, and is also a class of problems in which quantum computing can demonstrate superiority. Currently, quantum hardware is limited by physical qubit scale, coherence time, and error correction capability, and remains difficult to apply to large-scale combinatorial optimization problems. As the core physical model of quantum methods such as quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA), the Ising model also provides an effective mathematical mapping method for photonic computing. Leveraging the parallel, low-power characteristics of optics, the spatial photonic Ising machine (SPIM) holds great potential for solving large-scale Ising models. However, previous successful SPIM demonstrations on the knapsack problem were limited to small-scale instances. The core bottleneck is that, when mapping the knapsack problem to an Ising Hamiltonian, a few elements in the constructed coupling vector have absolute values far larger than the rest, so most small values are compressed to zero during quantization, causing severe information loss; meanwhile, these large-magnitude elements occupy only a few pixels, producing extremely weak optical signals that are hard to distinguish from noise.

To address this challenge, the research team proposed a Hamiltonian calibration scheme. Its core lies in optoelectronic hybrid processing: in the optical domain, abnormally large values in the coupling vector are set directly to zero, restoring bright, measurable diffraction signals; meanwhile, an analytical correction formula is used in the electronic domain to accurately reconstruct the original Hamiltonian. This strategy cleverly circumvents theSLMquantization precision limitation, enabling accurate restoration of the energy landscape.

Using a three-channel space-division multiplexingSPIMexperimental system, the team validated the method on a large-scale knapsack problem with102,400spins. Experiments showed that with the calibration scheme, the optical annealing curves matched digital simulations closely, whereas the original mapping scheme lost signal and produced completely distorted results. Across100repeated experiments, the average accuracy of feasible solutions obtained bySPIMreached99.34%, close to the99.51%of electronic computer simulations; moreover, a singleSPIMiteration took only0.572seconds, far better than the10.798seconds of the electronic computer.SPIMshowed stronger exploration in the search and, within the same limited number of solution attempts, could find higher-quality solutions with greater total value. This work effectively advancesSPIMin overcoming the scaling bottleneck of solving combinatorial optimization problems, providing a general strategy for combinatorial optimization problems with similar extreme coupling structures and demonstrating the practical application prospects of optoelectronic hybrid architectures.

Figure1. Schematic of the multi-channel spatial photonic Ising machine

Figure2. (a)Knapsack problemSPIMHamiltonian iteration curves;(b)SPIMknapsack problem solutions (green) compared with electronic computing results (blue); orange represents solutions violating the constraints

Original article link