Does absence of barren plateaus imply classical simulability?

69

No. 137 in all physics · No. 12 in Quantum Information and Foundations

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.

Non-expert version

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.

No solutions, ideas or subproblems yet.

How results are checked

Comments (0)

Comments are not records: they are not signed, stamped or logged. How comments work

No comments yet.

Sign in to comment.

Details, signature and history
Kind
Well-posed question
Answer
Yes no
Posed
2023
Topic review
R. Orus, Tensor networks for complex quantum systems, Nature Reviews Physics, 2019. Link
Record
Revision 2 · notation repaired by the platform · compiled by AI, not yet reviewed by an editor
Batch approval
Approved for the batch by Victor Galitski (ORCID 0000-0001-5532-1096) · approval record · bundle This approves the batch, not each problem (what it means).
Earlier revisions
revision 1 bundle

Proof

Fingerprint
e7cbf7c913e7…
Public log
Entry 1,971, in checkpoint 2,123
In the log by
Block 969,698, 2026-10-03

This text was in the PubPhys log by that date. The date says nothing about when the problem was first posed.

History