The power of random measurements: measuring Tr(\rho^n) on single copies of \rho

While it is known that Tr(\rho^n) can be measured directly (i.e., without first reconstructing the density matrix) by performing joint measurements on n copies of the same state rho, it is shown here that random measurements on single copies suffice, too. Averaging over the random measurements directly yields estimates of Tr(\rho^n), even when it is not known what measurements were actually performed (so that one cannot reconstruct \rho).