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

Abstract

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. We focus on the evaluations of three distinctive QAOA mixer designs, considering their performances in terms of numerical accuracy and optimization cost. Notably, we find a well-balanced QAOA mixer design exhibits more promising potential for gate-based simulators and realistic quantum devices in the long run, an observation further supported by our noise model simulations. Furthermore, we investigate the sensitivity of the simulations to the TSP graph. Overall, our simulation results show the digital quantum simulation of problem-inspired ansatz is a successful candidate for finding optimal TSP solutions.

arXiv comment18 pages, 6 figures, 3 tables

References in corpus (28)

• Quantum Computing in the NISQ era and beyond
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Adiabatic Quantum Computing
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Computing for Finance: State of the Art and Future Prospects
• Layerwise learning for quantum neural networks
• Quantum annealing of the Traveling Salesman Problem
• $XY$-mixers: analytical and numerical results for QAOA
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Exact Ising model simulation on a quantum computer
• Efficient quantum algorithms for $GHZ$ and $W$ states, and implementation on the IBM quantum computer
• An Adaptive Optimizer for Measurement-Frugal Variational Algorithms
• Digitized-counterdiabatic quantum approximate optimization algorithm
• Counterdiabaticity and the quantum approximate optimization algorithm
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Implementation of the XY interaction family with calibration of a single pulse
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• QuASeR -- Quantum Accelerated De Novo DNA Sequence Reconstruction
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Approaching the theoretical limit in quantum gate decomposition
• Solving hadron structures using the basis light-front quantization approach on quantum computers
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints

Cited by in corpus (6)

• Applying quantum approximate optimization to the heterogeneous vehicle routing problem
• Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling
• Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
• QTIS: A QAOA-Based Quantum Time Interval Scheduler
• A Quantitative Framework for Comparing Classical and Quantum Algorithms for the Traveling Salesman Problem
• Quantum circuit evolutionary framework applied on set partitioning problem