Though integrated circuit technology has experienced rapid development and greatly enhanced our computing power in the past few decades,1 myriad computational problems are still hard to solve efficiently.2^–4 The difficulty mostly lies in the huge consumption of resources, especially time resources that are irreversible and nonrecyclable.5 According to computational complexity theory,3^,5 problems in the class nondeterministic-polynomial-time (NP)-complete are out of the reach of traditional electronic computers, which are generally regarded as physical embodiments of the deterministic Turing machine.6^,7 The solution space of NP-complete problems grows super-polynomially with the problem size, which leads to massive computing time even for a medium-sized problem and therefore greatly restricts the size of the problem that can be dealt with. In contrast to the situation of lacking a practical and efficient computing regime, NP-complete problems are closely related to a wide range of realistic scenarios,8^–13 including transportation, industrial manufacturing, finance, biomedicine, and so on, which implies that an acceleration of solving NP-complete problems could lead to a more productive society and might even bring a revolution in future development.

Over these years, extensive efforts have been dedicated to the exploration of novel computing architectures for NP-complete problems. The emergent approaches that exploit different operational principles or different information carriers have provided more ways to cope with problems including quantum computation,14^,15 memcomputing,16^–18 biological computation,19^–21 and optical computing.22^–27 In general, high computing efficiency, high accuracy, and programmability are necessary ingredients for a computing architecture to move toward practical application. However, architectures meeting all the criteria still remain elusive. Our proof-of-principle experiment has demonstrated that integrated photonic technology can play a role in constructing a monolithic photonic processor solving NP-complete problems, which shows great potential in computing efficiency and accuracy by taking advantages of the intrinsic properties of photons.28 Meanwhile, substantial progress has been made in programmable integrated photonics.29^,30 These facts suggest the possibility of implementing a chip-scale NP-complete problem photonic processor fulfilling the practical requirements.

Here, we present a reconfigurable integrated photonic processor for a representative NP-complete problem, the subset sum problem (SSP), whose intractability can be utilized to construct attack-resistant cryptosystems.31^,32 The photonic processor is fabricated by femtosecond laser-writing techniques.33 It is composed of on-chip phase shifters (PSs) and an embedded three-dimensional (3D) waveguide network made of 1449 standardized modules. We map the SSP to the waveguide network, and the incident photons travel in the network to perform parallel computation. The optional entry and the tunable module of the waveguide network provide multiple degrees of freedom for programming the photonic processor, enabling solving different SSP instances. The reconfigurable architecture can also be used to implement other functions, although it is specially designed for solving the SSP. Moreover, we have analyzed the reliability and time-consumption performance of the photonic processor to show the photonic advantages.

Given a set S containing N integers, the SSP asks whether there exists a subset of S whose sum equals target T. As presented in Fig. 1(a), we use an integrated photonic processor to solve the SSP, which consists of PSs deposited on the surface and a buried 3D waveguide network encoding the SSP instance where S={2,3,5,7,11,13,17}. Once the coherent light enters the waveguide network, the photonic processor is activated to start a computation. Photons contained in the light beam propagate under the regulation of the waveguide network, exploring all the possible paths toward the output ports in a parallel manner. The arrival or absence of photons at the output is read out by a charge-coupled device in single-shot measurement, giving a YES or NO answer to the SSP, respectively.

In terms of solving the SSP with light, Oltean and Muntean provided a theoretical proposal based on delayed signals and optical fiber (see Sec. S11 in the Supplementary Material for more details).25 They also proposed achieving reconfigurability with programmable delay lines.26 Here, we encode the subset sums into the spatial (not temporal) information of light, providing a straightforward way to distinguish different output signals. Despite the differences and similarities, both approaches show the ability of light to realize complicated computation. Furthermore, we implement a large-scale integrated reconfigurable photonic processor and experimentally verify its excellent performance.

