TY - GEN
T1 - Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms
AU - Schnaus, Manuel
AU - Palackal, Lilly
AU - Poggel, Benedikt
AU - Runge, Xiomara
AU - Ehm, Hans
AU - Lorenz, Jeanette Miriam
AU - Mendl, Christian B.
N1 - Publisher Copyright:
© 2024 IEEE.
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
KW - Encoding
KW - Quantum Optimization
KW - Travelling Salesperson Problem
KW - Variational Quantum Algorithms
UR - http://www.scopus.com/inward/record.url?scp=85203834742&partnerID=8YFLogxK
U2 - 10.1109/QSW62656.2024.00022
DO - 10.1109/QSW62656.2024.00022
M3 - Conference contribution
AN - SCOPUS:85203834742
T3 - Proceedings - 2024 IEEE International Conference on Quantum Software, QSW 2024
SP - 81
EP - 87
BT - Proceedings - 2024 IEEE International Conference on Quantum Software, QSW 2024
A2 - Chang, Rong N.
A2 - Chang, Carl K.
A2 - Yang, Jingwei
A2 - Jin, Zhi
A2 - Sheng, Michael
A2 - Fan, Jing
A2 - Fletcher, Kenneth
A2 - He, Qiang
A2 - Faro, Ismael
A2 - Leymann, Frank
A2 - Barzen, Johanna
A2 - de la Puente, Salvador
A2 - Feld, Sebastian
A2 - Wimmer, Manuel
A2 - Atukorala, Nimanthi
A2 - Wu, Hongyue
A2 - Elkouss, David
A2 - Garcia-Alonso, Jose
A2 - Sarkar, Aritra
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 3rd IEEE International Conference on Quantum Software, QSW 2024
Y2 - 7 July 2024 through 13 July 2024
ER -