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

Understand

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.