  We show that the minimum experimental effort to characterize the proper
functioning of a quantum device scales as 2^n for n qubits and requires
classical computational resources ~ n^2 2^{3n}. This represents an exponential
reduction compared to the best currently available protocol, Monte Carlo
characterization. The reduction comes at the price of either having to prepare
entangled input states or obtaining bounds rather than the average fidelity
itself. It is achieved by applying Monte Carlo sampling to so-called
two-designs or two classical fidelities. For the specific case of Clifford
gates, the original version of Monte Carlo characterization based on the
channel-state isomorphism remains an optimal choice. We provide a
classification of the available efficient strategies for device
characterization in terms of the number of required experimental settings,
average number of actual measurements and classical computational resources.
