Abstract

Variational quantum algorithms (VQAs) optimize the parameters $\vecθ$ of a parametrized quantum circuit $V(\vecθ)$ 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(\vecθ)$ 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(\vecθ)$ 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(\vecθ)$ is $\mathcal{O}(\log n)$. 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.