Parallel Variational Quantum Algorithms With Gradient-Informed Restart to Speed Up Optimization in the Presence of Barren Plateaus

Abstract

Inspired by the Fleming–Viot stochastic process, we propose a parallel implementation with restart of variational quantum algorithms, with the aim of reducing the time spent by the algorithm in barren plateaus where the optimization direction is unclear. In the Fleming–Viot tradition, parallel searches are called particles. In the proposed approach, the search by a Fleming–Viot particle is stopped when it encounters a region where the gradient is too small or noisy, suggesting a barren plateau area. The stopped particle continues the search after being restarted at another location in the parameter space, potentially taking the exploration away from barren plateaus. We first analyze the behavior of the Fleming–Viot particles from a theoretical standpoint. We show that, when simulated-annealing optimization algorithms are used to drive the particle dynamics, the Fleming–Viot system is expected to find the global optimum faster than a single simulated-annealing instance. Furthermore, the relative efficiency increases proportionally to the percentage of barren plateaus in the domain. This result is corroborated by numerical experiments carried out on nonconvex 2-D synthetic problems, as well as on quantum approximated Max-Cut instances, both in a lower 2-D and a higher 16-D problem. The experiments show that our method tends to perform better than vanilla and parallel simulated annealing when large barren plateaus are present in the domain, especially in the higher dimensional problem where barrenness tends to be more important.