  Randomized benchmarking is a widely used experimental technique to
characterize the average error of quantum operations. Benchmarking procedures
that scale to enable characterization of $n$-qubit circuits rely on efficient
procedures for manipulating those circuits and, as such, have been limited to
subgroups of the Clifford group. However, universal quantum computers require
additional, non-Clifford gates to approximate arbitrary unitary
transformations. We define a scalable randomized benchmarking procedure over
$n$-qubit unitary matrices that correspond to protected non-Clifford gates for
a class of stabilizer codes. We present efficient methods for representing and
composing group elements, sampling them uniformly, and synthesizing
corresponding $\mathrm{poly}(n)$-sized circuits. The procedure provides
experimental access to two independent parameters that together characterize
the average gate fidelity of a group element.
