Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms

Abstract

Routing problems are a common optimization problem in industrial applications, which occur on a large scale in supply chain planning. Due to classical limitations for solving NP-hard problems, quantum computing hopes to improve upon speed or solution quality. Several suggestions have been made for encodings of routing problems to solve them with variational quantum algorithms. However, for an end user it is hard to decide a priori which encoding will give the best solutions according to their needs. In this work, we investigate different encodings for the Travelling Salesperson Problem. We compare their scaling and performance when using the Quantum Approximate Optimization Algorithm and the Variational Quantum Eigensolver and provide a clear guide for users when to choose which encoding. For small instances, we find evidence that the permutation encoding can yield good results since it does not suffer from feasibility issues.

Accepted at IEEE QSW 2024

References in corpus (7)

• Variational Quantum Algorithms
• A Quantum Approximate Optimization Algorithm
• Warm-starting quantum optimization
• Qubit-efficient encoding schemes for binary optimisation problems
• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem
• Trainability Barriers in Low-Depth QAOA Landscapes
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors

Cited by in corpus (2)

• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Optimization via Quantum Preconditioning