Improved Stochastic Trace Estimation using Mutually Unbiased Bases

JK Fitzsimons, MA Osborne, SJ Roberts, JF Fitzsimons
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:309-317, 2018.

Abstract

The paper begins by introducing the definition and construction of mutually unbiased bases, which are a widely used concept in quantum information processing but have received lit- tle to no attention in the machine learning and statistics literature. We demonstrate their use- fulness by using them to create a new sampling technique which offers an improvement on the previously well established bounds of stochas- tic trace estimation. This approach offers a new state of the art single shot sampling vari- ance while requiring O(log(n)) random bits for x $\in$Rn which significantly improves on traditional methods such as fixed basis meth- ods, Hutchinson’s and Gaussian estimators in terms of the number of random bits required and worst case sample variance.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-fitzsimons18a, title = {Improved Stochastic Trace Estimation using Mutually Unbiased Bases}, author = {Fitzsimons, JK and Osborne, MA and Roberts, SJ and Fitzsimons, JF}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {309--317}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/fitzsimons18a/fitzsimons18a.pdf}, url = {https://proceedings.mlr.press/r16/fitzsimons18a.html}, abstract = {The paper begins by introducing the definition and construction of mutually unbiased bases, which are a widely used concept in quantum information processing but have received lit- tle to no attention in the machine learning and statistics literature. We demonstrate their use- fulness by using them to create a new sampling technique which offers an improvement on the previously well established bounds of stochas- tic trace estimation. This approach offers a new state of the art single shot sampling vari- ance while requiring O(log(n)) random bits for x $\in$Rn which significantly improves on traditional methods such as fixed basis meth- ods, Hutchinson’s and Gaussian estimators in terms of the number of random bits required and worst case sample variance.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Improved Stochastic Trace Estimation using Mutually Unbiased Bases %A JK Fitzsimons %A MA Osborne %A SJ Roberts %A JF Fitzsimons %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-fitzsimons18a %I PMLR %P 309--317 %U https://proceedings.mlr.press/r16/fitzsimons18a.html %V R16 %X The paper begins by introducing the definition and construction of mutually unbiased bases, which are a widely used concept in quantum information processing but have received lit- tle to no attention in the machine learning and statistics literature. We demonstrate their use- fulness by using them to create a new sampling technique which offers an improvement on the previously well established bounds of stochas- tic trace estimation. This approach offers a new state of the art single shot sampling vari- ance while requiring O(log(n)) random bits for x $\in$Rn which significantly improves on traditional methods such as fixed basis meth- ods, Hutchinson’s and Gaussian estimators in terms of the number of random bits required and worst case sample variance. %Z Reissued by PMLR on 04 October 2026.
APA
Fitzsimons, J., Osborne, M., Roberts, S. & Fitzsimons, J.. (2018). Improved Stochastic Trace Estimation using Mutually Unbiased Bases. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:309-317 Available from https://proceedings.mlr.press/r16/fitzsimons18a.html. Reissued by PMLR on 04 October 2026.

Related Material