Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles.
Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles.
复制标题
DOI：
10.1140/epjqt/s40507-021-00100-3
复制
发表时间：
2021
影响因子：
5.3
通讯作者：
Veshchezerova M
中科院分区：
文献类型：
--
作者：
Dalyac C;Henriet L;Jeandel E;Lechner W;Perdrix S;Porcheron M;Veshchezerova M
为了使量子算法有资格解决工业NP-Hard问题，有必要将它们与可用的多项式近似经典算法进行比较，而不仅仅是精确的指数算法。这是一个巨大的挑战，因为在许多情况下，根据一些高度可信的复杂性理论，存在可达近似比的界限。因此，这种资格的一个有趣的设置是关注这些问题的特定实例，已知这些问题比最坏情况的问题“不那么困难”，并且可以超越上述界限：量子算法的性能至少应该与传统的一样好。在这些实例上，直到非常大的尺寸。我们提出了一个案例研究这样一个协议的两个工业问题，从强劲发展的智能充电领域的电动汽车。量身定制的实现的量子近似优化算法（QAOA）已经开发了这两个问题，并通过仿真Pasqal的Rydberg原子为基础的量子设备或使用Atos量子学习机与经典资源进行了数值测试。在这两种情况下，量子算法都表现出与传统近似算法相同的近似比或对其进行了改进。这些都是非常令人鼓舞的结果，虽然仍然是有限的大小的情况下，所允许的经典计算资源的研究。下一步将是在更大的实例、实际设备以及更复杂的问题版本上确认它们。
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.
登录
查看更多内容
影响因子：
1
作者：
De Klerk, E;Pasechnik, DV;Warners, JP
通讯作者：
Warners, JP
影响因子：
2.2
作者：
Elloumi, Sourour;Lambert, Amelie
通讯作者：
Lambert, Amelie
影响因子：
2.5
作者：
Håstad, J
通讯作者：
Håstad, J
影响因子：
56.9
作者：
Choi, Jae-yoon;Hild, Sebastian;Gross, Christian
通讯作者：
Gross, Christian
影响因子：
2.9
作者：
Henriet, Loic
通讯作者：
Henriet, Loic