Comparative Study of Variations in Quantum Approximate Optimization Algorithms for the Traveling Salesman Problem.

Area of Science:

• Quantum Computing
• Computational Complexity
• Optimization Algorithms

Background:

• The traveling salesman problem (TSP) is a benchmark NP-hard problem frequently used to assess quantum computing paradigms.
• Studying TSP on quantum computers is crucial for understanding the potential of quantum algorithms for complex optimization tasks.

Purpose of the Study:

• To investigate the application of the quantum approximate optimization algorithm (QAOA) for solving the traveling salesman problem (TSP).
• To evaluate different QAOA mixer designs and optimization strategies on gate-based quantum simulators.
• To assess the feasibility of digital quantum simulation for finding optimal TSP solutions.

Main Methods:

• Formulated the traveling salesman problem (TSP) as an optimization problem for quantum computation.
• Employed an improved qubit encoding strategy and a layer-wise learning optimization protocol within the QAOA framework.
• Conducted numerical simulations on a gate-based digital quantum simulator for TSP instances with 3, 4, and 5 cities.

Main Results:

• Evaluated the performance of three distinct QAOA mixer designs based on numerical accuracy and optimization cost.
• Identified that a well-balanced QAOA mixer design demonstrates superior potential for gate-based simulators and future quantum devices.
• Observed that noise model simulations support the effectiveness of the balanced mixer design.

Conclusions:

• Digital quantum simulation using problem-inspired ansatz is a viable approach for solving the traveling salesman problem (TSP).
• The choice of QAOA mixer design significantly impacts simulation performance and accuracy.
• A balanced QAOA mixer design is recommended for practical applications on quantum hardware.