The architecture of the photonic processor can be represented by an abstract network made of lines and nodes, as shown in Fig. 1(b). The lines denote optical paths. The five kinds of nodes represent entry of the network and the four types of functional modules [fixed split junctions, variable split (VS) junctions, pass junctions, and converge junctions]. Photons are launched into the network through one of the pink diamond nodes (network entries). At black hexagonal nodes [fixed split junctions; see Fig. 1(c) for physical structure], photons are equally divided into two portions, which then proceed in vertical (i.e., x) and diagonal directions, respectively. In the case of yellow hexagonal nodes [VS junctions;see Fig. 1(d) for physical structure], photons can be split with any specified ratio η:1−η(0≤η≤1) by properly setting the PSs (see Sec. S1 in the Supplementary Material). Similarly, the split light propagates vertically and diagonally. Blue circular nodes [pass junctions; see Fig. 1(e) for physical structure] enable photons to move forward along original direction, which is realized by 3D crossing structures. This special design is supported by the 3D fabrication capability of femtosecond laser writing,34 whereas it is difficult for traditional planar lithography. At the end of the network, brown square nodes [converge junctions; see Fig. 1(f) for physical structure] gather together photons from different paths.

The network encodes the SSP according to the following rules. First, a hexagonal-node block (whose color is either black or yellow) and a circular-node block alternately appear for N times (here N=7). Second, the vertical distance between two adjacent rows of hexagonal nodes is equal to the element in the set S, as denoted by the integers on the left. The distance is measured as the number of nodes. Third, the diagonal movement of photons means including an element into the summation, while the vertical movement means the opposite. Last, the position of the output signals represents the ultimate sums, which are denoted by the output port number. For example, the path highlighted in pink indicates that elements 3, 5, 11, and 13 are included into the summation, whose value is 32.

The foundation of reconfiguring the photonic processor is the optional network entry and the tunable functional module, VS junction. In a general case, a photonic processor is initially designed for an SSP instance where S={X1,X2,…,XN}. As shown in Fig. 1(g), there are different paths to programming the photonic processor. First, by switching to a different entry, such as entry i, we can program the photonic processor to solve the SSP instance where S={Xi,Xi+1,…,XN}. The reason is that the local network encoding the first i−1 elements is bypassed, preventing these elements from participating in the computation.

Second, we can choose to delete or keep the element Xj by properly setting the working modes of the jth row of VS junctions, which can be understood through the following deduction. As introduced above, the splitting ratio η:1−η of VS junctions is tunable. Therefore, we can set the jth row of VS junctions to total transmission mode (η=0) or total reflection mode (η=1), depending on their specific location, to completely transfer the arriving photons to vertical paths. On this occasion, there is a zero probability of including the element Xj into any summation. Namely, Xj is removed out of the computation. On the contrary, Xj is retained when the VS junctions work in balance mode (η=0.5). In summary, VS junctions can be used to decide whether to remove an element, therefore allowing to program the photonic processor.

The two approaches can be also applied simultaneously. Note that they play different roles in the reconfiguration. The first approach provides a flexible and energy-saving option. In some cases, part of VS junctions can be bypassed directly, avoiding the energy consumption of maintaining a particular working mode, whereas, the second approach enables to realize more combinations of the elements. For a fully reconfigurable photonic processor (i.e., every split junction is variable), it allows, in principle, 2N different configurations at most, which correspond to all the possible subsets of S, implying the potential versatility of the proposed computing architecture.

The realization of a desired photonic processor requires high-quality fabrication of the 3D waveguide network, PSs enabling 2π phase shift and accurate alignment between the waveguide network and the PSs. Prior to the construction of the waveguide network, we have elaborately designed and optimized the functional modules (see Secs. S2 and S3 in the Supplementary Material). We used a femtosecond laser with a pulse duration of 290 fs, a repetition rate of 1 MHz, and a central wavelength of 513 nm to fabricate the photonic processor. The laser was locked by a beam-pointing stabilizer (the pointing angle is fixed at lower than 0.5μrad), shaped by a cylindrical lens and then focused into the glass substrate (Corning Eagle XG) by a 50× objective. The glass substrate was placed on an air-bearing 3D translation stage whose position deviation is ±0.05μm.

