There is a folkloric belief that a depth-$\Theta(m)$ quantum circuit is needed to estimate the trace of the product of $m$ density matrices (i.e., a multivariate trace). We prove that this belief is overly conservative by constructing a constant quantum-depth circuit for the task, inspired by the method of Shor error correction. Furthermore, our circuit demands only local gates in a two dimensional circuit -- we show how to implement it in a highly parallelized way on an architecture similar to that of Google's Sycamore processor. With these features, our algorithm brings the task of multivariate trace estimation, crucial to applications in condensed matter and estimating nonlinear functions of quantum states, closer to the capabilities of near-term quantum processors. We instantiate the latter application with a theorem on estimating nonlinear functions of quantum states with ``well-behaved" polynomial approximations.

翻译：一种民间传说相信,需要用一个深度-$\ Theta(m) 量子电路来估计美元密度矩阵(即多变量跟踪)的产物的痕量。我们证明,这种信念过于保守,为此,在Shor错误校正方法的启发下,为任务建造了一个恒定量深度电路。此外,我们的电路只要求用两维电路的本地门,我们展示了如何在类似于谷歌的 Sycamore 处理器的建筑上以高度平行的方式执行它。有了这些特征,我们的算法带来了多变量跟踪估计的任务,这对浓缩物质的应用和估计量子状态的非线性功能至关重要,更接近于短期量子处理器的能力。我们用“well-behadd” 多边近似法将后者应用与估计量子状态的非线性函数的理论进行回转。