  We study the problem of estimating the trace of a matrix $\mathbf{A}$ that
can only be accessed through Kronecker-matrix-vector products. That is, for any
Kronecker-structured vector $\boldsymbol{\mathrm{x}} = \otimes_{i=1}^k
\boldsymbol{\mathrm{x}}_i$, we can compute $\mathbf{A}\boldsymbol{\mathrm{x}}$.
We focus on the natural generalization of Hutchinson's Estimator to this
setting, proving tight rates for the number of matrix-vector products this
estimator needs to find a $(1\pm\varepsilon)$ approximation to the trace of
$\mathbf{A}$.
  We find an exact equation for the variance of the estimator when using a
Kronecker of Gaussian vectors, revealing an intimate relationship between
Hutchinson's Estimator, the partial trace operator, and the partial transpose
operator. Using this equation, we show that when using real vectors, in the
worst case, this estimator needs $O(\frac{3^k}{\varepsilon^2})$ products to
recover a $(1\pm\varepsilon)$ approximation of the trace of any PSD
$\mathbf{A}$, and a matching lower bound for certain PSD $\mathbf{A}$. However,
when using complex vectors, this can be exponentially improved to
$\Theta(\frac{2^k}{\varepsilon^2})$. We show that Hutchinson's Estimator
converges slowest when $\mathbf{A}$ itself also has Kronecker structure. We
conclude with some theoretical evidence suggesting that, by combining
Hutchinson's Estimator with other techniques, it may be possible to avoid the
exponential dependence on $k$.
