  Quantum variational optimization has been posed as an alternative to solve
optimization problems faster and at a larger scale than what classical methods
allow. In this paper we study systematically the role of entanglement, the
structure of the variational quantum circuit, and the structure of the
optimization problem, in the success and efficiency of these algorithms. For
this purpose, our study focuses on the variational quantum eigensolver (VQE)
algorithm, as applied to quadratic unconstrained binary optimization (QUBO)
problems on random graphs with tunable density. Our numerical results indicate
an advantage in adapting the distribution of entangling gates to the problem's
topology, specially for problems defined on low-dimensional graphs.
Furthermore, we find evidence that applying conditional value at risk type cost
functions improves the optimization, increasing the probability of overlap with
the optimal solutions. However, these techniques also improve the performance
of Ans\"atze based on product states (no entanglement), suggesting that a new
classical optimization method based on these could outperform existing NISQ
architectures in certain regimes. Finally, our study also reveals a correlation
between the hardness of a problem and the Hamming distance between the ground-
and first-excited state, an idea that can be used to engineer benchmarks and
understand the performance bottlenecks of optimization methods.
