Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2404.05448 · IEEE International Conference on Quantum Software (QSW)

Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms

Manuel Schnaus, Lilly Palackal, Benedikt Poggel, Xiomara Runge, Hans Ehm, Jeanette Miriam Lorenz, Christian B. Mendl

Published Jul 7, 2024• 14 citations
arXivHTMLPDF

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.

DOI
10.1109/qsw62656.2024.00022

Related papers

Comparative Analysis of Quantum Approximate Optimization Algorithms for Solving the Travelling Salesperson Problem

Siddharth Chander

The Quantum Approximate Optimization Algorithm (QAOA) was developed to tackle combinatorial optimization problems, such as the Travelling Salesman Problem (TSP), by approximating solutions through quantum mechanics. QAOA utilizes a unitary transformation to prepare a quantum state that encodes a potential solution, with the parameters of the unitary optimized by a classical optimizer. This study evaluates QAOA's performance on the NP-hard TSP, comparing the standard version of the algorithm from Farhi \cite{qaoa} and an enhancement, Warm-Start QAOA \cite{warmstart}, to a classical solver. The TSP seeks the shortest possible route that visits a set of cities, a problem that is amenable to quantum formulation using platforms like Qiskit. Warm-Start QAOA initializes the algorithm's parameters based on a solution to a relaxed version of the problem, offering potential improvements in optimization efficiency. By comparing these quantum algorithms to a classical solver, we provide a comprehensive assessment of their performance across key metrics, including route quality, execution time, and scalability. Through this analysis, we highlight the relative strengths and weaknesses of QAOA and its warm-start variant for solving the TSP, alongside the classical approach, offering insights into their potential for route optimization and practical applications in realworld settings. We conclude that, while the classical solver significantly outperforms QAOA and warm-start QAOA at smaller-scale problem cases, warm-Start QAOA has the potential to yield advantages at a larger scale when run on NISQ-era noisy hardware.

IEEE International Conference on Quantum Control, Computing and Learning (qCCL)•Jun 25, 2025•1 citation

Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem

Lilly Palackal, Benedikt Poggel, Matthias Wulff +3 more

Many relevant problems in industrial settings result in NP-hard optimization problems, such as the Capacitated Vehicle Routing Problem (CVRP) or its reduced variant, the Travelling Salesperson Problem (TSP). Even with today's most powerful classical algorithms, the CVRP is challenging to solve classically. Quantum computing may offer a way to improve the time to solution, although the question remains open as to whether Noisy Intermediate-Scale Quantum (NISQ) devices can achieve a practical advantage compared to classical heuristics. The most prominent algorithms proposed to solve combinatorial optimization problems in the NISQ era are the Quantum Approximate Optimization Algorithm (QAOA) and the more general Variational Quantum Eigensolver (VQE). However, implementing them in a way that reliably provides high-quality solutions is challenging, even for toy examples. In this work, we discuss decomposition and formulation aspects of the CVRP and propose an application-driven way to measure solution quality. Considering current hardware constraints, we reduce the CVRP to a clustering phase and a set of TSPs. For the TSP, we extensively test both QAOA and VQE and investigate the influence of various hyperparameters, such as the classical optimizer choice and strength of constraint penalization. Results of QAOA are generally of limited quality because the algorithm does not reach the energy threshold for feasible TSP solutions, even when considering various extensions such as recursive and constraint-preserving mixer QAOA. On the other hand, the VQE reaches the energy threshold and shows a better performance. Our work outlines the obstacles to quantum-assisted solutions for real-world optimization problems and proposes perspectives on how to overcome them.

arXiv:2304.09629•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•38 citations

Travelling Salesperson Problem with Quantum Computing

Bhanu Lalith Aakash Medury, Vyoma Harshitha Podapati

Combinatorial optimization problems involve find-ing an optimal solution from a finite set of feasible solutions.Dynamic Programming attempts to solve a combinatorial prob-lem by performing an exhaustive search over the entire domain of the problem.In many such cases, this exhaustive search is not effective or tractable.Travelling salesperson problem is an important combinatorial optimization problem in which the salesperson is given N cities to travel with the condition that he has to travel each city exactly once and return to the origin.Among the finite set of feasible routes, the salesperson has to choose an optimal route with shortest total distance.The route can be optimal either by cost or by distance.The classical algorithm which attempts to find the shortest distance/cost to travel all the cities run in exponential time complexity.For small number of cities, the classical algorithm is effective and feasible but as the number of cities increase, the number of possible routes and the time required to compute them grows exponentially.However, addressing this problem by implementing quantum computing significantly reduces the time required to compute these routes.A quantum algorithm is required to run on a quantum computer to obtain meaningful results as quantum computers use Quantum Bits which differ from the bits used by a classical computer.A.

