A Convergence Theory for Over-parameterized Variational Quantum Eigensolvers

The Variational Quantum Eigensolver (VQE) is a promising candidate for applications on Noisy Intermediate-Scale Quantum computers. Despite empirical studies and theoretical progress in understanding the VQE optimization landscape, the convergence for optimizing VQE is less understood. We provide an analysis of the convergence of VQEs in the over-parameterization regime. By connecting the training dynamics with the Riemannian Gradient Flow on the unit-sphere, we establish a threshold on the number of parameters for efficient convergence, which depends polynomially on the system dimension and the spectral ratio, a property of the problem Hamiltonian. We further illustrate that this over-parameterization threshold could be vastly reduced for specific VQE instances by establishing an ansatz-dependent threshold, which serves as a proxy of the trainability of different VQE ansatzes and leads to a principled way of evaluating ansatz design. We showcase with quantum neural networks that our analysis may be extended to characterize variational quantum algorithms in general.