Training Variational Quantum Algorithms Is NP-Hard.

By Lennart Bittel, Martin Kliesch. Physical Review Letters, 2021

422 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/824acc137818b660df67ac43b66cec16958cd8b9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Barren plateaus in variational quantum computing (2024, neutral): “Throughout the paper, we have added boxes that include important details and more technical discussions.”
Diagnosing Barren Plateaus with Tools from Quantum Optimal Control (2021, background): “For instance, it has been shown that the optimization task associated with minimizing the VQA cost function is in general an NPhard non-convex optimization problem [31].”
Challenges and opportunities in quantum machine learning (2022, background): “Ultimately, this can lead to the over-all non-convex optimization being NP-hard [72], which is again similar to the classical case.”