# Optimal query complexity for estimating the trace of a matrix

arXiv: https://arxiv.org/abs/1405.7112 · HTML: https://mlsanity.com/paper/1405.7112/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2014.

## Built on by (most cited first, 6 of 6)

- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)
- [Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch](https://mlsanity.com/paper/2609.18577/) (2026)
- [Information Limits of Low-Rank Approximation Certification](https://mlsanity.com/paper/2610.03321/) (2026)

## Abstract (arXiv)

Given an implicit n× n matrix A with oracle access xTA x for any x∈ ℝ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 frac1ksumi=1k xiT A xi for xi∈ ℝ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/ε) queries to have a guarantee of variance at most ε. (2) We show that any estimator requires Omega(frac1ε2log frac1δ) queries to achieve a (1±ε)-multiplicative approximation guarantee with probability at least 1 - δ. 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.