  We derive an algebraic framework which identifies the minimal information
required to assess how well a quantum device implements a desired quantum
operation. Our approach is based on characterizing only the unitary part of an
open system's evolution. We show that a reduced set of input states is
sufficient to estimate the average fidelity of a quantum gate, avoiding a
sampling over the full Liouville space. Surprisingly, the minimal set consists
of only two input states, independent of the Hilbert space dimension. The
minimal set is, however, impractical for device characterization since one of
the states is a totally mixed thermal state and extracting bounds for the
average fidelity is impossible. We therefore present two further reduced sets
of input states that allow, respectively, for numerical and analytical bounds
on the average fidelity.
