  One of the crucial steps in building a scalable quantum computer is to
identify the noise sources which lead to errors in the process of quantum
evolution. Different implementations come with multiple hardware-dependent
sources of noise and decoherence making the problem of their detection
manyfoldly more complex. We develop a randomized benchmarking algorithm which
uses Weyl unitaries to efficiently identify and learn a mixture of error models
which occur during the computation. We provide an efficiently computable
estimate of the overhead required to compute expectation values on outputs of
the noisy circuit relying only on locality of the interactions and no further
assumptions on the circuit structure. The overhead decreases with the noise
rate and this enables us to compute analytic noise bounds that imply efficient
classical simulability. We apply our methods to ansatz circuits that appear in
the Variational Quantum Eigensolver and establish an upper bound on classical
simulation complexity as a function of noise, identifying regimes when they
become classically efficiently simulatable.
