Does absence of barren plateaus imply classical simulability?
This text mentions work from 2024 on. Those parts were partly written without a live literature search and have not been checked by an editor yet.
In plain words
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 statement
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.
What would settle it
A general simulation theorem under the polynomial-gradient-variance assumption, or a counterexample family with a complexity-theoretic hardness proof.
Results
No results have been posted on this problem yet.
Post a result · how results are checked
Sign in to follow or save this problem
Comments (0)
Comments are not records: they are not signed, stamped or logged. How comments work
No comments yet.
Sign in to comment.