Quantum Algorithm for the Traveling Salesperson Problem
- Resource Type
- Conference
- Authors
- Haverly, Andrew; Novotny, Mark A.; Rahimi, Shahram
- Source
- 2023 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE) Computer Science and Data Engineering (CSDE), 2023 IEEE Asia-Pacific Conference on. :1-6 Dec, 2023
- Subject
- Communication, Networking and Broadcast Technologies
Computing and Processing
Power, Energy and Industry Applications
Robotics and Control Systems
Transportation
Computers
Computer science
Quantum algorithm
Costs
Urban areas
Qubit
Traveling salesman problems
traveling salesperson
minimum spanning tree
quantum computing
- Language
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.