Modern computers still lack the capability to find the best solution for the classic “traveling salesman” problem. Even finding approximate solutions is challenging. But finding the shortest traveling salesman route among many different cities is more than just an academic exercise. This class of problems lies at the heart of many real-world business challenges such as scheduling delivery truck routes or discovering new pharmaceutical drugs.
Today’s computers handle combinatorial optimization problems by skipping some of the weaker solutions instead of considering all possibilities to find the very best solution. But U.S. and Japanese researchers have unveiled a new specialized computer that could someday solve the traveling salesman scenario and similar problems more efficiently. Their hybrid machine combines digital electronic circuits with optical devices similar to lasers.
“The simplest way to solve the traveling salesman problem is to consider all possible paths, but that is not the way that a conventional computer solves it,” says Peter McMahon, a physicist at the Quantum Information Science group of Stanford University. “If you try to solve that problem on your laptop, it’s not going to naively evaluate all paths because it’s not possible for larger problem sizes.”
McMahon is part of a research group based out of Stanford University and various Japanese research institutions. The group, led by Yoshihisa Yamamoto at the National Institute of Informatics in Tokyo, Japan, published two separate but complementary papers showing the possibilities of their new computer in the 21 October 2016 online release of the journal Science.
To read more, click here.