  A crucial task to obtain optimal and reliable quantum devices is to quantify
their overall performance. The average fidelity of quantum gates is a
particular figure of merit that can be estimated efficiently by Randomized
Benchmarking (RB). However, the concept of gate-fidelity itself relies on the
crucial assumption that noise behaves in a predictable, time-local, or
so-called Markovian manner, whose breakdown can naturally become the leading
source of errors as quantum devices scale in size and depth. We analytically
show that error suppression techniques such as Dynamical Decoupling (DD) and
Randomized Compiling (RC) can operationally Markovianize RB: i) fast DD reduces
non-Markovian RB to an exponential decay plus longer-time corrections, while on
the other hand, ii) RC generally does not affect the average, but iii) it
always suppresses the variance of such RB outputs. We demonstrate these effects
numerically with a qubit noise model. Our results show that simple and
efficient error suppression methods can simultaneously tame non-Markovian noise
and allow for standard and reliable gate quality estimation, a fundamentally
important task in the path toward fully functional quantum devices.
