Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems

arXiv (Cornell University)

Abstract

Variational quantum algorithms have attracted attention for their potential to solve combinatorial optimization problems. We study how the choice of encoding affects the resource requirements and optimization behavior of a variational quantum optimization algorithm. In order to quantify these effects, realistically inspired constrained electric vehicle (EV) fleet management problems were considered. These problems couple determining the optimal EV battery charging schedule with assigning EVs to trips requested by customers. We compare a conventional binary (qubit) trip encoding with an integer (qudit) encoding that represents assignments more directly. Both encodings guarantee the same feasible solution set, while the qudit encoding exponentially reduces the required Hilbert-space dimension. We solve many random instances of highly constrained uni- and bi-directional charging problems using qudit-based quantum approximate optimization algorithm (QAOA) and thoroughly evaluate the performance results. We find that the qudit encoding of customer trips achieves similar or better optimization performance at much reduced resource requirements and shorter simulation runtime. These results highlight qudit-native encodings as a practical route for integer and multi-valued scheduling problems in variational quantum optimization.

Authors 3

1. Linus Ekstrøm

   Honda (Japan)

   Affiliation as printed

   Honda Research Institute Europe GmbH , Carl-Legien Straße 30 , 63073 Offenbach , Germany

2. Hao Wang Aachen

   Leiden University · University of Applied Sciences Leiden

   Affiliation as printed

   Applied Quantum Algorithms Netherlands

   LIACS , Universiteit Leiden , Niels Bohrweg 1 , 2333 CA Leiden , ⟨𝑎𝑄𝑎 𝐿

3. Sebastian Schmitt

   Honda (Japan)

   Affiliation as printed

   Honda Research Institute Europe GmbH , Carl-Legien Straße 30 , 63073 Offenbach , Germany