# Multivariate trace estimation using quantum state space linear algebra

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 66 references that are in the map.
- First posted on arXiv 2 May 2024.

## Builds on (most cited first, 12 of 12)

- [An Investigation into Neural Net Optimization via Hessian Eigenvalue Density](https://mlsanity.com/paper/1901.10159/) (2019)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning](https://mlsanity.com/paper/1910.06151/) (2019)
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://mlsanity.com/paper/1804.01973/) (2018)
- [A divide-and-conquer algorithm for quantum state preparation](https://mlsanity.com/paper/2008.01511/) (2020)
- [Analysis of stochastic Lanczos quadrature for spectrum approximation](https://mlsanity.com/paper/2105.06595/) (2021)
- [Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2011.04125/) (2020)
- [Backpropagation for Implicit Spectral Densities](https://mlsanity.com/paper/1806.00499/) (2018)
- [Quantum algorithms for spectral sums](https://mlsanity.com/paper/2011.06475/) (2020)
- [Multivariate trace estimation in constant quantum depth](https://mlsanity.com/paper/2206.15405/) (2022)

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

- [On Encoding Matrices using Quantum Circuits](https://mlsanity.com/paper/2510.20030/) (2025)
- [Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch](https://mlsanity.com/paper/2609.18577/) (2026)

## Abstract (arXiv)

In this paper, we present a quantum algorithm for approximating multivariate traces, i.e. the traces of matrix products. Our research is motivated by the extensive utility of multivariate traces in elucidating spectral characteristics of matrices, as well as by recent advancements in leveraging quantum computing for faster numerical linear algebra. Central to our approach is a direct translation of a multivariate trace formula into a quantum circuit, achieved through a sequence of low-level circuit construction operations. To facilitate this translation, we introduce quantum Matrix States Linear Algebra (qMSLA), a framework tailored for the efficient generation of state preparation circuits via primitive matrix algebra operations. Our algorithm relies on sets of state preparation circuits for input matrices as its primary inputs and yields two state preparation circuits encoding the multivariate trace as output. These circuits are constructed utilizing qMSLA operations, which enact the aforementioned multivariate trace formula. We emphasize that our algorithm's inputs consist solely of state preparation circuits, eschewing harder to synthesize constructs such as Block Encodings. Furthermore, our approach operates independently of the availability of specialized hardware like QRAM, underscoring its versatility and practicality.