Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2308.14156

A Reconfigurable Photonic Processor for NP-complete Problems

Xiaoyun Xu, Tianyu Zhang, Ziwei Wang, Chu-Han Wang, Xian‐Min Jin

Published Aug 27, 2023• 2 citations
arXivHTMLPDF

Abstract

NP-complete problems are widely and deeply involved in various real-life scenarios while still intractable to solve efficiently on conventional computers. It is of great practical significance to construct versatile computing architectures that solve NP-complete problems with computational advantage. Here, we present a reconfigurable photonic processor to efficiently solve a benchmark NP-complete problem, the subset sum problem (SSP). We show that in the case of successive primes, the photonic processor has genuinely surpassed commercial electronic processors launched recently by taking advantages of the high propagation speed and vast parallelism of photons and state-of-the-art integrated photonic technology. Moreover, we are able to program the photonic processor to tackle different problem instances relying on the tunable integrated modules, variable split junctions, which can be used to build a fully reconfigurable architecture potentially allowing $2^{N}$ configurations at most. Our experiments confirm the potential of the photonic processor as a versatile and efficient computing platform, suggesting a possible practical route to solving computationally hard problems at large scale.

DOI
10.48550/arxiv.2308.14156

Related papers

Reconfigurable integrated photonic processor for NP-complete problems

Xiao-Yun Xu, Tian-Yu Zhang, Ziwei Wang +2 more

Nondeterministic-polynomial-time (NP)-complete problems are widely involved in various real-life scenarios but are still intractable in being solved efficiently on conventional computers. It is of great practical significance to construct versatile computing architectures that solve NP-complete problems with computational advantage. Here, we present a reconfigurable integrated photonic processor to efficiently solve a benchmark NP-complete problem, the subset sum problem. We show that in the case of successive primes, the photonic processor has genuinely surpassed electronic processors launched recently by taking advantage of the high propagation speed and vast parallelism of photons and state-of-the-art integrated photonic technology. Moreover, we are able to program the photonic processor to tackle different problem instances, relying on the tunable integrated modules, variable split junctions, which can be used to build a fully reconfigurable architecture potentially allowing 2N configurations at most. Our experiments confirm the potential of the photonic processor as a versatile and efficient computing platform, suggesting a possible practical route to solving computationally hard problems at a large scale.

Advanced Photonics•Sep 24, 2024•11 citations

A scalable photonic computer solving the subset sum problem

Xiao-Yun Xu, Xuan-Lun Huang, Zhan-Ming Li +6 more

The subset sum problem (SSP) is a typical nondeterministic-polynomial-time (NP)-complete problem that is hard to solve efficiently in time with conventional computers. Photons have the unique features of high propagation speed, strong robustness, and low detectable energy level and therefore can be promising candidates to meet the challenge. Here, we present a scalable chip built-in photonic computer to efficiently solve the SSP. We map the problem into a three-dimensional waveguide network through a femtosecond laser direct writing technique. We show that the photons sufficiently dissipate into the networks and search for solutions in parallel. In the case of successive primes, our approach exhibits a dominant superiority in time consumption even compared with supercomputers. Our results confirm the ability of light to realize computations intractable for conventional computers, and suggest the SSP as a good benchmarking platform for the race between photonic and conventional computers on the way toward "photonic supremacy."

arXiv:2002.05108•Science Advances•Jan 31, 2020•66 citations

A fully-programmable integrated photonic processor for both domain-specific and general-purpose computing

Feng-Kai Han, Xiaoyun Xu, Tianyu Zhang +10 more

A variety of complicated computational scenarios have made unprecedented demands on the computing power and energy efficiency of electronic computing systems, including solving intractable nondeterministic polynomial-time (NP)-complete problems and dealing with large-scale artificial intelligence models. Optical computing emerges as a promising paradigm to meet these challenges, whereas current optical computing architectures have limited versatility. Their applications are usually either constrained to a specialized domain or restricted to general-purpose matrix computation. Here, we implement a fully-programmable integrated photonic processor that can be configured to tackle both specific computational problems and general-purpose matrix computation. We achieve complete end-to-end control of the photonic processor by utilizing a self-developed integrated programmable optoelectronic computing platform. For domain-specific computing, our photonic processor can efficiently solve two kinds of NP-complete problems: subset sum problem (far more than 2^N different instances) and exact cover problem. For general-purpose computation, we experimentally demonstrate high-precision optical dot product and further realize accurate image edge detection and MNIST handwritten image classification task with an accuracy of 97%. Our work enhances the versatility and capability of optical computing architecture, paving the way for its practical application in future high-performance and complex computing scenarios.

