Bittel Lennart, Kliesch Martin
Quantum Technology Group, Heinrich Heine University Düsseldorf, 40225 Düsseldorf, Germany.
Phys Rev Lett. 2021 Sep 17;127(12):120502. doi: 10.1103/PhysRevLett.127.120502.
Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.
变分量子算法被提出来用于解决近期量子设备上的相关计算问题。流行的版本是变分量子特征求解器和量子近似优化算法，它们分别解决量子化学中的基态问题和二元优化问题。它们基于使用经典计算机训练参数化量子电路的思想。我们证明了相应的经典优化问题是NP难的。此外，这种难是稳健的，即对于每一个多项式时间算法，存在这样的实例，假设P≠NP，由经典优化问题产生的相对误差可以任意大。即使对于仅由对数多个量子比特或自由费米子组成的经典可处理系统，我们也证明优化是NP难的。这阐明了经典优化本质上是困难的，而不仅仅是从基态问题继承了这种困难。我们的分析表明，训练景观可能有许多远离最优的持久局部最小值。这意味着梯度和高阶下降算法通常会收敛到远离最优的解。
