  Variational quantum algorithms (VQAs) are proposed to solve relevant
computational problems on near term quantum devices. Popular versions are
variational quantum eigensolvers (VQEs) and quantum approximate optimization
algorithms (QAOAs) that solve ground state problems from quantum chemistry and
binary optimization problems, respectively. They are based on the idea to use 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
exists instances for which the relative error resulting from the classical
optimization problem can be arbitrarily large, unless P = NP. Even for
classically tractable systems, composed of only logarithmically many qubits or
free fermions, we show that the optimization is 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 decent algorithms will generally converge to
far from optimal solutions.
