Improved variational algorithms for optimization problems in a quantum computer

Recent advances in Noisy Intermediate-Scale Quantum (NISQ) computers allow us to solve combinatorial optimization problems encoded in Hamiltonians via hybrid quantum/classical variational algorithms. Current approaches minimize the expectation of the problem Hamiltonian for a parameterized trial state generated in the quantum circuit. The expectation is obtained by sampling the full outcome of an ensemble of measurements of the corresponding matrix element, while the trial wavefunction parameters are optimized classically. This procedure is fully justified for quantum mechanical observables (i.e. molecular energy). However, in the case of the simulation of classical optimization problems, which yield diagonal Hamiltonians, we argue that it is more natural to aggregate the samples using a different aggregation function than the expected value. In this talk, we present results of the aforementioned scheme for a plethora of interesting optimization problems where we demonstrate faster convergence towards more accurate solutions.