Quantum Computing and the Traveling Salesperson Problem: a tale of mystery and imagination (but mostly imagination)

I see posts about the Traveling Salesperson Problem (TSP) and Quantum Computing almost weekly. TSP is one of the most deeply studied problems in computational mathematics. It's so popular that there are even scientific papers studying how monkeys approach the problem [1].

Some urban legends say that quantum computers solve TSP instantaneously. Some mythological stories say that quantum computers solve TSP efficiently and, in doing so, exponentially faster than classical computers. This is far from being true and I’m happy to bet a plate of pici all’aglione [2] that this will never be the case.

Here is an informal statement of TSP: (Given) A list of cities and the distances between each pair of cities; (Task) Find the shortest possible route that visits each city exactly once and returns to the origin city.

For n cities, the exhaustive search algorithm requires at most n! steps – and I will omit polynomial factors here and below (and make of this what you will). In the notation, “n!” means “1 times 2 times 3, up to n-1 times n”. It follows that vanilla (i.e., standard) quantum algorithms based on good old Grover’s search would solve the problem in at most square root of n! steps, which is very nice. Surely 10 gives you a better feeling than 100, but this doesn't mean instantaneous or efficient.

Moreover, we know that the classical Bellman-Held-Karp algorithm goes like 2 to the power of n, which is then faster than Grover. This means that we need something else in the quantum setting if we want to do better than classical computers.

So, combining dynamic programming and Grover’s search, Ambainis et al. [3], in 2019,

designed a quantum algorithm for TSP that takes at most 1.728 to the power of n steps,

which is an improvement over Bellman-Held-Karp.

For low-degree graphs, or graphs with constraints on the edges, there are ad hoc quantum algorithmic solutions – see, Moylett et al. [4] for a quadratic speedup on the best classical counterparts. Noticeably, approximation algorithms for TSP are a different story and form a universe by themselves.

But what about quantum annealing? As far as I know, it’s still hard to tell whether quantum annealing can bring any provable advantage to TSP. It’s hard to figure this out beyond empirical observations. And this is the curse of all meta-heuristics, sadly.

Nothing superexciting or particularly rigorous happened following the 2004 paper of Martoňák, Santoro, and Tosatti [5]. But its authors conclude with this alluring idea:

“We believe that gaining further experience with the effects of artificially introduced quantum fluctuations in classical complex problems represents a very promising and challenging route”.

[1] Cramer, A., Gallistel, C. Vervet monkeys as travelling salesmen. Nature 387, 464 (1997). https://www.nature.com/articles/387464a0

[2] Pici all'aglione – Tuscan hand-rolled pasta with tomato and garlic sauce. https://www.greatitalianchefs.com/recipes/pici-all-aglione-recipe

[3] Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Kri?jānis Prūsis, Jevgēnijs Vihrovs. Quantum speedups for exponential-time dynamic programming algorithms. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, page 1783–1793, USA, 2019. Society for Industrial and Applied Mathematics. https://arxiv.org/abs/1807.05209v1

[4] Alexandra E. Moylett, Noah Linden, and Ashley Montanaro, Phys. Rev. A 95, 032323, 22 March 2017. https://arxiv.org/abs/1612.06203v1

[5] Roman Martoňák, Giuseppe E. Santoro, and Erio Tosatti, Phys. Rev. E 70, 057701, 10 Nov 2004. https://arxiv.org/abs/cond-mat/0402330