Quantum variational optimization: The role of entanglement and problem hardness

12 pags., 10 figs., 1 tab.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ätze 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.Work funded by CAM/FEDER project No. S2018/TCS-4342 (QUITEMAD-CM), Spanish project PGC2018-094792-B-I00 (MCIU/AEI/FEDER, UE), and CSIC Quantum Technology Platform PT-001. We acknowledge Santander Supercomputacion support group at the University of Cantabria who provided access to the supercomputer Altamira Supercomputer at the Institute of Physics of Cantabria (IFCA-CSIC), member of the Spanish Supercomputing Network, for performing simulations