7
Small Traveling Salesman Problems
Authors: Richard H. Warren
Number of views: 369
This paper illustrates fundamental principles about small traveling salesman problems
(TSPs) which are a current application for quantum annealing computers. The 2048 qubit, quantum
annealing computer manufactured by D-Wave Systems is estimated to be able to solve all TSPs on 8
cities, which advances a recent 4-city result on a quantum simulator. Additionally, the D-Wave
quantum computer is expected to find all optimal tours for each TSP. To prepare for this, we show
the expected quantum output for 5,000 randomly generated TSPs on 6, 8 and 10 cities. The examples
in the TSPLIB have 14 or more cities. These are too large for the current quantum annealing
processors. We have included an annotated bibliography about solving the TSP on a quantum
computer.