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.
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.
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.
Complex optimization problems, such as traffic routing and electric vehicle (EV) charging scheduling, are becoming increasingly challenging for intelligent transportation systems (ITSs), in particular as computational resources are limited and network conditions evolve frequently. This paper explores a quantum computing approach to address these issues by proposing a hybrid quantum-classical (HQC) workflow that leverages the variational quantum eigensolver (VQE), an algorithm particularly well suited for execution on noisy intermediate-scale quantum (NISQ) hardware. To this end, the EV charging scheduling and traffic routing problems are both reformulated as binary optimization problems and then encoded into Ising Hamiltonians. Within each VQE iteration, a parametrized quantum circuit (PQC) is prepared and measured on the quantum processor to evaluate the Hamiltonian’s expectation value, while a classical optimizer—such as COBYLA, SPSA, Adam, or RMSProp—updates the circuit parameters until convergence. In order to find optimal or nearly optimal solutions, VQE uses PQCs in combination with classical optimization algorithms to iteratively minimize the problem Hamiltonian. Simulation results exhibit that the VQE-based method increases the efficiency of EV charging coordination and improves route selection performance. These results demonstrate how quantum computing will potentially advance optimization algorithms for next-generation ITSs, representing a practical step toward quantum-assisted mobility solutions.
The integration of bidirectional (V2G) charging allows electric vehicle (EV) fleets to operate as distributed energy assets. However, the joint optimization of charging schedules and trip assignments is NP-hard. Moreover, bidirectional power flows create non-monotonic state-of-charge (SoC) dynamics that weaken standard dual-based Benders cuts. We propose a hybrid quantum-classical Benders decomposition framework. To overcome the qubit overhead associated with encoding feasibility cuts, we introduce logic-based conflict cuts, which require near-zero auxiliary qubits. Furthermore, we develop a sparse recursive SoC formulation that reduces the constraint-matrix density by a factor of T/3 in the horizon length T. We demonstrate that our framework recovers MILP-optimal solutions on benchmark instances with a low auxiliary-qubit budget, and, as a minimal proof of concept, we execute a small instance end-to-end on IBM quantum hardware.
Electric vehicles (EVs) have emerged as the transportation of the future due to their environmental benefits and fuel efficiency. However, as EVs adoption grows, efficiently managing charging schedules has become a critical challenge due to limited charging infrastructures. EV charging scheduling (EVCS) is a well-known problem within EV charging systems and is generally modeled as an NP-hard graph coloring problem. Recently, quantum computing has emerged as a novel technology that revolutionizes the conventional approach in solving complex optimization problems. However, current noisy intermediate-scale quantum (NISQ) computers lack sufficient hardware capacity to tackle large problem spaces. To address this insufficiency, we propose a hybrid quantum-classical (HQC) optimization pipeline mainly consisting of Hamiltonian reduction, quantum computation, and solution recovery. Theoretically, we demonstrate that optimal graph coloring and EVCS solutions can be recovered if the ground state is found for the reduced Hamiltonian. Numerically, using the Caltech ACN dataset (2018-2019 observations), our approach increases the number of executable EVCS instances on quantum simulators (IonQ, QASM, and Rigetti) from 1.30%- 2.28% to 54.23%-54.72%, thereby outperforming Roof Duality and FastHare (2.28%-6.68%). On the D-Wave Advantage, executable instances increase from 11.89% to 80.46%, compared to 13.52% and 19.87% with Roof Duality and FastHare. These results present promising opportunities for advancing quantum computing research on EVCS within intelligent transportation systems.
A frequent starting point of quantum computation platforms is the two-state quantum system, i.e., the qubit. However, in the context of integer optimization problems, relevant to scheduling optimization and operations research, it is often more resource-efficient to employ quantum systems with more than two basis states, so-called qudits. Here, we discuss the quantum approximate optimization algorithm (QAOA) for qudit systems. We illustrate how the QAOA can be used to formulate a variety of integer optimization problems such as graph coloring problems or electric vehicle charging optimization. In addition, we comment on the implementation of constraints and describe three methods to include these in a quantum circuit of a QAOA by penalty contributions to the cost Hamiltonian, conditional gates using ancilla qubits, and a dynamical decoupling strategy. Finally, as a showcase of qudit-based QAOA, we present numerical results for a charging optimization problem mapped onto a maximum-k-graph-coloring problem. Our work illustrates the flexibility of qudit systems to solve integer optimization problems.
Combinatorial optimization problems have attracted much interest in the quantum computing community in the recent years as a potential testbed to showcase quantum advantage. In this paper, we show how to exploit multilevel carriers of quantum information—qudits—for the construction of algorithms for constrained quantum optimization. These systems have been recently introduced in the context of quantum optimization and they allow us to treat more general problems than the ones usually mapped into qubit systems. In particular, we propose a hybrid classical quantum heuristic strategy that allows us to sample constrained solutions while greatly reducing the search space of the problem, thus optimizing the use of fewer quantum resources. As an example, we focus on the Electric Vehicle Charging and Routing Problem (EVCRP). We translate the classical problem and map it into a quantum system, obtaining promising results on a toy example which shows the validity of our technique.