Abstract
Interactions between electrons and phonons play a crucial role in quantum materials. Yet, there is no universal method that would simultaneously accurately account for strong electron-phonon interactions and electronic correlations. By combining methods of the variational quantum eigensolver and the variational non-Gaussian solver, we develop a hybrid quantum-classical algorithm suitable for this type of correlated systems. This hybrid method tackles systems with arbitrarily strong electron-phonon coupling without increasing the number of required qubits and quantum gates, as compared to purely electronic models. We benchmark the new method by applying it to the paradigmatic Hubbard-Holstein model at half filling, and show that it correctly captures the competition between charge density wave and antiferromagnetic phases, quantitatively consistent with exact diagonalization.