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?

You are right that for calculating the trace of a matrix this does not reduce cost vs a simple calculation...but this trick is very useful when we need to compute the trace of a function of a matrix, $tr(f(A))$.
For example, consider estimating a log determinant, which can be rewritten as $tr( log(A) )$, the trace of the log of the matrix; or consider (the closely related!) calculation where we need the trace of a matrix raised to a power, e.g. $tr(A^k)$. If you are calculating the trace of a function of a matrix, Hutchison's trace estimator may dramatically reduce your computational cost.
If you are trying to calculate $tr(A^2)$, for example, where A is some square $D x D$ matrix, you could calculate $AA$ and then take the trace of this -- this costs $O(D^3)$, for a large matrix this will be quite expensive, or you could use Hutchison's trace estimator to replace that series of matrix multiplications with a series of matrix-vector multiplications which will be substantially cheaper, as long as the number $M$ of probe vectors that you use is $M << D$.
Another use case is when forming the matrix $A$ explicitly would be very expensive but taking a matrix vector product would be much cheaper. For example, consider if we have a matrix formed from $XX^T$, where $X$ is some $N x M$ matrix and $N$ is very large, so that $A$ would be too large to fit in memory. In this case, if you need to evaluate $tr(A)$, it might be much cheaper to use matrix-vector products rather than forming $A$ explicitly.
Basically, the trick helps us reduce the cost of trace estimation when we want to estimate the trace of a function of a matrix or when we are working with matrices that we do not want to for explicitly. Estimating log determinants is a common use case -- this paper uses Hutchison's trace estimator in their approach for approximating log determinants for example:
http://proceedings.mlr.press/v37/hana15.pdf
