  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.
