  Variational quantum algorithms are proposed to solve relevant computational
problems on near term quantum devices. Popular versions are variational quantum
eigensolvers and quantum ap- proximate 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 parameterized 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 P $\neq$ 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 that gradient and higher order
descent algorithms will generally converge to far from optimal solutions.
