Training Variational Quantum Algorithms Is NP-Hard
Training Variational Quantum Algorithms Is NP-Hard
复制标题
DOI：
10.1103/physrevlett.127.120502
复制
发表时间：
2021-09-17
影响因子：
8.6
通讯作者：
Kliesch, Martin
中科院分区：
文献类型：
--
作者：
Bittel, Lennart;Kliesch, Martin
提出了变分量子算法来解决近期量子器件上的相关计算问题。流行的版本是变分量子本征解算法和量子近似优化算法，分别解决量子化学中的基态问题和二元优化问题。它们是基于使用经典计算机来训练参数化量子电路的想法。我们证明了相应的经典优化问题是NP-难的。此外，在假设P不等于NP的情况下，对于每个多项式时间算法，经典优化问题产生的相对误差可以是任意大的实例，从这个意义上讲，难度是健壮的。即使对于仅由对数个量子比特或自由费米子组成的经典易处理系统，我们也证明了优化是NP-难的。这说明经典最优化本质上是困难的，而不仅仅是继承了基态问题的困难。我们的分析表明，训练场景可能存在许多远离最优的持久局部极小值，这意味着梯度算法和高阶下降算法通常会收敛到远离最优解。
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 not equal 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.