With the translation stage moving at a speed of 10 mm/s, the laser (185 nJ pulse energy) radiated into the substrate to write the waveguide network at a depth of 55 to 155μm. The shallow embedment of the waveguide network is beneficial to decrease the power consumption of the PSs. Specially, the overlap segment of the two waveguides in converge junctions was inscribed with a laser pulse energy of 250 nJ, leading to a multimode output port. Meanwhile, three triangular marks were written on the glass surface as position reference for the subsequent alignment. The stable and high-precision fabrication system, along with the inherent strengths of monolithic integration, lays a crucial foundation for the excellent phase stability and interference visibility of the waveguide network (see Sec. S12 in the Supplementary Material).

PSs were formed by ablating the thin metal films deposited on the substrate surface,35 which was conducted with the same fabrication system. A pulse energy of 245 nJ and a speed of 5 mm/s were utilized. The thin films consist of 2 nm chromium and 100 nm gold, which were successively deposited via electron-beam evaporating after the waveguide fabrication. We used the chromium film to enhance the adhesion of the PSs, given the fragile bonding between the golden film and the glass. The PSs comprise two pads for connecting external power supply and a resistor for heating waveguides. We adopted wide pads (∼3mm×2.3mm) and narrow resistors (∼0.03mm×5mm) to ensure a good heating efficiency. The PSs were carefully aligned with the target waveguides based on their coordinates relative to the reference marks. Though high-density integration of PSs on femtosecond-laser-written silica photonic chip is challenging, the recent advancements in fabricating isolation trenches and near-surface waveguides offer possible ways to cope with it (see Sec. S13 in the Supplementary Material).36^,37

We experimentally investigate the reconfigurability and reliability of the implemented photonic processor, in which the second row of split junctions is variable as shown in Fig. 1(b) (see Sec. S4 in the Supplementary Material for the experimental setup). To correctly set the working modes of the VS junctions, we first characterize their optical response to the dissipated power of the PSs (see Sec. S5 in the Supplementary Material). The response curves are well consistent with theory, allowing us to easily identify the three working modes (see Fig. S5 in the Supplementary Material).

We achieve programming of the photonic processor to solve the SSP instance where S={2,3,5,7,11,13,17} by choosing entry 1 and setting all the VS junctions to balance mode. With the 808 nm laser injected into the photonic processor, the computation is started. The evolution results of the incident light appear as a line of spots, as displayed in Fig. 2(a). The appearance of the spots represents that there exist subsets of S whose sums are equal to the corresponding output port numbers, as denoted by the numbers below the spots. Compared with the results attained by enumeration, all the spots observed in our experiments are valid certifications; meanwhile, they cover all the possible subset sums, suggesting the excellent accuracy of the photonic computing.

The experimental evolution results are further investigated by an analysis of intensity distribution, as shown in Fig. 2(b). For comparison, the theoretical intensity distribution is obtained based on an ideal photonic computing model and can be used as a benchmark result (see Sec. S6 in the Supplementary Material). In the theoretical regime, any signal of nonzero intensity denotes the existence of the corresponding subset sum, whereas, this is not the case in the experiment, due to inevitable environmental noise and fabrication imperfection. Nevertheless, we can correctly classify the experimental signals into valid and invalid certifications by applying a reasonable intensity threshold. If the signal has an intensity beyond the threshold, it is identified as valid. Otherwise, it is invalid (highlighted by the white solidus pattern). As indicated by the band filled with the black solidus, the tolerance interval for the threshold is relatively large (with an upper bound of 0.00143 and a lower bound of 0.00027), further confirming the reliability of our photonic processor.

