Direct Fidelity Estimation from Few Pauli Measurements

We describe a simple method for certifying that an experimental device
prepares a desired quantum state rho. Our method is applicable to any pure
state rho, and it provides an estimate of the fidelity between rho and the
actual (arbitrary) state in the lab, up to a constant additive error. The
method requires measuring only a constant number of Pauli expectation values,
selected at random according to an importance-weighting rule. Our method is
faster than full tomography by a factor of d, the dimension of the state space,
and extends easily and naturally to quantum channels.