Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles
Pasqal, 2 avenue Augustin Fresnel, 91120, Palaiseau, France
2 LIP6, CNRS, Sorbonne Université, 4 Place Jussieu, 75005, Paris, France
3 Mocqua, LORIA, CNRS, Université de Lorraine, Inria, Inria Mocqua, F 54000, Nancy, France
4 University of Innsbruck, Technikerstrasse 21a, Innsbruck, Austria
5 Parity Quantum Computing GmbH, Rennweg 1, Innsbruck, Austria
6 EDF R&D, 7, boulevard Gaspard Monge, 91120, Palaiseau, France
Accepted: 29 April 2021
Published online: 17 May 2021
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 Author(s) 2021
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.