Description
Electric Vehicle Charger Placement (EVCP) is an optimization problem that is sure to become of great interest in the upcoming years, given the increase in electric vehicles, and the costs associated with setting up an electric charger. However, this problem is non-deterministic polynomial time (NP) ard,
and becomes intractable with an increase in the number of charging stations to be placed.
Quantum Annealing on D-Wave Computers
Quantum annealing is a meta-heuristic for finding the global minima of an objective function. The quantum advantage stems from the ability to explore multiple candidate solutions in parallel, as well as the ability to quantum tunnel, overcoming energy walls between two local minima, allowing for easier traversal of the energy landscape. Using the D-Wave methodology, the problem is encoded as a Quadratic Unconstrained Binary Optimization (QUBO) problem, and quantum annealing is used to find the solution to this QUBO formulation.
The objective function f(x) in a QUBO problem is written in the form of
where, X is a vector of binary variables x, and qij are the weights of the N × N QUBO matrix. The weights can be written in the form of either a symmetric matrix or an upper triangular matrix that we call the N × N QUBO matrix. The result of the quantum annealing is the value of X that minimizes the objective function f(x). The challenge with Quantum annealing lies in finding the correct values of QUBO matrix to efficiently represent the problem that the authors are aiming to solve.
Read the complete paper: https://arxiv.org/pdf/2111.01622.pdf