We are also able to program the photonic processor for a different SSP instance where S={2,5,7,11,13,17} by tuning the working modes of the VS junctions (see Sec. S7 in the Supplementary Material). Entry 1 still serves as the input. Similar to the previous case, the computation outcomes are of high accuracy, as demonstrated by the experimental evolution results in Fig. 2(c) and the intensity distribution in Fig. 2(d). In addition, the photonic processor is capable of dealing with more SSP instances by using other network entries for photon injection (see Sec. S7 in the Supplementary Material). Figures 3(a), 3(c), and 3(d) present the experimental evolution results when the light is injected through entry 2, entry 3, and entry 4, respectively. More results can be found in Sec. S8 in the Supplementary Material. It should be noted that, in all the cases, the experimental evolution results are in accordance with theory. Furthermore, the tolerance intervals of the thresholds applicable in our experiments are considerably large, as exhibited in Fig. 3(b) and Figs. S6 and S7 in the Supplementary Material, owing to the good experimental signal-to-noise ratio. The above facts indicate the achievement of solving multiple SSP instances on the single photonic processor with high accuracy, verifying the reconfigurability and strong reliability of the photonic computing architecture.

Computing time is one of the most critical performances of a computing architecture. We investigate the time consumption of our photonic processor by comparing it with representative electronic processors. We define the computing time of the photonic processor as the propagation time of photons in the longest path of the waveguide network. It is obtained by dividing the length of the longest path by the propagation speed of light in the waveguide based on the actual geometric parameters of the waveguide network and the estimated refractive index of laser-written glass.28^,38 Owing to the parallel working manner, the photonic processor is able to give all the possible subset sums at a time, which, to some extent, is equivalent to simultaneously solving a series of SSP instances whose target T is different. For a fair comparison, electronic processors are considered to search the entire solution space to solve the SSP, accompanied with the acquirement of all the subset sums. The computing time of electronic processors is estimated by dividing the total number of arithmetic operations by the floating point operations per second,39 without taking into account performance degradation.40

Figure 4(a) displays the estimated computing time in the case of successive primes, a nontrivial set where the elements are neither generated with a single definite formula nor explicitly related. We find that, when 2≤N≤4, the photonic processor is comparable to the Intel Pentium III released in 2001,41 whereas it lags behind Intel Core i7-11370H and i7-1160G7,42 the electronic processors launched in recent years. However, when N>5, the photonic processor tends to outperform its electronic counterparts. We magnify the curves encircled by dashed lines in Fig. 4(a) and see that in our experimental demonstration (N=7,S={2,3,5,7,11,13,17}), the photonic processor has shown an obvious advantage over all the electronic rivals, as shown in Fig. 4(b). Specifically, the photonic processor is several orders of magnitude faster than the Intel Pentium III and several times faster than the other two rivals. Moreover, the photonic superiority is reinforced with the growth of problem size, showing considerable competitiveness. It should be noted that the time-consumption advantage of the photonic processor is achieved with classical light, which implies another possible way toward computational advantage in addition to quantum speed-up. In fact, an injection of quantum light into our photonic processor cannot bring computational acceleration despite the demonstrated quantum advantage,43^–45 the reason being that the latency arising from photon emission (i.e., quantum light emits only a few photons at a time) hinders the parallel computation of the photonic processor.

As for space consumption, the width of our photonic processor can be written as W′=c1×q, where c1=0.04mm is the pitch of the output channels and q is the sum of all the elements in the set. In addition, the length of our photonic processor can be expressed by L′=c2×N+c3×q+c4, where c2=7.3811mm, c3=0.8238mm, and c4=29.3285mm. It should be noted that the length can be greatly reduced by increasing the intersection angles of the waveguides in the pass junctions (see Sec. S15 in the Supplementary Material for details). Figure 4(c) presents the estimated physical size of the optimized photonic processor. For a silica glass chip with a length of 250 mm and a width of 110 mm, whose size is smaller than half of a standard A4 paper (297mm×210mm), the size of the set that could be mapped to the chip is up to N=30, and the maximal element in the set is 113 (see Sec. S15 in the Supplementary Material for details about the mapping).

