Improved stochastic trace estimation using mutually unbiased bases

J. K. Fitzsimons, M. A. Osborne, S. J. Roberts +1

We examine the problem of estimating the trace of a matrix $A$ when given access to an oracle which computes $x^{†}Ax$ for an input vector $x$. We make use of the basis vecto…