Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms
- URL: http://arxiv.org/abs/2404.05448v2
- Date: Fri, 26 Jul 2024 10:47:34 GMT
- Title: Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms
- Authors: Manuel Schnaus, Lilly Palackal, Benedikt Poggel, Xiomara Runge, Hans Ehm, Jeanette Miriam Lorenz, Christian B. Mendl,
- Abstract summary: We investigate different encodings for the Travelling Salesperson Problem.
We find evidence that the permutation encoding can yield good results since it does not suffer from feasibility issues.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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.
Related papers
- Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
Variational Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems.
This paper explores the current state and recent developments of VQAs, emphasizing their applicability to Approximate optimization.
We implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes.
arXiv Detail & Related papers (2024-07-08T22:02:39Z) - Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems.
In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems.
We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
arXiv Detail & Related papers (2024-04-17T11:00:12Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems.
This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios.
We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
arXiv Detail & Related papers (2023-06-15T15:28:12Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry.
In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
arXiv Detail & Related papers (2023-06-14T13:44:35Z) - Recommending Solution Paths for Solving Optimization Problems with
Quantum Computing [4.306566710489809]
We propose a framework designed to identify and recommend the best-suited solution paths.
State-of-the-art hybrid algorithms, encoding and decomposition techniques can be integrated in a modular manner.
We demonstrate and validate our approach on a selected set of options and illustrate its application on the capacitated vehicle routing problem.
arXiv Detail & Related papers (2022-12-21T15:55:43Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem.
Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
arXiv Detail & Related papers (2022-11-01T07:52:47Z) - Analysis of The Vehicle Routing Problem Solved via Hybrid Quantum
Algorithms in Presence of Noisy Channels [0.0]
The objective is to plan routes of vehicles to deliver goods to a fixed number of customers with optimal efficiency.
We build a basic VRP solver for 3 and 4 cities using the variational quantum eigensolver on a fixed ansatz.
We find that the performance of the quantum algorithm depends heavily on what noise model is used.
arXiv Detail & Related papers (2022-05-13T11:29:12Z) - Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
Vehicle routing problem (VRP) is an NP-hard optimization problem.
This work builds a basic VRP solution for 3 and 4 cities using variational quantum eigensolver on a variable ANSATZ.
arXiv Detail & Related papers (2021-12-28T10:20:42Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions.
Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
arXiv Detail & Related papers (2021-06-24T20:16:02Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.