Cost function dependent barren plateaus in shallow parametrized quantum circuits

Variational quantum algorithms (VQAs) optimize the parameters θ of a parametrized quantum circuit V ( θ ) to minimize a cost function C . While VQAs may enable practical applications of noisy quantum computers, they are nevertheless heuristic methods with unproven scaling. Here, we rigorously prove two results, assuming V ( θ ) is an alternating layered ansatz composed of blocks forming local 2-designs. Our first result states that defining C in...