Multivariate trace estimation in constant quantum depth
Yihui Quek, Eneet Kaur, Mark M. Wilde · Quantum · 2024
There is a folkloric belief that a depth- Θ ( 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 S y c a m o r e 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.