Quantum Algorithm for the Traveling Salesperson Problem

The traveling salesperson problem (TSP) is “if a traveling salesman wishes to visit exactly once each of a list of
$m$
cities (where the cost of traveling from city
$i$
to city
$j$
is
$c_{ij}$
) and then return to the home city, what is the least costly route the traveling salesman can take [1]?” The TSP is an NP-Complete problem. This paper introduces a solution to the TSP using Grover's quantum algorithm. This paper also introduces a quantum algorithm to the minimum (and maximum) spanning tree problem. The full circuit implementation is presented using the open-source Qiskit environment [2]. This paper provides the number of qubits required, the quantum depth, and the quantum volume of the algorithm for the TSP. This paper also shows how to solve the minimum (and maximum) spanning tree using Grover's algorithm.