EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Combinatorial Optimization
Status: accepted
Back to the list of papers