Isaac Scientific Publishing
Journal of Advances in Applied Mathematics
JAAM > Volume 2, Number 2, April 2017

Small Traveling Salesman Problems

Download PDF  (330.7 KB)PP. 101-107,  Pub. Date:April 12, 2017
DOI: 10.22606/jaam.2017.22003

Author(s)
Richard H. Warren
Affiliation(s)
Retired: Lockheed Martin Corporation, King of Prussia, PA 19406, USA
Abstract
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.
Keywords
Traveling salesman, optimal tour, combinatorial analysis, discrete optimization, quantum annealing
References
Copyright © 2017 Isaac Scientific Publishing Co. All rights reserved.