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 \emph{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.

本文提出了一种适用于近似多元痕迹（即矩阵乘积的痕迹）的量子算法，该算法通过一系列低层电路构造操作将多元痕迹公式直接转化为量子电路，并利用 qMSLA 操作构建状态准备电路，输出两个编码多变痕迹的状态准备电路。此算法仅使用状态准备电路作为输入，不依赖于诸如 Block Encodings 之类较难合成的构造，同时也不依赖于特定硬件（如 QRAM），突显其通用性和实用性。