Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 53 / 1 / 3 / Solution

Prepare the auxiliary system in the maximally mixed state $\rho =I/N$. Then $\mathrm{Tr}(\rho U)=\mathrm{Tr}U/N$, so the two measurement bases giveThere is no need to know the eigenvectors of $U$. Choose a uniformly random member of any known orthonormal basis on each run; discarding the classical preparation label produces $I/N$. Alternatively, discard one half of a maximally entangled pair of $N$-level systems. This is trace estimation by a maximally mixed Hadamard test.

The circuit directly estimates the normalized trace. To demand fixed absolute accuracy $\epsilon$ in the unnormalized trace requires normalized accuracy $\epsilon /N$; straightforward independent frequency sampling consequently uses order $N^2/{\epsilon }^2$ runs at fixed confidence. Thus the construction should not be confused with a dimension-independent guarantee for arbitrary absolute trace precision.