Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles
| Autor: | Simon Perdrix, Wolfgang Lechner, Marc Porcheron, Emmanuel Jeandel, Loïc Henriet, Margarita Veshchezerova, Constantin Dalyac |
|---|---|
| Přispěvatelé: | Pasqal, Information Quantique [LIP6] (QI), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Designing the Future of Computational Models (MOCQUA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Universität Innsbruck [Innsbruck], Parity Quantum Computing (ParityQC), EDF R&D (EDF R&D), EDF (EDF), Perdrix, Simon, Leopold Franzens Universität Innsbruck - University of Innsbruck, EDF Labs, INSA Lyon, Sciencesconf.org, CCSD |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Mathematical optimization Polynomial Optimization problem [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO] Field (physics) Computer science [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] FOS: Physical sciences [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences 010305 fluids & plasmas [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph] [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 0103 physical sciences Electrical and Electronic Engineering 010306 general physics Quantum ComputingMilieux_MISCELLANEOUS [PHYS.QPHY] Physics [physics]/Quantum Physics [quant-ph] Quantum Physics Emulation Scheduling Research Approximation algorithm [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Condensed Matter Physics Atomic and Molecular Physics and Optics [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] Graphes Control and Systems Engineering Rydberg atom Heuristique quantique Quantum algorithm [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] Quantum Physics (quant-ph) Informatique Quantique Optimisation combinatoire |
| Zdroj: | ROADEF 2022-23ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision ROADEF 2022-23ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, INSA Lyon, Feb 2022, Villeurbanne-Lyon, France EPJ Quantum Technology Epj Quantum Technology |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|