Cost function dependent barren plateaus in shallow parametrized quantum circuits

Abstract 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 terms of global observables leads to exponentially vanishing gradients (i.e., barren plateaus) even when V ( θ ) is shallow. Hence, several VQAs in the literature must revise their proposed costs. On the other hand, our second result states that defining C with local observables leads to at worst a polynomially vanishing gradient, so long as the depth of V ( θ ) is $${\mathcal{O}}(\mathrm{log}\,n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>log</mml:mi> <mml:mspace/> <mml:mi>n</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Our results establish a connection between locality and trainability. We illustrate these ideas with large-scale simulations, up to 100 qubits, of a quantum autoencoder implementation.