arXiv:2508.13551•Aug 19, 2025•0 citations

Ising accelerator with a reconfigurable interferometric photonic processor

Rausell-Campo, José Roberto, Kayed, Nayem Al, Pérez-Lppez, Daniel +3 more

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.

arXiv:2511.13284•Nov 17, 2025•0 citations

Scalable and programmable three-dimensional photonic processor

X. Gary Tan, Hang Song, Ye Ji +7 more

Three-dimensional photonic chips are superior in handling $N\phantom{\rule{0}{0ex}}P$-complete problems, but their large-scale application is hindered by the difficulty of programming them. The authors experimentally demonstrate a programmable three-dimensional photonic processor capable of solving the maximum clique problem by encoding injection conditions of photons. The prototype shows the potential of photonic computing, and is applied to solve molecular docking problems. The combination of non-von Neumann parallel computing architectures with fully programmable capabilities paves the way for wider practical applications and photonic computational advantages.

Physical Review Applied•Oct 16, 2023•11 citations

Photonic Ising machines for combinatorial optimization problems

Yuan Gao, Guanyu Chen, Qi Luo +3 more

The demand for efficient solvers of complicated combinatorial optimization problems, especially those classified as NP-complete or NP-hard, has recently led to increased exploration of novel computing architectures. One prominent collective state computing paradigm embodied in the so-called Ising machines has recently attracted considerable research attention due to its ability to optimize complex problems with large numbers of interacting variables. Ising model-inspired solvers, thus named due to mathematical similarities to the well-known model from solid-state physics, represent a promising alternative to traditional von Neumann computer architectures due to their high degree of inherent parallelism. While there are many possible physical realizations of Ising solvers, just as there are many possible implementations of any binary computer, photonic Ising machines (PIMs) use primarily optical components for computation, taking advantage of features like lower power consumption, fast calculation speeds, the leveraging of physical optics to perform the calculations themselves, possessing decent scalability and noise tolerance. Photonic computing in the form of PIMs may offer certain computational advantages that are not easily achieved with non-photonic approaches and is nonetheless an altogether fascinating application of photonics to computing. In this review, we provide an overview of Ising machines generally, introducing why they are useful, what types of problems they can tackle, and how different Ising solvers can be compared and benchmarked. We delineate their various operational mechanisms, advantages, and limitations vis-à-vis non-photonic Ising machines. We describe their scalability, interconnectivity, performance, and physical dimensions. As research in PIMs continues to progress, there is a potential that photonic computing could well emerge as a way to handle large and challenging optimization problems across diverse domains. This review serves as a comprehensive resource for researchers and practitioners interested in understanding capabilities and potential of PIMs in addressing such complex optimization problems.

