# Improved stochastic trace estimation using mutually unbiased bases

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jul 2016.

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

- [A Unifying Generative Model for Graph Learning Algorithms: Label Propagation, Graph Convolutions, and Combinations](https://mlsanity.com/paper/2101.07730/) (2021)
- [Variance Reduction for Matrix Computations with Applications to Gaussian Processes](https://mlsanity.com/paper/2106.14565/) (2021)

## Abstract (arXiv)

We examine the problem of estimating the trace of a matrix A when given access to an oracle which computes x^dagger A x for an input vector x. We make use of the basis vectors from a set of mutually unbiased bases, widely studied in the field of quantum information processing, in the selection of probing vectors x. This approach offers a new state of the art single shot sampling variance while requiring only O(log(n)) random bits to generate each vector. This significantly improves on traditional methods such as Hutchinson's and Gaussian estimators in terms of the number of random bits required and worst case sample variance.