  We present a protocol for Interleaved Randomized Benchmarking of arbitrary
quantum gates using Monte Carlo sampling of quantum states. It is generally
applicable, including non-Clifford gates while preserving key advantages of
Randomized Benchmarking such as error amplification as well as independence
from state preparation and measurement errors. This property is crucial for
implementations in many contemporary systems. Although the protocol scales
exponentially in the number of qubits, it is superior to direct Monte Carlo
sampling of the average gate fidelity in both the total number of experiments
by orders of magnitude and savings in classical preprocessing, that are
exponential.