International Journal of Engineering Research and•Mar 12, 2020•1 citation

A High-Performance Cyclic-Mapping Encoding for Quantum Computing of Traveling Salesperson Problems on NISQ Devices

J. Wang, Takumi Kanezashi, Daisuke Tsukayama +3 more

With the ongoing progress of quantum computing, there is increasing interest in bringing quantum technologies into real-world applications, making practically motivated NP-hard problems particularly important to study. In this work, we solve the traveling salesperson problem (TSP) on real quantum hardware to demonstrate and analyze the performance of different quantum chips, and we benchmark these results against simulations. This comparison provides evidence supporting the feasibility of deploying quantum computation toward practical applications.

IEEE International Conference on Nanotechnology (IEEE-NANO)•Jul 1, 2026•0 citations

Solving larger Travelling Salesman Problem networks with a penalty-free Variational Quantum Algorithm

Daniel Goldsmith, Xing Liang, Dimitrios Makris +1 more

The Travelling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimisation problem with important industrial applications. Although extensively studied, quantum solutions for instances beyond a dozen locations remain uncommon. We present a hybrid penalty-free Variational Quantum Algorithm (VQA) that significantly reduces both the qubit count and the runtime through a compact penalty-free formulation scaling as $\mathcal{O}(nlog_2 n)$ qubits compared to conventional formulations with $\mathcal{O}(n^2)$ scaling. The VQA achieves solution qualities exceeding 90\% on Rigetti quantum hardware for instances of up to 17 locations. To the best of our knowledge, this represents the largest TSP instance solved on gate-based hardware. We systematically evaluate multiple encoding and optimisation strategies, and show that warm-start initialisation improves solution quality, while runtime is reduced by nearly two orders of magnitude through the use of gradient-free optimisation methods and cost-function caching. We additionally introduce a novel VQA inspired classical machine learning model (VQAi-CML) and benchmark the VQA against VQAi-CML, a greedy heuristic, a Monte Carlo baseline, and a strong classical optimisation baseline. Across the networks evaluated, the VQA consistently achieves superior solution quality relative to VQAi-CML, greedy heuristic, and Monte Carlo baselines, but not the classical solver

quant-pharXiv:2512.06523•Dec 9, 2025•0 citations

Efficient Encoding of the Traveling Salesperson Problem on a Quantum Computer

John Stenger, Sean Crowe, Joseph Diaz +3 more

We propose an amplitude encoding of the traveling salesperson problem along with a method for calculating the cost function using a probability distribution obtained on a quantum computer. Our encoding requires a number of qubits that grows logarithmically with the number of cities. We propose to calculate the cost function using a nonlinear function of expectation values of quantum operators. This is in contrast to the typical method of evaluating the cost function by summing expectation values of quantum operators. We demonstrate our method using a variational quantum eigensolver algorithm to find the shortest route for a given graph. We find that there is a broad range in the hyperparameters of the optimization procedure for which the best route is found.

