= Solution
Prepare the auxiliary system in the <maximally mixed state> $\rho=I/N$. Then $\operatorname{Tr}(\rho U)=\operatorname{Tr}U/N$, so the two measurement bases give
$$
\boxed{\widehat{\operatorname{Tr}U}=N\bigl[(\widehat P_0-\widehat P_1)+i(\widehat P_--\widehat P_+)\bigr].}
$$
There 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 $\varepsilon$ in the unnormalized <trace> requires normalized accuracy $\varepsilon/N$; straightforward independent frequency sampling consequently uses order $N^2/\varepsilon^2$ runs at fixed confidence. Thus the construction should not be confused with a dimension-independent guarantee for arbitrary absolute trace precision.
Back to article page
