An iterative variational algorithm for optimization on near-term quantum devices

Hybrid quantum-classical optimization algorithms have recently attracted interest for applications in the noisy intermediate-scale quantum devices (NISQ) era of quantum computing. However, as it has been recently shown by Jarrod McClean et. al. (arXiv:1803.11173v1), many such algorithms could suffer from the issue of Barren Plateaus even at shallow depth circuits, which corresponds to the phenomenon of vanishing of gradients in training classical deep neural networks. Here we introduce a variational method which restricts the entropy of the batch Hamiltonian per circuit complexity and propose an algorithm that attempts to avoid this issue by iteratively recombining the solutions while approaching an optimal solution. Finally we compare the performance of our algorithm with existing variational and quantum approximate optimization algorithms.