Heuristic Approach Uses Photonics to Solve Complex Problems Fast

Researchers at MIT and the Institute for Soldier Nanotechnologies have opened the path to solving NP-complete problems with integrated photonics, by developing a heuristic algorithm dedicated to solving the NP-complete Ising problem using photonics hardware.

NP-complete problems — that is, nondeterministic polynomial problems — require numerous operations to solve. Optical machines that consist of a set of optical transformations conveyed to an optical signal could provide a way to solve them. Further, optical hardware integrated into silicon photonics could provide optical machines with benefits such as low-loss, parallel processing; optical passivity at low optical powers; and robust scalability. However, compact, fast, photonic hardware with dedicated algorithms that can optimize the capability of optical hardware has been lacking.

The MIT team developed a heuristic Ising machine to provide a candidate solution to the NP-problem. Heuristic algorithms, an alternative to exact algorithms, provide fast, inexpensive solutions to hard problems.

Artistic illustration of solving complex problems with a photonic circuit. The background pattern shows a network of interferometers able to perform arbitrary unitary matrix multiplication. By encoding the problem data into the weights of the optical matrix and letting an optical signal evolve through the optical circuit, one can find the state minimizing the energy of the associated problem (the solution). In the case of the Ising problem, the solution is a given distribution of spins that can take only binary values. Courtesy of Charles Roques-Carmes et al.

The researchers were guided by their knowledge of fundamental photonics. “Optical computing is a very old field of research,” professor Marin Soljacic said. “Therefore, we had to identify which recent advances in photonic hardware could make a difference. In other words, we had to identify the value proposition of modern photonics.”

The researchers identified this value proposition to be: performance of fast and inexpensive fixed matrix multiplication, and performance of noisy computation, which means that the result of the computation would vary slightly from one run to the other. “These two elements are the building blocks of our work,” researcher Charles Roques-Carmes said.

While developing their algorithm and benchmarking it on various problems, the researchers discovered a variety of related algorithms that could also be implemented in photonics to find solutions even faster. The researchers are enthusiastic about the prospect of this work.

“The field of enhancing computing capability with integrated photonics is currently booming, and we believe this work can be part of it,” researcher Yichen Shen said. “Since the algorithm we developed optimally leverages the strengths and weaknesses of photonic hardware, we hope it could find some short-term application.”

There has been much effort toward developing application-specific hardware across many different fields of engineering, such as integrated circuits, memristors, and photonics. However, unleashing the potential of such architectures requires the development of algorithms that optimally exploit their fundamental properties. The Photonic Recurrent Ising Sampler (PRIS) developed by the MIT team is a heuristic method tailored for parallel architectures, allowing fast and efficient sampling from distributions of arbitrary Ising problems.

The researchers at MIT are currently working in collaboration with others to realize proof-of-concept experiments and are benchmarking their algorithm on photonic hardware versus other photonic machines and conventional algorithms running on computers.

The research was published in Nature Communications (https://doi.org/10.1038/s41467-019-14096-z).