Why does Hutchinson's trace estimator reduce computation complexity? Given a matrix $A$, we want to compute its trace, in which we can use a trick name Hutchinson's trace estimator
\begin{align}
tr(A) = tr(A\mathbb{E}[\epsilon \epsilon^T])=\mathbb{E}[tr(A \epsilon \epsilon^T)]=\mathbb{E}[tr(\epsilon^T A \epsilon)]=\mathbb{E}[\epsilon^T A \epsilon],
\end{align}
where $\epsilon \sim \mathcal{N}(0,1)$ is a standard normal distribution. Then the trace of $A$ can be estimated using Monte Carlo sampling.
Some literature said, by transforming the computation into quadratic form, the computation complexity of the trace calculators can be reduced. I can't understand it. Why can such a stochastic quadratic way reduce the complexity of trace computation?

I have never heard of this trick before, and it does look strange ... since the trace is a sum of the $n$ diagonal terms, while the quadratic form needs a double sum over all the $n^2$ terms. So I guess the "trick" must be used only as one idea in combination with others, for some more involved problem than just a trace.
And indeed, in your own linked reference such examples are given, so just start top read those examples with attention. But I do not find the example in that link very well written, so better to go to the reference they give Randomized algorithms for matrices and data, but that paper does not mention the trick! Search gives a lot of relevant papers, and RANDOMIZED ALGORITHMS FOR ESTIMATING THE TRACE OF AN
IMPLICIT SYMMETRIC POSITIVE SEMI-DEFINITE MATRIX says, in its abstract that

these algorithms are useful in applications in which there is no explicit representation of $A$ but rather an efficient method to compute $z^T Az$ given $z$.

So this trick is not useful in isolation, but as a building block for randomized algorithms.
