Let $A$ be a real symmetric matrix of size $N$ such that the number of non-zero entries in each row is polylogarithmic in $N$ and the positions and the values of these entries are specified by an efficiently computable function. We consider the problem of estimating an arbitrary diagonal entry $(A^m)_{jj}$ of the matrix $A^m$ up to an error of $\epsilon\, b^m$, where $b$ is an a priori given upper bound on the norm of $A$ and $m$ and $\epsilon$ are polylogarithmic and inverse polylogarithmic in $N$, respectively.

We show that this problem is PromiseBQP-complete. It can be solved efficiently on a quantum computer by repeatedly applying measurements of $A$ to the $j$th basis vector and raising the outcome to the $m$th power. Conversely, every uniform quantum circuit of polynomial length can be encoded into a sparse matrix such that some basis vector $|j\rangle$ corresponding to the input induces two different spectral measures depending on whether the input is accepted or not. These measures can be distinguished by estimating the $m$th statistical moment for some appropriately chosen $m$, i.e., by the $j$th diagonal entry of $A^m$. The problem remains PromiseBQP-hard when restricted to matrices having only $-1$, $0$, and $1$ as entries. Estimating off-diagonal entries is also PromiseBQP-complete.