Integer factorization, a cryptographic cornerstone, remains exponentially hard for classical computers, while quantum approaches, though theoretically polynomial-time, still face hardware limitations. We propose an Ising-accelerated lattice sieve method using a photonic Ising machine to solve the NP-hard closest vector problem efficiently. Our approach requires only sub-linear growth in spin number and stable dynamic range of the interaction matrix as integer bit-length increases, minimizing hardware demands. We construct a programmable spatial photonic Ising machine based on a Dammann grating. Through multi-path simulated annealing experiments on the constructed SPIM, we experimentally achieved the complete factorization of a 32-bit integer and demonstrated the identification of multiple distinct smooth relation pairs required for factorizing a 100-bit integer. To further validate the generality and scalability of the proposed method, we performed classical computer simulations of the multi-path annealing process, achieving factorization of integers up to 120 bits and establishing a benchmark for lattice sieve-based factorization.
Integer factorization, a cryptographic cornerstone, remains exponentially hard for classical computers, while quantum approaches, though theoretically polynomial-time, still face hardware limitations. We propose an Ising-accelerated lattice sieve method using a photonic Ising machine to solve the NP-hard closest vector problem efficiently. Our approach requires only sub-linear growth in spin number and stable dynamic range of the interaction matrix as integer bit-length increases, minimizing hardware demands. We construct a programmable spatial photonic Ising machine based on a Dammann grating. Through multi-path simulated annealing experiments on the constructed SPIM, we experimentally achieved the complete factorization of a 32-bit integer and demonstrated the identification of multiple distinct smooth relation pairs required for factorizing a 100-bit integer. To further validate the generality and scalability of the proposed method, we performed classical computer simulations of the multi-path annealing process, achieving factorization of integers up to 120 bits and establishing a benchmark for lattice sieve-based factorization.
Integer factorization, a fundamental problem in computational mathematics, holds critical significance for modern cryptography, particularly in RSA encryption. Traditional approaches such as the number field sieve face exponential complexity limitations, while Shor’s quantum algorithm remains impractical due to hardware constraints. This study proposes a universal algorithm for integer factorization based on Ising machines by transforming the problem into a Quadratic Unconstrained Binary Optimization (QUBO) formulation. The algorithm introduces an optimal reduction formula to optimize the parameter ranges of local field coefficients ( h ) and coupling coefficients ( J ) in the Ising model. Additionally, a non-uniform column grouping method is employed to resolve the conflict between coefficient ranges and carry auxiliary quantum bits(qubits), minimizing the number of auxiliary qubits with minimal compromise on coefficient ranges. Using this approach, we successfully factorized the 22-bit integer 2,093,809 with only 118 qubits. Extrapolating to existing photonic Ising machines with 100,000 qubits, our method demonstrates the potential to factorize 631-bit integers, highlighting its promise for efficient large-scale integer factorization. All results presented in this paper are obtained from simulations on Fixstars Amplify and D-Wave simulators.
We evaluate the performance of different algorithms in minimizing the Hamiltonian of a spatial-photonic Ising machine (SPIM). We then encode the number-partitioning problem on the SPIM and adiabatically arrive at good solutions for the problem for over 16000 spins, with a time complexity that only scales linearly with problem size. Finally, we benchmark our machine performance against the classical solver, Gurobi, and also a D-Wave 5000+ quantum annealer. With just one spatial light modulator, and and adiabatic evolution scheme for the phase, our results surpass current state-of-the-art SPIMs. We reduce hardware costs, and can solve larger problems more efficiently.
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.
The general-purpose programmable photonic processors offer a scalable and reconfigurable solution for a wide range of RF and optical applications. Therefore, implementing photonic Ising machines using programmable processors leverages the advantages of high speed and parallelism, enabling efficient hardware acceleration for finding ground-state solutions to combinatorial optimization problems. In this work, we demonstrate a novel programmable photonic Ising solver based on a hexagonal mesh general-purpose programmable photonic platform. The integrated system allows reconfigurable matrix multiplication and computes the Hamiltonian iteratively using an annealing algorithm that facilitates spin updates and effectively searches for the ground state. As a proof of concept, we experimentally solve two benchmark optimization problems, a fundamental three-node ferromagnetic coupling problem with external bias that demonstrates nontrivial spin interactions, and a four-node Max-Cut problem with arbitrary coupling matrices. Furthermore, to establish a large-scale capability, we emulated Ising problems with sizes up to N = 50, achieving success probabilities exceeding 80\%. Additionally, we examined the impact of errors, such as phase and coupling, on the performance of the programmable photonic Ising machine. Our general-purpose photonic Ising machine paves the way for implementing large-scale, programmable architectures for solving optimization problems.
Ising machines are an emerging class of hardware that promises ultrafast and energy-efficient solutions to NP-hard combinatorial optimization problems. Spatial photonic Ising machines (SPIMs) exploit optical computing in free space to accelerate the computation, showcasing parallelism, scalability, and low power consumption. However, current SPIMs can implement only a restricted class of problems. This partial programmability is a critical limitation that hampers their benchmark. Achieving full programmability of the device while preserving its scalability is an open challenge. Here, we report a fully programmable SPIM achieved through a novel operation method based on the division of the focal plane. In our scheme, a general Ising problem is decomposed into a set of Mattis Hamiltonians, whose energies are simultaneously computed optically by measuring the intensity on different regions of the camera sensor. Exploiting this concept, we experimentally demonstrate the computation with high success probability of ground-state solutions of up to 32-spin Ising models on unweighted maximum cut graphs with and without ferromagnetic bias. Simulations of the hardware prove a favorable scaling of the accuracy with the number of spin. Our fully programmable SPIM enables the implementation of many quadratic unconstrained binary optimization problems, further establishing SPIMs as a leading paradigm in non-von Neumann hardware.
Spatial photonic Ising machines (SPIMs) based on spatial light modulators (SLMs) have emerged as highly effective solvers for many tasks, including combinatorial optimization problems and spin-glass simulations. However, traditional SPIMs relying solely on the simulated annealing algorithm require a large number of measurement-feedback iterations to find a relatively optimal solution in complex energy landscapes, suffering from slow convergence and high time cost. Here, we propose an optical genetic-simulated annealing hybrid algorithm to accelerate the ground-state search of SPIMs. GA conducts a global coarse-grained search in the early iteration stage, while SA performs fine-grained local refinement in the late stage. Numerical simulations show that our method enables a higher solution quality of full-rank Max-Cut problems than pure GA or SA at different scales. We also experimentally demonstrate its superiority over conventional algorithms on a gauge-transformation time-division multiplexing SPIM for high-rank optimization problems under the same iteration budget. Our approach can be further developed with other advanced metaheuristic algorithms toward intelligent optical Ising computing systems.