  We describe how randomized benchmarking can be used to reconstruct the unital
part of any trace-preserving quantum map, which in turn is sufficient for the
full characterization of any unitary evolution, or more generally, any unital
trace-preserving evolution. This approach inherits randomized benchmarking's
robustness to preparation, measurement, and gate imperfections, therefore
avoiding systematic errors caused by these imperfections. We also extend these
techniques to efficiently estimate the average fidelity of a quantum map to
unitary maps outside of the Clifford group. The unitaries we consider
correspond to large circuits commonly used as building blocks to achieve
scalable, universal, and fault-tolerant quantum computation. Hence, we can
efficiently verify all such subcomponents of a circuit-based universal quantum
computer. In addition, we rigorously bound the time and sampling complexities
of randomized benchmarking procedures, proving that the required non-linear
estimation problem can be solved efficiently.
