  Variational quantum algorithms (VQAs) hold much promise but face the
challenge of exponentially small gradients. Unmitigated, this barren plateau
(BP) phenomenon leads to an exponential training overhead for VQAs. Perhaps the
most pernicious are noise-induced barren plateaus (NIBPs), a type of
unavoidable BP arising from open system effects, which have so far been shown
to exist for unital noise maps. Here, we generalize the study of NIBPs to more
general completely positive, trace-preserving maps, establishing the existence
of NIBPs in the unital case and a class of non-unital maps we call
Hilbert-Schmidt (HS)-contractive. The latter includes amplitude damping. We
identify the associated phenomenon of noise-induced limit sets (NILS) of the
VQA cost function and prove its existence for both unital and HS-contractive
non-unital noise maps. Along the way, we extend the parameter shift rule of
VQAs to the noisy setting. We provide rigorous bounds in terms of the relevant
variables that give rise to NIBPs and NILSs, along with numerical simulations
of the depolarizing and amplitude-damping maps that illustrate our analytical
results.
