Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem

Understand

The Traveling Salesman Problem (TSP) is one of the most often-used NP-Hard problems in computer science to study the effectiveness of computing models and hardware platforms.

• In this regard, it is also heavily used as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems.
• In this paper, we tackle the TSP using the quantum approximate optimization algorithm (QAOA) approach by formulating it as an optimization problem.
• By adopting an improved qubit encoding strategy and a layerwise learning optimization protocol, we present numerical results obtained from the gate-based digital quantum simulator, specifically targeting TSP instances with 3, 4, and 5 cities.