Polynomially Trainable Variational Quantum Circuits with BQP-Hard Costs

Understanding when parameterized quantum circuits can be both trainable and computationally advantageous is an important challenge in assessing the potential of variational quantum algorithms. Avoiding exponentially vanishing gradients is essential for scalable optimization, but a trainable landscape is of limited computational interest if its cost function can also be efficiently evaluated classically. Of particular interest is the intermediate regime beyond the immediate neighborhood of Clifford circuits, where inverse-polynomial gradients and the breakdown of known efficient classical approximations had previously been observed numerically, but their coexistence had not been proved. In this work, we establish this phenomenon rigorously under the standard assumption that $\mathsf{BQP}⊈\mathsf{BPP}$. Our results provide a theoretical basis for seeking computationally useful trainable quantum models.