Multivariate trace estimation in constant quantum depth

Abstract

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.

v3: 18 pages, 3 figures, accepted for publication in Quantum Journal

References in corpus (7)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum algorithm for solving linear systems of equations
• Entanglement Spectrum as a Generalization of Entanglement Entropy: Identification of Topological Order in Non-Abelian Fractional Quantum Hall Effect States
• Entanglement spectroscopy on a quantum computer
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Quantum algorithms for estimating quantum entropies
• Unified multivariate trace estimation and quantum error mitigation

Cited by in corpus (21)

• Unitary-invariant witnesses of quantum imaginarity
• Measurement-Based Long-Range Entangling Gates in Constant Depth
• Kirkwood-Dirac representations beyond quantum states (and their relation to noncontextuality)
• Quantum Neural Estimation of Entropies
• Logarithmic-Depth Quantum Circuits for Hamming Weight Projections
• Geometry of sets of Bargmann invariants
• Certifying nonstabilizerness in quantum processors
• Readout Error Mitigation for Mid-Circuit Measurements and Feedforward
• Sample Complexity of Black Box Work Extraction
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• Space-time tradeoff in networked virtual distillation
• Parallel Quantum Signal Processing Via Polynomial Factorization
• Quantum advantage in temporally flat measurement-based quantum computation
• Resource-efficient algorithm for estimating the trace of quantum state powers
• Variational-toolbox-based separability detection of multiqubit states
• An Elementary Characterization of Bargmann Invariants
• Numerical ranges of Bargmann invariants
• Detecting entanglement from few partial transpose moments and their decay via weight enumerators
• Bargmann-invariant framework for local unitary equivalence and entanglement
• Estimation of multivariate traces of states given partial classical information
• Beating the Optimal Verification of Entangled States via Collective Strategies