The traveling salesman problem is easy to describe and hard to solve with certainty. It goes like this: A salesman – or a UPS driver, or the Tooth Fairy – must visit a number of cities and end where she or he began. What’s the most efficient route? With more cities, the problem becomes vastly more complex.
Computer scientists study optimization problems like the traveling salesman not because they want solutions, but because they want to and algorithms that can do such heavy computational lifting. The ideal algorithm identifies the best strategy and proves that no others are better. Ordinary computers balk at the task, but quantum computers might do better.
Benchmark problems are needed to test new algorithms and computer architectures like quantum machines. Quantum annealers – devices that can identify the optimal solution to a problem – increase in power every year, which means testing their efficiencies will get increasingly difficult.
A common approach to difficult optimization problems is a reverse-engineering process called “planting solutions,” in which researchers start with a dataset and devise a problem that describes the data.
“Imagine you measured some experimental result, and you know it could be understood with a mathematical model,” says SFI External Professor Helmut Katzgraber (Texas A&M). “The question is, can you build a model out of the results that show the underlying physics?”
Katzgraber organized a two-day working group in December, The Inverse Ising problem and Planted Solutions, to talk strategies. Invitees included experts in the inverse Ising problem, machine learning algorithms, and quantum annealing.
“These people have worked on related projects from different angles, and my hope is that by combining these angles we and something that successfully advances our understanding,” he says.