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.
The rapid deployment of electric vehicles (EVs) in public parking facilities and fleet operations raises challenging intra-day charging scheduling problems under tight charger capacity and limited dwell times. We model this problem as a variant of the Partition Coloring Problem (PCP), where each vehicle defines a partition, its candidate charging intervals are vertices, and temporal and resource conflicts are represented as edges in a conflict graph. On this basis, we design a branch-and-price algorithm in which the restricted master problem selects feasible combinations of intervals, and the pricing subproblem is a maximum independent set problem. The latter is reformulated as a quadratic unconstrained binary optimization (QUBO) model and solved by quantum-annealing-inspired algorithms (QAIA) implemented in the MindQuantum framework, specifically the ballistic simulated branching (BSB) and simulated coherent Ising machine (SimCIM) methods, while the master problem is solved by Gurobi. Computational experiments on a family of synthetic EV charging instances show that the QAIA-enhanced algorithms match the pure Gurobi-based branch-and-price baseline on small and medium instances, and clearly outperform it on large and hard instances. In several cases where the baseline reaches the time limit with non-zero optimality gaps, the QAIA-based variants close the gap and prove optimality within the same time budget. These results indicate that integrating QAIA into classical decomposition schemes are a promising direction for large-scale EV charging scheduling and related PCP applications.