A Scalable Photonic Computer Solving the Subset Sum Problem

Abstract

The subset sum problem is a typical NP-complete problem that is hard to solve efficiently in time due to the intrinsic superpolynomial-scaling property. Increasing the problem size results in a vast amount of time consuming in conventionally available computers. Photons possess the unique features of extremely high propagation speed, weak interaction with environment and low detectable energy level, therefore can be a promising candidate to meet the challenge by constructing an a photonic computer computer. However, most of optical computing schemes, like Fourier transformation, require very high operation precision and are hard to scale up. Here, we present a chip built-in photonic computer to efficiently solve the subset sum problem. We successfully map the problem into a waveguide network in three dimensions by using femtosecond laser direct writing technique. We show that the photons are able to sufficiently dissipate into the networks and search all the possible paths for solutions in parallel. In the case of successive primes the proposed approach exhibits a dominant superiority in time consumption even compared with supercomputers. Our results confirm the ability of light to realize a complicated computational function that is intractable with conventional computers, and suggest the subset sum problem as a good benchmarking platform for the race between photonic and conventional computers on the way towards "photonic supremacy".

13 pages, 6 figures

References in corpus (15)

• Quantum Computing
• Universal Linear Optics
• Boson Sampling on a Photonic Chip
• Experimental Boson Sampling
• Experimental boson sampling in arbitrary integrated photonic circuits
• Photonic Boson Sampling in a Tunable Circuit
• Memcomputing: a computing paradigm to store and process information on the same physical platform
• Experimental Two-dimensional Quantum Walk on a Photonic Chip
• On the experimental verification of quantum complexity in linear optics
• Universal Memcomputing Machines
• Experimental Quantum Fast Hitting on Hexagonal Graphs
• Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states
• Fisher information for far-field linear optical superresolution via homodyne or heterodyne detection in a higher-order local oscillator mode
• Solving the subset-sum problem with a light-based device
• Nonlinear optics of photonic hyper-crystals: optical limiting and hyper-computing

Cited by in corpus (5)

• Large-scale neuromorphic optoelectronic computing with a reconfigurable diffractive processing unit
• Scalable spin-glass optical simulator
• Solving the max-3-cut problem using synchronized dissipative networks
• Programmable 200 GOPS Hopfield-inspired photonic Ising machine
• Physical requirements for scaling up network-based biocomputation