  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 manuscript 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
that purpose, our study focuses on the Variational Quantum 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 CVaR type cost functions improves
the optimization, increasing the probability of overlap with the optimal
solutions. However, these techniques also improve the performance of ansatz
based on product states (no entanglement), suggesting 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.
