  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.
