Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Access

Leveraging Knapsack QAOA Approach for Optimal Electric Vehicle Charging

Kimleang Kea, Chansreynich Huot, Youngsun Han

Published Jan 1, 2023• 18 citations
Publisher

Abstract

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.

DOI
10.1109/access.2023.3320800

Related papers

Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles

Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel +4 more

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.

arXiv:2012.14859•Dec 29, 2020•1 citation

Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles

Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel +4 more

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.

EPJ Quantum Technology•May 17, 2021•46 citations

Quantum-Powered Optimization for Electric Vehicle Charging Infrastructure Deployment

Nazmush Sakib, Xin Chen

The infrastructure development of electric vehicle charging stations (EVCS) is critical to the integration of electrical vehicles (EVs) into transportation systems, which requires significant investment and has long-term impact on the adoption of EVs. In this paper, a mathematical model is developed to identify the optimal placement of EVCS by utilizing a novel quantum annealing (QA) algorithm and quantum computation (QC). The objective of the optimization model is to determine the locations of EVCS that maximize their service quality for EV users. The model is validated using a real-world case study and solved using commercially available quantum computers from D-Wave. The case study shows that the QA algorithm can find the optimal placement of EVCS within seconds. The quality of the solutions obtained using QC is not sensitive to the shape or size of the area where EVCS are to be deployed.

arXiv:2411.06684•Nov 11, 2024•0 citations

Enhancing Knapsack-Based Financial Portfolio Optimization Using Quantum Approximate Optimization Algorithm

Chansreynich Huot, Kimleang Kea, Tae-Kyung Kim +1 more

Portfolio optimization is a primary component of the decision-making process in finance, aiming to tactfully allocate assets to achieve optimal returns while considering various constraints. Herein, we proposed a method that uses the knapsack-based portfolio optimization problem and incorporates the quantum computing capabilities of the quantum walk mixer with the quantum approximate optimization algorithm (QAOA) to address the challenges presented by the NP-hard problem. Additionally, we present the sequential procedure of our suggested approach and demonstrate empirical proof to illustrate the effectiveness of the proposed method in finding the optimal asset allocations across various constraints and asset choices. Moreover, we discuss the effectiveness of the QAOA components in relation to our proposed method. Consequently, our study successfully achieves the approximate ratio of the portfolio optimization technique using a circuit layer of$p\geqslant 3$, compared to the classical best-known solution of the knapsack problem. Our proposed methods potentially contribute to the growing field of quantum finance by offering insights into the potential benefits of employing quantum algorithms for complex optimization tasks in financial portfolio management.

arXiv:2402.07123•IEEE Access•Jan 1, 2024•14 citations

A Quantum-Inspired QAOA Solver for Knapsack Problems with 100-Qubit Scalability and 100,000x Speedup

Shan-Jung Hou, Chuan-Chi Wang, Po-Hsuan Huang +2 more

Combinatorial optimization problems play a central role in computer science and real-world decision-making, as they aim to find the optimal solution from a large set of possibilities. Among these, the Knapsack Problem is a fundamental example with many practical applications. The Quantum Approximate Optimization Algorithm (QAOA) is a quantum-classical hybrid approach designed to address such problems. However, existing simulation approaches for QAOA applied to the Knapsack Problem do not scale well because they fail to exploit the problem's structural properties. To overcome these limitations, this study exploits the entangling characteristics of circuits in the Knapsack Problem and develops an optimized solver tailored to this setting. The key technical contributions include an entanglement-free circuit simulation method that reduces complexity from exponential to linear for non-entangling circuits, enabling 24,000x speedups for QAOA ansatz circuit simulations, and a two-phase parameter selection strategy that enhances the efficiency of finding optimal Knapsack solutions. Our solver extends the scalability of QAOA simulations from the previous limit of approximately 10 qubits to 100 qubits within a system memory of 256 GB. It achieves performance gains of over 100,000x for solving Knapsack Problems while maintaining high solution quality.

ACM Conference on Research in Adaptive and Convergent Systems (RACS)•Nov 16, 2025•0 citations

Joint optimization of electric vehicle routes and charging locations through learning charge constraints using QUBO solvers

A. Okada, Keisuke Otaki, Hiroaki Yoshida

