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 |
1.IntroductionThough 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. 2.Reconfigurable Photonic ProcessorGiven a set containing integers, the SSP asks whether there exists a subset of whose sum equals target . 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 . 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. 2.1.Architecture of the Photonic ProcessorThe 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 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 times (here ). Second, the vertical distance between two adjacent rows of hexagonal nodes is equal to the element in the set , 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. 2.2.Programming the Photonic ProcessorThe 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 . 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 , we can program the photonic processor to solve the SSP instance where . The reason is that the local network encoding the first elements is bypassed, preventing these elements from participating in the computation. Second, we can choose to delete or keep the element by properly setting the working modes of the row of VS junctions, which can be understood through the following deduction. As introduced above, the splitting ratio of VS junctions is tunable. Therefore, we can set the row of VS junctions to total transmission mode () or total reflection mode (), 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 into any summation. Namely, is removed out of the computation. On the contrary, is retained when the VS junctions work in balance mode (). 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, different configurations at most, which correspond to all the possible subsets of , implying the potential versatility of the proposed computing architecture. 2.3.FabricationThe realization of a desired photonic processor requires high-quality fabrication of the 3D waveguide network, PSs enabling 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 ), shaped by a cylindrical lens and then focused into the glass substrate (Corning Eagle XG) by a objective. The glass substrate was placed on an air-bearing 3D translation stage whose position deviation is . 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 . 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 () and narrow resistors () 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 3.Results3.1.Reconfigurability and ReliabilityWe 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 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 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 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. 3.2.Time–Space ConsumptionComputing 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 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 , 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 , 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 (), 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 , where is the pitch of the output channels and is the sum of all the elements in the set. In addition, the length of our photonic processor can be expressed by , where , , and . 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 (), the size of the set that could be mapped to the chip is up to , and the maximal element in the set is 113 (see Sec. S15 in the Supplementary Material for details about the mapping). 4.Discussion and ConclusionIn 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 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 Code and Data AvailabilityThe data that support the findings of this study are available from the corresponding author on reasonable request. AcknowledgmentsThis research was supported by the National Key R&D Program of China (Grants Nos. 2019YFA0308703, 2019YFA0706302, and 2017YFA0303700); the National Natural Science Foundation of China (NSFC) (Grant Nos. 62235012, 12104299, 61734005, 11761141014, 11690033, 11904299, and 12304342); the Innovation Program for Quantum Science and Technology (Grant Nos. 2021ZD0301500 and 2021ZD0300700); the Science and Technology Commission of Shanghai Municipality (STCSM) (Grant Nos. 20JC1416300, 2019SHZDZX01, 21ZR1432800, and 22QA1404600); the Shanghai Municipal Education Commission (SMEC) (Grant No. 2017-01-07-00-02-E00049); the China Postdoctoral Science Foundation (Grant Nos. 2022T150415, 2021M692094, and 2020M671091); and the Startup Fund for Young Faculty at SJTU (SFYF at SJTU). X.-M.J. acknowledges additional support from a Shanghai Talent Program and support from the Zhiyuan Innovative Research Center of Shanghai Jiao Tong University. The authors thank Jian-Peng Dou and Feng-Kai Han for helpful discussion. ReferencesL. Venema,
“Silicon electronics and beyond,”
Nature, 479
(7373), 309 https://doi.org/10.1038/479309a
(2011).
Google Scholar
M. M. Waldrop,
“The chips are down for Moore’s law,”
Nature, 530 144
–147 https://doi.org/10.1038/530144a
(2016).
Google Scholar
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman(
(1979). Google Scholar
S.-T. Wei et al.,
“Trends and challenges in the circuit and macro of RRAM-based computing-in-memory systems,”
Chip, 1 100004 https://doi.org/10.1016/j.chip.2022.100004 CHIPDP 0170-6632
(2022).
Google Scholar
M. Sipser, Introduction to the Theory of Computation, Cengage Learning(
(2012). Google Scholar
A. M. Turing,
“On computable numbers, with an application to the Entscheidungs problem,”
Proc. Lond. Math. Soc., 2 230
–265
(1936).
Google Scholar
A. Currin et al.,
“Computing exponentially faster: implementing a non-deterministic universal Turing machine using DNA,”
J. R. Soc. Interface, 14 20160990 https://doi.org/10.1098/rsif.2016.0990 1742-5689
(2017).
Google Scholar
G. Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications, 31
–41 Springer(
(2003). Google Scholar
A. Smith et al.,
“Fault diagnosis and logic debugging using Boolean satisfiability,”
IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 24 1606
–1621 https://doi.org/10.1109/TCAD.2005.852031 ITCSDI 0278-0070
(2005).
Google Scholar
A. Darmann et al.,
“The subset sum game,”
Eur. J. Oper. Res., 233 539
–549 https://doi.org/10.1016/j.ejor.2013.08.047 EJORDT 0377-2217
(2014).
Google Scholar
H. Kellerer, U. Pferschy and D. Pisinger, Knapsack Problems, 449
–482 Springer Berlin(
(2004). Google Scholar
D. Biesner, R. Sifa and C. Bauckhage,
“Solving subset sum problems using binary optimization with applications in auditing and financial data analysis,”
(2022). Google Scholar
M. Eghdami and M. Naghibzadeh,
“SSA: subset sum approach to protein β-sheet structure prediction,”
Comput. Biol. Chem., 94 107552 https://doi.org/10.1016/j.compbiolchem.2021.107552 CBCOCH 1476-9271
(2021).
Google Scholar
E. Farhi et al.,
“A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem,”
Science, 292 472
–475 https://doi.org/10.1126/science.1057726 SCIEAS 0036-8075
(2001).
Google Scholar
W.-L. Chang et al.,
“Quantum speedup in solving the maximal-clique problem,”
Phys. Rev. A, 97 032344 https://doi.org/10.1103/PhysRevA.97.032344
(2018).
Google Scholar
M. Di Ventra and Y. V. Pershin,
“The parallel approach,”
Nat. Phys., 9 200
–202 https://doi.org/10.1038/nphys2566 NPAHAX 1745-2473
(2013).
Google Scholar
F. L. Traversa et al.,
“Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states,”
Sci. Adv., 1 e1500031 https://doi.org/10.1126/sciadv.1500031 STAMCV 1468-6996
(2015).
Google Scholar
X. Yan et al.,
“Reconfigurable stochastic neurons based on tin hetero-memristors for simulated annealing and the Boltzmann machine,”
Nat. Commun., 12 5710 https://doi.org/10.1038/s41467-021-26012-5 NCAOBW 2041-1723
(2021).
Google Scholar
L. M. Adleman,
“Molecular computation of solutions to combinatorial problems,”
Science, 266 1021
–1024 https://doi.org/10.1126/science.7973651 SCIEAS 0036-8075
(1994).
Google Scholar
R. S. Braich et al.,
“Solution of a 20-variable 3-SAT problem on a DNA computer,”
Science, 296 499
–502 https://doi.org/10.1126/science.1069528 SCIEAS 0036-8075
(2002).
Google Scholar
D. V. Nicolau et al.,
“Parallel computation with molecular-motor-propelled agents in nanofabricated networks,”
Proc. Natl. Acad. Sci. U. S. A., 113 2591
–2596 https://doi.org/10.1073/pnas.1510825113
(2016).
Google Scholar
K. Wu et al.,
“An optical fiber network oracle for NP-complete problems,”
Light Sci. Appl., 3 e147 https://doi.org/10.1038/lsa.2014.28
(2014).
Google Scholar
M. R. Vázquez et al.,
“Optical NP problem solver on laser-written waveguide platform,”
Opt. Express, 26 702
–710 https://doi.org/10.1364/OE.26.000702 OPEXFF 1094-4087
(2018).
Google Scholar
P. L. McMahon et al.,
“A fully programmable 100-spin coherent Ising machine with all-to-all connections,”
Science, 354 614
–617 https://doi.org/10.1126/science.aah5178 SCIEAS 0036-8075
(2016).
Google Scholar
M. Oltean and O. Muntean,
“Solving the subset-sum problem with a light-based device,”
Nat. Comput., 8 321
–331 https://doi.org/10.1007/s11047-007-9059-3 NCAOAV 1567-7818
(2009).
Google Scholar
M. Oltean, O. Muntean,
“Solving NP-complete problems with delayed signals: an overview of current research directions,”
Opt. SuperComputing, 115
–127 Springer Berlin Heidelberg(
(2008). Google Scholar
X.-Y. Xu and X.-M. Jin,
“Integrated photonic computing beyond the von Neumann architecture,”
ACS Photonics, 10
(4), 1027
–1036 https://doi.org/10.1021/acsphotonics.2c01543
(2023).
Google Scholar
X.-Y. Xu et al.,
“A scalable photonic computer solving the subset sum problem,”
Sci. Adv., 6 eaay5853 https://doi.org/10.1126/sciadv.aay5853 STAMCV 1468-6996
(2020).
Google Scholar
I. V. Dyakonov et al.,
“Reconfigurable photonics on a glass chip,”
Phys. Rev. Appl., 10 044048 https://doi.org/10.1103/PhysRevApplied.10.044048 PRAHB2 2331-7019
(2018).
Google Scholar
W. Bogaerts et al.,
“Programmable photonic circuits,”
Nature, 586 207
–216 https://doi.org/10.1038/s41586-020-2764-0
(2020).
Google Scholar
T. Okamoto, K. Tanaka and S. Uchiyama,
“Quantum public-key cryptosystems,”
in Proc. Annu. Int. Cryptol. Conf.,
147
–165
(2000). Google Scholar
A. Kate and I. Goldberg,
“Generalizing cryptosystems based on the subset sum problem,”
Int. J. Inf. Secur., 10 189
–199 https://doi.org/10.1007/s10207-011-0129-2
(2011).
Google Scholar
R. Osellame, G. Cerullo and R. Ramponi, Femtosecond Laser Micromachining: Photonic and Microfluidic Devices in Transparent Materials, Springer(
(2012). Google Scholar
X.-Y. Xu et al.,
“Quantum transport in fractal networks,”
Nat. Photonics, 15 703
–710 https://doi.org/10.1038/s41566-021-00845-4 NPAHBY 1749-4885
(2021).
Google Scholar
F. Ceccarelli et al.,
“Thermal phase shifters for femtosecond laser written photonic integrated circuits,”
J. Lightwave Technol., 37 4275
–4281 https://doi.org/10.1109/JLT.2019.2923126 JLTEDG 0733-8724
(2019).
Google Scholar
C. Pentangelo et al.,
“High-fidelity and polarization-insensitive universal photonic processors fabricated by femtosecond laser writing,”
Nanophotonics, 13
(12), 2259
–2270 https://doi.org/10.1515/nanoph-2023-0636
(2024).
Google Scholar
J.-P. Bérubé and R. Vallée,
“Femtosecond laser direct inscription of surface skimming waveguides in bulk glass,”
Opt. Lett., 41
(13), 3074
–3077 https://doi.org/10.1364/OL.41.003074 OPLEDP 0146-9592
(2016).
Google Scholar
Corning Incorporated, “Refractive index of Corning Eagle XG glass,”
https://www.corning.com/worldwide/en/products/display-glass/products/eagle-xg-slim.html
(2019).
Google Scholar
P. Gepner, D. L. Fraser and V. Gamayunov,
“Evaluation of the 3rd generation Intel Core processor focusing on HPC applications,”
in Proc. Int. Conf. Parallel and Distrib. Process. Tech. and Appl.,
1
–6
(2012). Google Scholar
“Intel Pentium processor,”
https://www.intel.com/content/www/us/en/support/articles/000007250/processors.html
(2020).
Google Scholar
“Intel Core processor,”
https://www.intel.com/content/www/us/en/support/articles/000005755/processors.html
(2024).
Google Scholar
H.-S. Zhong et al.,
“Quantum computational advantage using photons,”
Science, 370 1460
–1463 https://doi.org/10.1126/science.abe8770 SCIEAS 0036-8075
(2020).
Google Scholar
J. Gao et al.,
“Quantum advantage with membosonsampling,”
Chip, 1 100007 https://doi.org/10.1016/j.chip.2022.100007 CHIPDP 0170-6632
(2022).
Google Scholar
L. S. Madsen et al.,
“Quantum computational advantage with a programmable photonic processor,”
Nature, 606 75
–81 https://doi.org/10.1038/s41586-022-04725-x
(2022).
Google Scholar
X. Hou et al.,
“Waveguide-coupled superconducting nanowire single-photon detectors based on femtosecond laser direct writing,”
Opt. Express, 29 7746
–7756 https://doi.org/10.1364/OE.419724 OPEXFF 1094-4087
(2021).
Google Scholar
C. Liu, H.-F. Ye and Y.-L. Shi,
“Advances in near-infrared avalanche diode single-photon detectors,”
Chip, 1 100005 https://doi.org/10.1016/j.chip.2022.100005 CHIPDP 0170-6632
(2022).
Google Scholar
H. J. Caulfield and S. Dolev,
“Why future supercomputing requires optics,”
Nat. Photonics, 4
(5), 261 https://doi.org/10.1038/nphoton.2010.94 NPAHBY 1749-4885
(2010).
Google Scholar
S. Schwerdfeger and R. Walter,
“A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines,”
Comput. Oper. Res., 73 84
–91 https://doi.org/10.1016/j.cor.2016.03.008 CMORAP 0305-0548
(2016).
Google Scholar
G. Alonistiotis et al.,
“Approximating subset sum ratio via subset sum computations,”
Acta Inf., 61 101
–113 https://doi.org/10.1007/s00236-023-00451-7
(2024).
Google Scholar
R. M. Karp,
“Reducibility among combinatorial problems,”
Complexity of Computer Computations, 85
–103 Springer(
(1972). Google Scholar
M. Oltean and O. Muntean,
“Exact cover with light,”
New. Gener. Comput., 26 329
–346 https://doi.org/10.1007/s00354-008-0049-5 NGCOE5
(2008).
Google Scholar
M. Oltean, O. Muntean,
“An optical solution for the SAT problem,”
Optical Supercomputing, 53
–62 Springer(
(2010). Google Scholar
F. Centrone et al.,
“Experimental demonstration of quantum advantage for NP verification with limited information,”
Nat. Commun., 12
(1), 850 https://doi.org/10.1038/s41467-021-21119-1 NCAOBW 2041-1723
(2021).
Google Scholar
A. Zhang et al.,
“Quantum verification of NP problems with single photons and linear optics,”
Light: Sci. Appl., 10
(1), 169 https://doi.org/10.1038/s41377-021-00608-4
(2021).
Google Scholar
S. Xu et al.,
“Optical coherent dot-product chip for sophisticated deep learning regression,”
Light: Sci. Appl., 10
(1), 221 https://doi.org/10.1038/s41377-021-00666-8
(2021).
Google Scholar
M. Spagnolo et al.,
“Experimental photonic quantum memristor,”
Nat. Photonics, 16
(4), 318
–323 https://doi.org/10.1038/s41566-022-00973-5 NPAHBY 1749-4885
(2022).
Google Scholar
Excelitas Technologies Corp., “Commercial silicon detectors,”
https://www.excelitas.com/product/spcm-nir
(2024).
Google Scholar
R.-J. Ren et al.,
“128 identical quantum sources integrated on a single silica chip,”
Phys. Rev. Appl., 16
(5), 054026 https://doi.org/10.1103/PhysRevApplied.16.054026 PRAHB2 2331-7019
(2021).
Google Scholar
N. Psaila et al.,
“Passively aligned glass micro-optic bridge for expanded-beam vertical coupling and pluggable silicon photonics,”
J. Light. Technol., 42 5223
–5230 https://doi.org/10.1109/JLT.2024.3386033 JLTEDG 0733-8724
(2024).
Google Scholar
L. Brusberg et al.,
“Glass platform for co-packaged optics,”
IEEE J. Sel. Top. Quantum Electron., 29 6000210 https://doi.org/10.1109/JSTQE.2023.3247245 IJSQEN 1077-260X
(2023).
Google Scholar
D. Pisinger,
“Linear time algorithms for knapsack problems with bounded weights,”
J. Alg., 33
(1), 1
–14 https://doi.org/10.1006/jagm.1999.1034
(1999).
Google Scholar
BiographyXiao-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. |