Multivariate trace estimation in constant quantum depth

Quantum 8, 1220 (2024).

https://doi.org/10.22331/q-2024-01-10-1220

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), a subroutine crucial to applications in condensed matter and quantum information science. 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 central task of multivariate trace estimation 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.