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 little to no attention in the machine learning and statistics literature. We demonstrate their usefulness by using them to create a new sampling technique which offers an improvement on the previously well established bounds of stochastic trace estimation. This approach offers a new state of the art single shot sampling variance while requiring O(log(n)) random bits for x $\in$Rn which significantly improves on traditional methods such as fixed basis methods, 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 little to no attention in the machine learning and statistics literature. We demonstrate their usefulness by using them to create a new sampling technique which offers an improvement on the previously well established bounds of stochastic trace estimation. This approach offers a new state of the art single shot sampling variance while requiring O(log(n)) random bits for x $\in$Rn which significantly improves on traditional methods such as fixed basis methods, 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 little to no attention in the machine learning and statistics literature. We demonstrate their usefulness by using them to create a new sampling technique which offers an improvement on the previously well established bounds of stochastic trace estimation. This approach offers a new state of the art single shot sampling variance while requiring O(log(n)) random bits for x $\in$Rn which significantly improves on traditional methods such as fixed basis methods, 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