Quantum Reports•Jul 17, 2025•4 citations
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.
The Quantum Approximate Optimization Algorithm (QAOA) was developed to tackle combinatorial optimization problems, such as the Travelling Salesman Problem (TSP), by approximating solutions through quantum mechanics. QAOA utilizes a unitary transformation to prepare a quantum state that encodes a potential solution, with the parameters of the unitary optimized by a classical optimizer. This study evaluates QAOA's performance on the NP-hard TSP, comparing the standard version of the algorithm from Farhi \cite{qaoa} and an enhancement, Warm-Start QAOA \cite{warmstart}, to a classical solver. The TSP seeks the shortest possible route that visits a set of cities, a problem that is amenable to quantum formulation using platforms like Qiskit. Warm-Start QAOA initializes the algorithm's parameters based on a solution to a relaxed version of the problem, offering potential improvements in optimization efficiency. By comparing these quantum algorithms to a classical solver, we provide a comprehensive assessment of their performance across key metrics, including route quality, execution time, and scalability. Through this analysis, we highlight the relative strengths and weaknesses of QAOA and its warm-start variant for solving the TSP, alongside the classical approach, offering insights into their potential for route optimization and practical applications in realworld settings. We conclude that, while the classical solver significantly outperforms QAOA and warm-start QAOA at smaller-scale problem cases, warm-Start QAOA has the potential to yield advantages at a larger scale when run on NISQ-era noisy hardware.
Many relevant problems in industrial settings result in NP-hard optimization problems, such as the Capacitated Vehicle Routing Problem (CVRP) or its reduced variant, the Travelling Salesperson Problem (TSP). Even with today's most powerful classical algorithms, the CVRP is challenging to solve classically. Quantum computing may offer a way to improve the time to solution, although the question remains open as to whether Noisy Intermediate-Scale Quantum (NISQ) devices can achieve a practical advantage compared to classical heuristics. The most prominent algorithms proposed to solve combinatorial optimization problems in the NISQ era are the Quantum Approximate Optimization Algorithm (QAOA) and the more general Variational Quantum Eigensolver (VQE). However, implementing them in a way that reliably provides high-quality solutions is challenging, even for toy examples. In this work, we discuss decomposition and formulation aspects of the CVRP and propose an application-driven way to measure solution quality. Considering current hardware constraints, we reduce the CVRP to a clustering phase and a set of TSPs. For the TSP, we extensively test both QAOA and VQE and investigate the influence of various hyperparameters, such as the classical optimizer choice and strength of constraint penalization. Results of QAOA are generally of limited quality because the algorithm does not reach the energy threshold for feasible TSP solutions, even when considering various extensions such as recursive and constraint-preserving mixer QAOA. On the other hand, the VQE reaches the energy threshold and shows a better performance. Our work outlines the obstacles to quantum-assisted solutions for real-world optimization problems and proposes perspectives on how to overcome them.
Combinatorial optimization problems involve find-ing an optimal solution from a finite set of feasible solutions.Dynamic Programming attempts to solve a combinatorial prob-lem by performing an exhaustive search over the entire domain of the problem.In many such cases, this exhaustive search is not effective or tractable.Travelling salesperson problem is an important combinatorial optimization problem in which the salesperson is given N cities to travel with the condition that he has to travel each city exactly once and return to the origin.Among the finite set of feasible routes, the salesperson has to choose an optimal route with shortest total distance.The route can be optimal either by cost or by distance.The classical algorithm which attempts to find the shortest distance/cost to travel all the cities run in exponential time complexity.For small number of cities, the classical algorithm is effective and feasible but as the number of cities increase, the number of possible routes and the time required to compute them grows exponentially.However, addressing this problem by implementing quantum computing significantly reduces the time required to compute these routes.A quantum algorithm is required to run on a quantum computer to obtain meaningful results as quantum computers use Quantum Bits which differ from the bits used by a classical computer.A.
With the ongoing progress of quantum computing, there is increasing interest in bringing quantum technologies into real-world applications, making practically motivated NP-hard problems particularly important to study. In this work, we solve the traveling salesperson problem (TSP) on real quantum hardware to demonstrate and analyze the performance of different quantum chips, and we benchmark these results against simulations. This comparison provides evidence supporting the feasibility of deploying quantum computation toward practical applications.
The Travelling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimisation problem with important industrial applications. Although extensively studied, quantum solutions for instances beyond a dozen locations remain uncommon. We present a hybrid penalty-free Variational Quantum Algorithm (VQA) that significantly reduces both the qubit count and the runtime through a compact penalty-free formulation scaling as O(nlog2n)\mathcal{O}(nlog_2 n)O(nlog2​n) qubits compared to conventional formulations with O(n2)\mathcal{O}(n^2)O(n2) scaling. The VQA achieves solution qualities exceeding 90\% on Rigetti quantum hardware for instances of up to 17 locations. To the best of our knowledge, this represents the largest TSP instance solved on gate-based hardware. We systematically evaluate multiple encoding and optimisation strategies, and show that warm-start initialisation improves solution quality, while runtime is reduced by nearly two orders of magnitude through the use of gradient-free optimisation methods and cost-function caching. We additionally introduce a novel VQA inspired classical machine learning model (VQAi-CML) and benchmark the VQA against VQAi-CML, a greedy heuristic, a Monte Carlo baseline, and a strong classical optimisation baseline. Across the networks evaluated, the VQA consistently achieves superior solution quality relative to VQAi-CML, greedy heuristic, and Monte Carlo baselines, but not the classical solver
We propose an amplitude encoding of the traveling salesperson problem along with a method for calculating the cost function using a probability distribution obtained on a quantum computer. Our encoding requires a number of qubits that grows logarithmically with the number of cities. We propose to calculate the cost function using a nonlinear function of expectation values of quantum operators. This is in contrast to the typical method of evaluating the cost function by summing expectation values of quantum operators. We demonstrate our method using a variational quantum eigensolver algorithm to find the shortest route for a given graph. We find that there is a broad range in the hyperparameters of the optimization procedure for which the best route is found.