Applied Physics Reviews•Oct 14, 2024•34 citations
NP-complete problems are widely and deeply involved in various real-life scenarios while still intractable to solve efficiently on conventional computers. It is of great practical significance to construct versatile computing architectures that solve NP-complete problems with computational advantage. Here, we present a reconfigurable photonic processor to efficiently solve a benchmark NP-complete problem, the subset sum problem (SSP). We show that in the case of successive primes, the photonic processor has genuinely surpassed commercial electronic processors launched recently by taking advantages of the high propagation speed and vast parallelism of photons and state-of-the-art integrated photonic technology. Moreover, we are able to program the photonic processor to tackle different problem instances relying on the tunable integrated modules, variable split junctions, which can be used to build a fully reconfigurable architecture potentially allowing 2N2^{N}2N configurations at most. Our experiments confirm the potential of the photonic processor as a versatile and efficient computing platform, suggesting a possible practical route to solving computationally hard problems at large scale.
Nondeterministic-polynomial-time (NP)-complete problems are widely involved in various real-life scenarios but are still intractable in being solved efficiently on conventional computers. It is of great practical significance to construct versatile computing architectures that solve NP-complete problems with computational advantage. Here, we present a reconfigurable integrated photonic processor to efficiently solve a benchmark NP-complete problem, the subset sum problem. We show that in the case of successive primes, the photonic processor has genuinely surpassed electronic processors launched recently by taking advantage of the high propagation speed and vast parallelism of photons and state-of-the-art integrated photonic technology. Moreover, we are able to program the photonic processor to tackle different problem instances, relying on the tunable integrated modules, variable split junctions, which can be used to build a fully reconfigurable architecture potentially allowing 2N configurations at most. Our experiments confirm the potential of the photonic processor as a versatile and efficient computing platform, suggesting a possible practical route to solving computationally hard problems at a large scale.
The subset sum problem (SSP) is a typical nondeterministic-polynomial-time (NP)-complete problem that is hard to solve efficiently in time with conventional computers. Photons have the unique features of high propagation speed, strong robustness, and low detectable energy level and therefore can be promising candidates to meet the challenge. Here, we present a scalable chip built-in photonic computer to efficiently solve the SSP. We map the problem into a three-dimensional waveguide network through a femtosecond laser direct writing technique. We show that the photons sufficiently dissipate into the networks and search for solutions in parallel. In the case of successive primes, our approach exhibits a dominant superiority in time consumption even compared with supercomputers. Our results confirm the ability of light to realize computations intractable for conventional computers, and suggest the SSP as a good benchmarking platform for the race between photonic and conventional computers on the way toward "photonic supremacy."
A variety of complicated computational scenarios have made unprecedented demands on the computing power and energy efficiency of electronic computing systems, including solving intractable nondeterministic polynomial-time (NP)-complete problems and dealing with large-scale artificial intelligence models. Optical computing emerges as a promising paradigm to meet these challenges, whereas current optical computing architectures have limited versatility. Their applications are usually either constrained to a specialized domain or restricted to general-purpose matrix computation. Here, we implement a fully-programmable integrated photonic processor that can be configured to tackle both specific computational problems and general-purpose matrix computation. We achieve complete end-to-end control of the photonic processor by utilizing a self-developed integrated programmable optoelectronic computing platform. For domain-specific computing, our photonic processor can efficiently solve two kinds of NP-complete problems: subset sum problem (far more than 2^N different instances) and exact cover problem. For general-purpose computation, we experimentally demonstrate high-precision optical dot product and further realize accurate image edge detection and MNIST handwritten image classification task with an accuracy of 97%. Our work enhances the versatility and capability of optical computing architecture, paving the way for its practical application in future high-performance and complex computing scenarios.
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.
Three-dimensional photonic chips are superior in handling $N\phantom{\rule{0}{0ex}}P$-complete problems, but their large-scale application is hindered by the difficulty of programming them. The authors experimentally demonstrate a programmable three-dimensional photonic processor capable of solving the maximum clique problem by encoding injection conditions of photons. The prototype shows the potential of photonic computing, and is applied to solve molecular docking problems. The combination of non-von Neumann parallel computing architectures with fully programmable capabilities paves the way for wider practical applications and photonic computational advantages.
The demand for efficient solvers of complicated combinatorial optimization problems, especially those classified as NP-complete or NP-hard, has recently led to increased exploration of novel computing architectures. One prominent collective state computing paradigm embodied in the so-called Ising machines has recently attracted considerable research attention due to its ability to optimize complex problems with large numbers of interacting variables. Ising model-inspired solvers, thus named due to mathematical similarities to the well-known model from solid-state physics, represent a promising alternative to traditional von Neumann computer architectures due to their high degree of inherent parallelism. While there are many possible physical realizations of Ising solvers, just as there are many possible implementations of any binary computer, photonic Ising machines (PIMs) use primarily optical components for computation, taking advantage of features like lower power consumption, fast calculation speeds, the leveraging of physical optics to perform the calculations themselves, possessing decent scalability and noise tolerance. Photonic computing in the form of PIMs may offer certain computational advantages that are not easily achieved with non-photonic approaches and is nonetheless an altogether fascinating application of photonics to computing. In this review, we provide an overview of Ising machines generally, introducing why they are useful, what types of problems they can tackle, and how different Ising solvers can be compared and benchmarked. We delineate their various operational mechanisms, advantages, and limitations vis-à-vis non-photonic Ising machines. We describe their scalability, interconnectivity, performance, and physical dimensions. As research in PIMs continues to progress, there is a potential that photonic computing could well emerge as a way to handle large and challenging optimization problems across diverse domains. This review serves as a comprehensive resource for researchers and practitioners interested in understanding capabilities and potential of PIMs in addressing such complex optimization problems.