Solving “unsolvable” math challenges with quantum-inspired computers

SRI researchers hope to compete with quantum computing by applying new algorithms to map large problems onto faster, more energy-efficient photonic circuitry.

Some problems are so complex that even the world’s fastest supercomputers take far too long to be cost-effective or practical. Many problems share this property of computational complexity. The famous traveling salesperson problem—a simple mathematical construct to calculate the most efficient route through multiple cities—is the best-known example and has far-reaching applications to many real-world problems.

Such problems are known among mathematicians as “non-deterministic polynomial-time hard problems”—or NP-hard problems, for short. Often, approximations are used to get close. However, certain situations encountered by the Department of Defense or others requiring significant financial investments demand real-time decision-making and high accuracy.

To more efficiently solve NP-hard problems, SRI International’s Computer Science Laboratory (CSL) and its Advanced Technology and Systems Division (ATSD) were awarded a five-year contract under the Quantum-Inspired Classical Computing (QuICC) program with the Defense Advanced Research Projects Agency (DARPA).

David Stoker, PhD, and Adam Cobb, PhD, bring laser-physics and computer science expertise to lead SRI’s research under QuICC. Together, they aim to demonstrate a new approach to solving NP-hard problems by mapping quantum algorithms onto energy-efficient analog photonic hardware. Such hybrid approaches are known as “quantum-inspired” (QI) computing.

QI computing, the researchers say, could lead to more scalable hardware accelerators than its purely quantum counterpart. Compared to quantum computers, QI technologies can be built and scaled with existing industrial components and processes. Currently, quantum computers don’t meet the DoD’s exacting size, weight, and power specifications. “So, we’re trying to solve similar problems at, hopefully, a faster rate and lower cost,” said Cobb.

“So-called ‘quantum supremacy’ becomes much more difficult to achieve when considering metrics like total energy required for a solution,” Stoker said. “We’ve assembled a solid team with experience in photonics fabrication and neuromorphic computing to develop scalable solvers of complex, real-world problems important to the Department of Defense.”

“We will develop bespoke machine learning approaches to tackle NP-hard problems that will be efficiently designed to be specific to our new hardware,” Cobb said. “The objective is to take problems that quantum computers are being designed to solve and develop new theory to make these solutions faster and more efficient when run on classical hardware.”

To reach these challenging goals, SRI will collaborate with Stefan Preble at Rochester Institute of Technology (RIT) and Christopher Baiocco at the Research Foundation for the State University of New York (RF-SUNY). Together the team will leverage state-of-the-art integrated photonics fabrication, packaging, and testing facilities at the AIM photonics foundry.

“With quantum-inspired computing, we believe we can solve existing complex optimization problems that are supremely relevant to the Department of Defense’s work and scale the solver hardware to meet future needs,” Stoker said. “But there could be broad implications for a range of optimization challenges for all of human society—traffic, energy and water resourcing, health care, and much more—down the road.”

This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) through Air Force Research Laboratory (AFRL) Contract No. FA8750-23-C-1001. The views, opinions, and/or findings expressed are those of the authors and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.

Read more from SRI