Hybrid benchmarking of arbitrary quantum gates. Abstract 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.