Revision 1

Superseded · first revision · record

Title: Does absence of barren plateaus imply classical simulability
Plain: Variational quantum algorithms tune circuit settings to lower a cost, but most become untrainable because the cost changes exponentially little as the settings vary (a barren plateau). It is conjectured that every circuit family provably free of this flatness can also be imitated by a classical computer, which would remove the point of using it.
Precise: For parametrized circuits with loss $L(\theta) = \operatorname{Tr}[O U(\theta) \rho U(\theta)^{\mathrm{dag}}]$ whose gradient variance provably decays at most polynomially in qubit number $n$, is there always a classical algorithm that, after collecting $\operatorname{poly}(n)$ measurement data from a quantum device once, estimates $L(\theta)$ to $1/\operatorname{poly}(n)$ for any $\theta$ in $\operatorname{poly}(n)$ time? Cerezo et al. (arXiv:2312.09121, Nat. Commun. 16, 7907, 2025) argue yes for known families. An answer is a proof, or a barren-plateau-free family with a hardness proof.
Settled by: A general simulation theorem under the polynomial-gradient-variance assumption, or a counterexample family with a complexity-theoretic hardness proof.
Kind: well-posed
Answer type: yes-no
References: (empty)
Literature status: open
Status note: (empty)
Posed since: 2023