The reduction of CO2emissions is one of the major challenges in the current century. A game-changer might be quantum computing due to the proposed capabilities. A key field of interest for reducing CO2emissions is the energy sector being transformed from fossil-based to be based on renewable energies and simultaneously combining electricity, heating, mobility, and manufacturing industries.Here, we study an use case for optimal charging scheduling of battery-electric service vehicles considering the requirements of their tasks, local solar power generation, and their battery capabilities to minimize power grid usage and so CO2emissions from fossil-based electricity generation.The study compares benchmark results obtained classically with results obtained by the quantum approximate optimization algorithm (QAOA) to show the current capability of gate-based quantum optimization for a real-world use case. We present different formulations of the optimization problem and specific considerations for our use case necessary to yield optimal solutions reproducible with IBM’s gate-based quantum computers. Here, we used Qiskit’s built-in QAOA method but also self-made methods to examine the influence of the complexity of the problem formulation (penalty factors, landscape of cost function, etc.) as well as the dependence on parameters of the QAOA method (classical optimizer, result extraction, etc.). To obtain reliable results, we used different physical backends and simulations.Finally, we summarize or results and address future improvements for the used QAOA approach for automated real-world applications.
The reduction of CO2emissions is one of the major challenges in the current century. A game-changer might be quantum computing due to the proposed capabilities. A key field of interest for reducing CO2emissions is the energy sector being transformed from fossil-based to be based on renewable energies and simultaneously combining electricity, heating, mobility, and manufacturing industries.Here, we study an use case for optimal charging scheduling of battery-electric service vehicles considering the requirements of their tasks, local solar power generation, and their battery capabilities to minimize power grid usage and so CO2emissions from fossil-based electricity generation.The study compares benchmark results obtained classically with results obtained by the quantum approximate optimization algorithm (QAOA) to show the current capability of gate-based quantum optimization for a real-world use case. We present different formulations of the optimization problem and specific considerations for our use case necessary to yield optimal solutions reproducible with IBM’s gate-based quantum computers. Here, we used Qiskit’s built-in QAOA method but also self-made methods to examine the influence of the complexity of the problem formulation (penalty factors, landscape of cost function, etc.) as well as the dependence on parameters of the QAOA method (classical optimizer, result extraction, etc.). To obtain reliable results, we used different physical backends and simulations.Finally, we summarize or results and address future improvements for the used QAOA approach for automated real-world applications.
Battery electric service vehicles are one step to reduce CO2emissions in the mobility sector. We present an use case for optimal charging scheduling in combination with local solar power generation to minimize power grid usage. The study compares results obtained with a classical optimizer and with a quantum computing algorithm on real quantum hardware. It is shown that for most benchmark experiments, the quantum computing method yields an optimal solution however the quantum approximate optimization algorithm is more sensitive to penalty factors than the classical optimization. Additionally, we present a comparison of the computing times and give a brief review of the current state of IBM’s gate-based quantum computing.
The major advances in quantum computing over the last few decades have sparked great interest in applying it to solve the most challenging computational problems in a wide variety of areas. One of the most pronounced domains here are optimization problems and a number of algorithmic approaches have been proposed for their solution. For the current noisy intermediate-scale quantum (NISQ) computers the quantum approximate optimization algorithm (QAOA), the variational quantum eigensolver (VQE), and quantum annealing (QA) are the central algorithms for this problem class. The two former can be executed on digital gate-model quantum computers, whereas the latter requires a quantum annealer. Across all hardware architectures and manufactures, the quantum computers available today share the property of being too error-prone to reliably execute involved quantum circuits as they typically arise from quantum optimization algorithms. In order to characterize the limits of existing quantum computers, many component and system level benchmarks have been proposed. However, owing to the complex nature of the errors in quantum systems these benchmark fail to provide predictive power beyond simple quantum circuits and small examples. Application oriented benchmarks have been proposed to remedy this problem, but both, results from real quantum systems as well as use cases beyond constructed academic examples, remain very rare. This paper addresses precisely this gap by considering two industrial relevant use cases: one in the realm of optimizing charging schedules for electric vehicles, the other concerned with the optimization of truck routes. Our central contribution are systematic series of examples derived from these uses cases that we execute on different processors of the gate-based quantum computers of IBM as well as on the quantum annealer of D-Wave.
The electric vehicle (EV) industry is currently afflicted with inefficient charging systems. Considering the growing adoption of EVs, optimization strategies for efficient charging, and overcoming constraints such as limited power supply and extended waiting times, are required. The knapsack algorithm, a classical technique that maximizes value and capacity, enables the efficient utilization of the limited available power supply while minimizing waiting times in EV charging scenarios. However, the knapsack problem is notoriously NP-hard, making it difficult to find efficient solutions classically. In this paper, we propose an approach that leverages the quantum approximation optimization algorithm (QAOA) to resolve the EV charging problem using a knapsack-based formulation. By incorporating a knapsack problem constraint into the QAOA, we overcome the limitations of the original QAOA method and provide a potential solution to the knapsack problem. We extensively evaluate and analyze the effectiveness of our approach in finding optimal EV charging solutions in both noise-free simulations and noisy real quantum devices. The proposed approach achieves impressive approximation ratios of up to 100% and 50% in noise-free and noisy environments, respectively. Even with small circuit sizes, we confirm that our approach can find optimal solutions effectively.
When talking about rising demand for electricity, shifting to renewable energy sources, and prioritizing grid stability, one thing that is crucial is optimizing the scheduling of electricity load based on the demand. There are various classical machine learning (ML) and meta-heuristic optimization methods (Particle Swarm Optimization, Genetic Algorithms, Differential Evolution, Simulated Annealing) used to forecast load, and then schedule accordingly to minimize cost, reduce the peak load of system, and improve the overall efficiency. However, these methods struggle in handling large-scale combinatorial complexity and multiple constrained systems in real time. This paper presents a comparative study of classical ML-based optimization techniques and introduces a novel quantum-machine-learning approach using the Quantum Approximate Optimization Algorithm (QAOA) for electricity load scheduling. Initially, a survey was conducted and several classical techniques for optimization and forecasting were evaluated on realistic demand data. The paper highlights their strengths and drawbacks in terms of solution quality, computational time, and scalability. Then, the paper proposes and apply QAOA to the same scheduling problem, formulating load scheduling as a quadratic unconstrained binary optimization (QUBO) model suitable for quantum optimization. We assess the performance of QAOA against classical methods under identical constraints. Thus, Simulated Annealing produces a normalized cost of 0.00029 (after 37 seconds) whereas the cost found by Differential Evolution is 0.1314 and by the Genetic Algorithm 0.4379. This tends to confirm the validity of classical heuristics for smaller problems [16]. Our results show that while classical methods perform well for small to medium scale problems, the QAOA approach offers competitive or superior performance in terms of optimization quality and scalability for larger, more complex instances, with potential reductions in computation time under certain conditions. We conclude by discussing the practical challenges of implementing QAOA (e.g. noise, parameter tuning) and suggest directions for future research to advance quantum-assisted optimization in electricity scheduling.
In order to qualify quantum algorithms for industrial NP-Hard problems, comparing them to available polynomial approximate classical algorithms and not only to exact exponential ones is necessary. This is a great challenge as, in many cases, bounds on the reachable approximation ratios exist according to some highly-trusted conjectures of Complexity Theory. An interesting setup for such qualification is thus to focus on particular instances of these problems known to be "less difficult" than the worst-case ones and for which the above bounds can be outperformed: quantum algorithms should perform at least as well as the conventional approximate ones on these instances, up to very large sizes. We present a case study of such a protocol for two industrial problems drawn from the strongly developing field of smart-charging of electric vehicles. Tailored implementations of the Quantum Approximate Optimization Algorithm (QAOA) have been developed for both problems, and tested numerically with classical resources either by emulation of Pasqal's Rydberg atom based quantum device or using Atos Quantum Learning Machine. In both cases, quantum algorithms exhibit the same approximation ratios as conventional approximation algorithms or improve them. These are very encouraging results, although still for instances of limited size as allowed by studies on classical computing resources. The next step will be to confirm them on larger instances, on actual devices, and for more complex versions of the problems addressed.
In order to qualify quantum algorithms for industrial NP-Hard problems, comparing them to available polynomial approximate classical algorithms and not only to exact ones -- exponential by nature -- , is necessary. This is a great challenge as, in many cases, bounds on the reachable approximation ratios exist according to some highly-trusted conjectures of Complexity Theory. An interesting setup for such qualification is thus to focus on particular instances of these problems known to be "less difficult" than the worst-case ones and for which the above bounds can be outperformed: quantum algorithms should perform at least as well as the conventional approximate ones on these instances, up to very large sizes. We present a case study of such a protocol for two industrial problems drawn from the strongly developing field of smart-charging of electric vehicles. Tailored implementations of the Quantum Approximate Optimization Algorithm (QAOA) have been developed for both problems, and tested numerically with classical resources either by emulation of Pasqal's Rydberg atom based quantum device or using Atos Quantum Learning Machine. In both cases, quantum algorithms exhibit the same approximation ratios than conventional approximation algorithms, or improve them. These are very encouraging results, although still for instances of limited size as allowed by studies on classical computing resources. The next step will be to confirm them on larger instances, on actual devices, and for more complex versions of the problems addressed.