  Parameterized quantum circuits used as variational ans\"atze are emerging as
promising tools to tackle complex problems ranging from quantum chemistry to
combinatorial optimization. These variational quantum circuits can suffer from
the well-known curse of barren plateaus, which is characterized by an
exponential vanishing of the cost-function gradient with the system size,
making training unfeasible for practical applications. Since a generic quantum
circuit cannot be simulated efficiently, the determination of its trainability
is an important problem. Here we find an efficient method to compute the
gradient of the cost function and its variance for a wide class of variational
quantum circuits. Our scheme relies on our proof of an exact mapping from
randomly initialized circuits to a set of Clifford circuits that can be
efficiently simulated on a classical computer by virtue of the celebrated
Gottesmann-Knill theorem. This method is scalable and can be used to certify
trainability for variational quantum circuits and explore design strategies
that can overcome the barren plateau problem. As illustrative examples, we show
results with up to 100 qubits.