In summary, we construct a reconfigurable and large-scale photonic processor containing 1449 integrated 3D components by femtosecond laser-writing techniques. The photonic processor allows solving the SSP, a typical NP-complete problem, and possesses good performance in reconfigurability, reliability, and time consumption. Photons with strong robustness act as information carriers. Given the low detectable energy level of photons,46^,47 a coherent light beam could contain enormous amounts of independent information carriers. With the injection of the coherent light, a bunch of photons travels in the photonic processor to search for the solution in parallel.

We successfully program the photonic processor to solve different SSP instances by tunning the working modes of the tunable modules or/and changing the entry. It is worth stressing that, in all the cases, the experimental results are of high accuracy, strongly confirming the reliability of the photonic processor. Furthermore, the photonic processor has been capable of exceeding the recently launched commercial electronic processors in the context of successive primes, suggesting promising computing potential. The photonic speed-up is attributed to the parallel search of photons, the inherently high propagation speed of light, and the confining of light to a limited space via advanced integrated photonic technology. A further comparison between the photonic processor and dynamic programming algorithm is shown in Sec. S16 in the Supplementary Material. Meanwhile, the thermal cross talk in our experiments is negligible (see Sec. S9 in the Supplementary Material). The signal-to-noise ratio (see Sec. S10 in the Supplementary Material) of the photonic processor is also discussed.

The reconfigurable photonic computing architecture for the SSP, to the best of our knowledge, is proposed and experimentally demonstrated for the first time. Our experimental investigation verifies the feasibility of the proposal, and the presented core idea can be applied to implementing a fully reconfigurable architecture that in principle allows 2N configurations at most. The introduction of reconfigurability lays a solid foundation for building a versatile photonic computing platform, which might play a key role in future supercomputing.48 First, a large number of different SSP instances can be encoded into a single photonic processor. Second, many SSP-based real-life problems and algorithms,49^,50 which usually require programmable hardware, are possible to be tackled in the framework of the photonic computing architecture possessing a potential of accelerating computation. Third, given the fact that any NP-complete problems can be efficiently reduced to a certain NP-complete problem,3^,51 this photonic processor built for SSP provides a potential platform to deal with a variety of NP-complete problems.52^,53 Last but not least, our reconfigurable architecture is not limited to solving NP-complete problems, though it is not a universal linear photonic circuit. In fact, there are many tasks that do not require universal linear optics, such as verifying NP-complete problems and dot-product operation.54^–56 It is worth highlighting that the specific architecture adopted in our investigation could be used in a broader range of applications, including implementing optical convolutional neural networks and photonic quantum memristors (see Sec. S14 in the Supplementary Material).56^,57

Xiao-Yun Xu is an assistant professor at Shanghai Jiao Tong University. She received her PhD in physics from Shanghai Jiao Tong University in 2020, and received her bachelor’s degree in science from Donghua University in 2015. She was awarded “Shanghai Postdoctoral Excellence Program” and “Forbes China 30 under 30 (U30) in Science” in 2021. Her research interests include integrated photonics, optical computing, and quantum simulation.

Tian-Yu Zhang is currently a PhD student in the Applied Physics Department at Eindhoven University of Technology. She received her master’s degree in science from Shanghai Jiao Tong University in 2023. Her research area includes integrated photonics and hybrid photonic-spintronic devices.

Zi-Wei Wang is currently a PhD student in the School of Physics and Astronomy at Shanghai Jiao Tong University. He received his bachelor’s degree from Tianjin University in 2021. His research area includes optical computing and nano optics.

Chu-Han Wang is a PhD candidate at Shanghai Jiao Tong University, under the supervision of Prof. Xian-Min Jin. His research primarily focuses on integrated photonics, femtosecond laser micromachining and light–matter interaction.

Xian-Min Jin is a Changjiang distinguished professor at Shanghai Jiao Tong University, director of the Institute of Optical Science and Technology, director of the Center for Integrated Quantum Information Technologies (IQIT), head of Chip Hub for Integrated Photonics Xplore (CHIPX), and the founder of TuringQ Co. Ltd. He received his PhD in science from University of Science and Technology of China in 2008. His research area includes photonic chips and quantum information.