Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles
arXiv:2012.14859 · doi:10.1140/epjqt/s40507-021-00100-3
Abstract
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.
References in corpus (17)
- Quantum Computing in the NISQ era and beyond
- Quantum information with Rydberg atoms
- QuTiP 2: A Python framework for the dynamics of open quantum systems
- Strengths and Weaknesses of Quantum Computing
- Exploring the many-body localization transition in two dimensions
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
- Quantum computing with atomic qubits and Rydberg interactions: Progress and challenges
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
- Practical optimization for hybrid quantum-classical algorithms
- Hybrid quantum-classical algorithms for approximate graph coloring
- Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
- For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
- Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks
- Constrained quantum annealing of graph coloring
- Robustness to spontaneous emission of a variational quantum algorithm