Scalable photonic computer solves the subset sum problem

A team of researchers affiliated with several institutions in China created a photonic computer that was able to solve the subset sum problem. In their paper published in the journal Science Advances, the group describes their computer and how well it performed.

In recent years, it has become apparent to computer engineers that the continued ability to increase the efficiency and speed of standard computers is heading toward a ceiling—someday soon, engineers will reach a limit beyond which there is no way to make them faster. Such an outcome is undesirable, because it will limit the kinds of applications that can be developed in the future. In addition to heading off advanced user applications, this roadblock also stands in the way of solving problems such as the subset sum problem—a typical NP-complete problem that bogs down conventional computers. So computer engineers have begun looking at other options, such as quantum or molecular computers. In this new effort, the researchers propose the idea of a photonic computer by creating one that can solve the subset sum problem.

The subset sum problem can be formulated as follows: given the integers or natural numbers w(1)... w(n), does any subset of them sum to precisely W? For instance, a computer is given a list of numbers and is instructed to return a pair of them, if they exist, that add up to a given number. Given the list, 1, 9, 13, 7, 0, for example, and a request to find a pair that adds up to 14, the computer should return 1, 13. This problem is easy for a conventional computer when the list is small—but when it grows large, it becomes unworkable.

To solve the problem using a photonic computer, the researchers mapped it into a 3-D waveguide network etched onto glass using a femtosecond laser. Photons were then allowed to dissipate into the network in search of a solution in parallel. This allowed the researchers to try different combinations at the same time rather than grinding through them all, as is done with a conventional computer. Not only did the approach work, it was able to do so faster than a supercomputer—and it demonstrated that photonic computers are capable of solving such problems and are scalable, as well.