EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

4231. Efficient Encoding for the Traveling Salesman Problem using Quantum Variational Algorithm

Invited abstract in session MB-42: Decomposition methods for Quantum Optimization, stream Quantum Computing Optimization.

Monday, 10:30-12:00
Room: 98 (building: 306)

Authors (first author is the speaker)

1. Imran Meghazi
LIRMM
2. Eric Bourreau
LIRMM, Montpellier University

Abstract

The Traveling Salesman Problem (TSP) stands as a quintessential challenge in combinatorial optimization, with vast implications across industries. Given the absence of efficient classical algorithms to solve this problem, there's a great interest in quantum computing to address such challenge. However, the current quantum computing landscape is dominated by Noisy Intermediate Scale Quantum (NISQ) computers. Hence, the development of efficient encodings becomes paramount in harnessing the potential of these computers to tackle complex problems like the TSP. While previous encoding techniques have been introduced, they lacked the essential characteristic of proximity between neighboring solutions. We propose an algorithm capable of efficiently computing an encoding with proximity. Through experimentation, we show that our encoding facilitates superior performance of variational quantum algorithms compared to existing encodings. Furthermore, our approach requires fewer gates and qubits compared to conventional algorithms such as QAOA, highlighting its potential for practical quantum computing implementations.

Keywords

Status: accepted


Back to the list of papers