Optimal routing problems of electric vehicles (EVs) have attracted much attention in recent years, and installation of charging stations is an important issue for EVs. Hence, we focus on the joint optimization of the location of charging stations and the routing of EVs. When routing problems are formulated in the form of quadratic unconstrained binary optimization (QUBO), specialized solvers such as quantum annealers are expected to provide optimal solutions with high speed and accuracy. However, battery capacity constraints make it hard to formulate into QUBO form without a large number of auxiliary qubits. Here, we propose a sequential optimization method utilizing the Bayesian inference and QUBO solvers, in which the battery capacity constraints are automatically learned. This method enables us to optimize the number and location of charging stations and the routing of EVs with a small number of searches. Applying this method to a routing problem of 20 locations, we observed consistent convergence toward battery-feasible solutions across independent runs, demonstrating stable learning behavior of the proposed framework. Small-scale validation experiments using exhaustive enumeration show that the framework reliably discovers feasible configurations close to the global optimum, while runtime and QUBO-size analyses clarify its computational characteristics.

arXiv:2506.04687•Scientific Reports•Jun 2, 2026•1 citation
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.
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.
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.
The infrastructure development of electric vehicle charging stations (EVCS) is critical to the integration of electrical vehicles (EVs) into transportation systems, which requires significant investment and has long-term impact on the adoption of EVs. In this paper, a mathematical model is developed to identify the optimal placement of EVCS by utilizing a novel quantum annealing (QA) algorithm and quantum computation (QC). The objective of the optimization model is to determine the locations of EVCS that maximize their service quality for EV users. The model is validated using a real-world case study and solved using commercially available quantum computers from D-Wave. The case study shows that the QA algorithm can find the optimal placement of EVCS within seconds. The quality of the solutions obtained using QC is not sensitive to the shape or size of the area where EVCS are to be deployed.
Portfolio optimization is a primary component of the decision-making process in finance, aiming to tactfully allocate assets to achieve optimal returns while considering various constraints. Herein, we proposed a method that uses the knapsack-based portfolio optimization problem and incorporates the quantum computing capabilities of the quantum walk mixer with the quantum approximate optimization algorithm (QAOA) to address the challenges presented by the NP-hard problem. Additionally, we present the sequential procedure of our suggested approach and demonstrate empirical proof to illustrate the effectiveness of the proposed method in finding the optimal asset allocations across various constraints and asset choices. Moreover, we discuss the effectiveness of the QAOA components in relation to our proposed method. Consequently, our study successfully achieves the approximate ratio of the portfolio optimization technique using a circuit layer ofp⩾3p\geqslant 3p⩾3, compared to the classical best-known solution of the knapsack problem. Our proposed methods potentially contribute to the growing field of quantum finance by offering insights into the potential benefits of employing quantum algorithms for complex optimization tasks in financial portfolio management.
Combinatorial optimization problems play a central role in computer science and real-world decision-making, as they aim to find the optimal solution from a large set of possibilities. Among these, the Knapsack Problem is a fundamental example with many practical applications. The Quantum Approximate Optimization Algorithm (QAOA) is a quantum-classical hybrid approach designed to address such problems. However, existing simulation approaches for QAOA applied to the Knapsack Problem do not scale well because they fail to exploit the problem's structural properties. To overcome these limitations, this study exploits the entangling characteristics of circuits in the Knapsack Problem and develops an optimized solver tailored to this setting. The key technical contributions include an entanglement-free circuit simulation method that reduces complexity from exponential to linear for non-entangling circuits, enabling 24,000x speedups for QAOA ansatz circuit simulations, and a two-phase parameter selection strategy that enhances the efficiency of finding optimal Knapsack solutions. Our solver extends the scalability of QAOA simulations from the previous limit of approximately 10 qubits to 100 qubits within a system memory of 256 GB. It achieves performance gains of over 100,000x for solving Knapsack Problems while maintaining high solution quality.
Optimal routing problems of electric vehicles (EVs) have attracted much attention in recent years, and installation of charging stations is an important issue for EVs. Hence, we focus on the joint optimization of the location of charging stations and the routing of EVs. When routing problems are formulated in the form of quadratic unconstrained binary optimization (QUBO), specialized solvers such as quantum annealers are expected to provide optimal solutions with high speed and accuracy. However, battery capacity constraints make it hard to formulate into QUBO form without a large number of auxiliary qubits. Here, we propose a sequential optimization method utilizing the Bayesian inference and QUBO solvers, in which the battery capacity constraints are automatically learned. This method enables us to optimize the number and location of charging stations and the routing of EVs with a small number of searches. Applying this method to a routing problem of 20 locations, we observed consistent convergence toward battery-feasible solutions across independent runs, demonstrating stable learning behavior of the proposed framework. Small-scale validation experiments using exhaustive enumeration show that the framework reliably discovers feasible configurations close to the global optimum, while runtime and QUBO-size analyses clarify its computational characteristics.