Ricard Puig

Variational quantum algorithms are limited in practice by the barren plateau (BP) problem, where cost function gradients vanish exponentially with system size. We show that Quantum Signal Processing (QSP) provides a structured variational ansatz that is provably BP-free in a region around the all-zero initialization, for a broad class of observables with eigenvalues bounded away from zero. The BP-free region is an ellipsoid in parameter space characterized precisely via the connection to symmetric QSP and the energy landscape results of Wang, Dong, and Lin (arXiv:2110.04993v2). Contrary to the conjecture of Cerezo et al. (arXiv:2312.09121v2) that BP-free cost functions are classically simulable, we show that the cost functions of general QSP ansatze are classically hard. Finally, we show that the optimization over QSP phases can be reduced to a convex quadratic program over Chebyshev coefficients, solvable classically using measurements on unparametrized quantum circuits. These results establish QSP as a theoretically principled variational ansatz that is simultaneously trainable, classically hard, and efficiently optimizable, opening near-term applications in quantum simulation and sensing.