Fewer Quantum Measurements Unlock Better eV Charging Schedules

Scientists at Honda Research Institute, led by Linus Ekstrøm in collaboration with Leiden University, are investigating the impact of encoding methods on the performance of variational quantum algorithms when applied to challenging optimisation problems. The team’s research centres on a comparative analysis of qubit and qudit encodings, specifically within the context of realistically modelled electric vehicle (EV) fleet management. Their work focuses on the simultaneous optimisation of EV charging schedules and vehicle-to-trip assignments, demonstrating that utilising a qudit encoding significantly reduces the computational resources and simulation time required, all while maintaining comparable, or even improved, optimisation performance. These findings highlight the potential of qudit-native encodings as a crucial pathway for addressing integer and multivalued scheduling challenges inherent in variational quantum optimisation

Qudit encoding substantially lowers computational cost for large-scale electric vehicle fleet

The research demonstrates that qudit encoding reduced the Hilbert-space dimension by a factor of eight compared to qubit encoding when applied to realistic electric vehicle fleet management problems. The Hilbert space represents the totality of all possible states of a quantum system; a smaller Hilbert space directly translates to reduced computational demands. This exponential reduction in dimensionality, previously difficult to achieve with traditional binary representations, unlocks the potential to simulate substantially larger and more complex EV fleets. Prior to this work, computational limitations often restricted optimisation studies to fleets comprising only a few vehicles. Typically, these fleets contained fewer than 5 vehicles. This advance enables the exploration of more realistic scenarios, involving fleets of 20 or more vehicles, with a corresponding increase in accuracy, thereby paving the way for practical applications of quantum computing in logistical optimisation. The ability to model larger fleets is critical for capturing the nuances of real-world operations, including variations in demand, charging infrastructure availability, and vehicle capacity.

Crucially, comparable, or improved, optimisation performance was maintained while sharply decreasing the computational resources needed for simulations. The simulations, conducted using exact state-vector simulations on small instances, up to 10 EVs, completed with significantly shorter runtimes. This allows for more realistic modelling of logistical challenges in scenarios previously inaccessible due to computational limits. For example, the team was able to explore scenarios with varying charging costs and time-of-use tariffs, providing a more granular understanding of optimal charging strategies. These results, while promising, were obtained using simulations and scaling to genuinely large, real-world EV fleets still requires overcoming significant hurdles in quantum hardware development and error mitigation. Specifically, maintaining qubit coherence and fidelity over extended periods remains a major challenge. Further research will focus on addressing these limitations and exploring hybrid classical-quantum approaches, leveraging the strengths of both computational paradigms. This includes investigating techniques such as variational quantum eigensolvers (VQEs) and quantum approximate optimisation algorithms (QAOAs) in conjunction with classical optimisation routines.

Qudit-based algorithms offer potential fleet scheduling efficiencies despite current hardware

Efficient scheduling of both charging and trip assignments represents a complex logistical puzzle when optimising electric vehicle fleets; current solutions rely heavily on classical computing power and often struggle with scalability. The problem is considered NP-hard, meaning that the computational effort required to find the optimal solution grows exponentially with the size of the fleet. Qudits, quantum digits capable of representing more than two values, unlike qubits which are limited to 0 or 1, demonstrate substantial resource reductions in simulations, though these gains remain unproven on actual quantum hardware. A qudit with d levels can represent d different states, allowing for a more compact representation of multivalued variables. Dr. Eleanor Rieffel and colleagues at the Institute for Quantum Computing explicitly acknowledge this limitation, noting that achieving a true quantum speedup requires the development of stable and scalable quantum computers with a sufficient number of qubits or qudits and low error rates. Current noisy intermediate-scale quantum (NISQ) devices are prone to errors that can significantly degrade the performance of quantum algorithms.

This work offers valuable insight for algorithm development, even acknowledging that fully functional, fault-tolerant quantum computers remain a future prospect. Developers can proactively prepare algorithms ready to exploit quantum hardware when it matures, potentially unlocking efficiencies in complex logistical problems extending beyond electric vehicles. The principles of qudit-based encoding can be applied to a wide range of optimisation problems, including supply chain management, resource allocation, and financial modelling. An integer-based encoding, facilitated by qudits, offers a more efficient method for representing data within quantum algorithms when optimising complex electric vehicle fleet management, representing a key area for logistical efficiency. This advance stems from the ability of qudits to exponentially decrease the size of the ‘Hilbert space’, the total number of possible states a quantum system can occupy, simplifying calculations and reducing computational complexity. By reducing the Hilbert space, the quantum computer requires fewer resources to explore the solution space, potentially leading to faster and more accurate optimisation. The team’s findings suggest that qudit-based approaches could offer a significant advantage over traditional qubit-based methods for tackling these types of complex logistical challenges, provided the necessary hardware advancements are made.

The researchers demonstrated that using qudits, quantum units capable of representing more than two states, improves the efficiency of solving complex electric vehicle fleet management problems. This alternative to conventional qubit encoding exponentially reduces the computational resources needed while achieving comparable or better optimisation performance. The study focused on problems involving both uni- and bi-directional charging, highlighting the potential of qudit-native encodings for integer and multi-valued scheduling. Although stable and scalable quantum computers are still under development, this work provides a valuable encoding strategy for future algorithm implementation.