  We analyze randomized benchmarking for arbitrary gate-dependent noise and
prove that the exact impact of gate-dependent noise can be described by a
single perturbation term that decays exponentially with the sequence length.
That is, the exact behavior of randomized benchmarking under general
gate-dependent noise converges exponentially to a true exponential decay of
exactly the same form as that predicted by previous analysis for
gate-independent noise. Moreover, we show that the operational meaning of the
decay parameter for gate-dependent noise is essentially unchanged, that is, we
show that it quantifies the average fidelity of the noise between ideal gates.
We numerically demonstrate that our analysis is valid for strongly
gate-dependent noise models. We also show why alternative analyses do not
provide a rigorous justification for the empirical success of randomized
benchmarking with gate-dependent noise.
