Quantum-classical system solves EV charging on IBM hardware

Researchers at Fraunhofer IOSB-AST and Honda Research Institute Europe GmbH have developed a hybrid quantum-classical framework to optimize electric vehicle (EV) charging and trip assignments. The work addresses a computationally difficult problem; jointly scheduling charging and trips is NP-hard, and introduces logic-based conflict cuts requiring near-zero auxiliary qubits to reduce the computational load. A sparse recursive state-of-charge formulation further improves efficiency by reducing constraint-matrix density by approximately a factor of T/3, where T represents the planning horizon length. The team executed a small instance end-to-end on IBM quantum hardware.

Bidirectional V2G Integration for EV Fleets

This reduction in density directly addresses a key challenge in bidirectional vehicle-to-grid (V2G) integration, where traditional optimization methods struggle with the computational demands of modeling non-monotonic SoC dynamics. Unlike unidirectional charging, which simplifies battery limit evaluations, bidirectional discharging necessitates dense constraints at each timestep, significantly increasing computational complexity. This architecture iteratively refines solutions through a master problem exploring trip assignments and a subproblem evaluating feasibility and cost, with cutting planes passed between them to improve accuracy.

The team’s innovation lies in the introduction of logic-based conflict cuts, designed to minimize the qubit overhead typically associated with encoding feasibility cuts in quantum optimization problems. These cuts allow for a near-zero-qubit QUBO encoding, a significant step towards practical quantum implementation.

The ability to run, even a limited instance, on existing quantum hardware suggests a pathway toward more efficient and scalable solutions for managing increasingly complex EV fleets as distributed energy resources. The researchers note that this work is the first hybrid quantum-classical framework applied to the joint optimization of bidirectional EV charging and fleet scheduling.

Hybrid Benders Decomposition with Logic-Based Cuts

A reduction in computational complexity achieved through a novel approach to electric vehicle (EV) charging optimization allows for a constraint-matrix density decrease of approximately T/3, where T represents the length of the planning horizon. This efficiency stems from a sparse recursive state-of-charge formulation detailed in a new hybrid quantum-classical framework, designed to address the challenges of jointly scheduling EV charging and trip assignments. The framework tackles an inherently difficult problem, the optimization is NP-hard, by combining the strengths of both classical and quantum computing techniques.

Standard dual-based Benders cuts, commonly used in optimization problems, are weakened by the non-monotonic state-of-charge dynamics created by bidirectional power flows, the ability of EVs to both draw power from and supply it back to the grid. The logic-based cuts circumvent this issue, allowing for a more efficient encoding of feasibility constraints.

The team’s approach builds on classical Benders decomposition, a technique that breaks down large-scale optimization problems into smaller, more manageable subproblems. When a proposed solution is feasible, its dual variables generate an optimality cut; when infeasible, a feasibility cut is derived to prevent the algorithm from revisiting that solution. The researchers’ logic-based cuts refine this process, improving both speed and accuracy.

Recursive SoC Formulation Reduces Constraint Density

The reduction in constraint density stems from a reformulation of how SoC bounds are handled, lessening the computational burden of large-scale electric vehicle (EV) fleet optimization. Standard methods typically generate a constraint matrix with a density proportional to T squared, but this new approach significantly diminishes that complexity. This improved sparsity directly addresses a key bottleneck in solving the joint optimization of EV charging schedules and trip assignments, a problem known to be NP-hard.

The framework presented achieves this reduction by recursively defining the SoC constraints, limiting the number of non-zero elements within the constraint matrix. This is critical because the SoC bounds represent the densest portion of the overall model, directly impacting memory and processing time. Beyond the recursive SoC formulation, the team also introduced logic-based conflict cuts designed to minimize qubit overhead in the quantum portion of their hybrid approach. These cuts require near-zero auxiliary qubits.

The framework’s efficiency stems from a design prioritizing minimal auxiliary qubit usage, a critical factor in scaling quantum optimization algorithms. The framework recovers MILP-optimal solutions on benchmark instances with a low auxiliary-qubit budget, and the team executed a small instance end-to-end on IBM quantum hardware.

Joint Optimization of Trip Assignment and Charging

This improvement stems from the way the team modeled battery state, reducing the number of non-zero elements needed to represent the problem mathematically. Specifically, the formulation considers that a trip is present from its departure onward, contributing an average of R(T + 1)/2 non-zero elements across all R trips, and one additional row with T charging and R assignment non-zero elements at the horizon’s end.

This approach contrasts with traditional methods that demand extensive qubit resources, making practical implementation challenging. The team’s work builds on previous investigations into d-level qudit systems, further refining the encoding of the EV charging problem for quantum computation. The team previously benchmarked quantum approximate optimization algorithm (QAOA) on smaller instances and subsequently investigated qudit systems to improve encoding efficiency, establishing a foundation for this current work.

Framework Validation on IBM Quantum Hardware

This formulation addresses a key challenge in modeling bidirectional power flows, which introduce non-monotonic dynamics that typically complicate standard optimization techniques. The team’s algorithm iteratively solves a master problem on quantum hardware to generate candidate solutions, then a subproblem classically to refine the solution and identify conflicts. If the subproblem is infeasible, conflict cuts are added to the master problem, guiding the optimization process.

The framework’s performance was assessed by comparing its results to those obtained through mixed-integer linear programming, confirming its ability to recover optimal solutions within a limited auxiliary-qubit budget. The team concludes that the approach offers a pathway toward solving large-scale bidirectional EV charging and trip assignment problems.

More like this

Quantum ApplicationsIonQ and EPB Detail Quantum Applications for Grid Reconfiguration

Quantum Computing Business NewsLG CNS will use D-Wave’s quantum tech in South Korea and beyond

Quantum SecurityScience Applications delivers first practical quantum solutions to US agencies

Quantum AlgorithmsNew quantum algorithm maps out optimal qubit gate performance