  Given an implicit $n\times n$ matrix $A$ with oracle access $x^TA x$ for any
$x\in \mathbb{R}^n$, we study the query complexity of randomized algorithms for
estimating the trace of the matrix. This problem has many applications in
quantum physics, machine learning, and pattern matching. Two metrics are
commonly used for evaluating the estimators: i) variance; ii) a high
probability multiplicative-approximation guarantee. Almost all the known
estimators are of the form $\frac{1}{k}\sum_{i=1}^k x_i^T A x_i$ for $x_i\in
\mathbb{R}^n$ being i.i.d. for some special distribution.
  Our main results are summarized as follows. We give an exact characterization
of the minimum variance unbiased estimator in the broad class of linear
nonadaptive estimators (which subsumes all the existing known estimators). We
also consider the query complexity lower bounds for any (possibly nonlinear and
adaptive) estimators: (1) We show that any estimator requires
$\Omega(1/\epsilon)$ queries to have a guarantee of variance at most
$\epsilon$. (2) We show that any estimator requires
$\Omega(\frac{1}{\epsilon^2}\log \frac{1}{\delta})$ queries to achieve a
$(1\pm\epsilon)$-multiplicative approximation guarantee with probability at
least $1 - \delta$. Both above lower bounds are asymptotically tight.
  As a corollary, we also resolve a conjecture in the seminal work of Avron and
Toledo (Journal of the ACM 2011) regarding the sample complexity of the
Gaussian Estimator.
