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.

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

References in corpus (45)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum algorithm for solving linear systems of equations
• Area laws for the entanglement entropy - a review
• Entanglement Spectrum as a Generalization of Entanglement Entropy: Identification of Topological Order in Non-Abelian Fractional Quantum Hall Effect States
• Quantum principal component analysis
• Entanglement spectrum of a topological phase in one dimension
• Quantum fingerprinting
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Probing entanglement entropy via randomized measurements
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Direct estimations of linear and non-linear functionals of a quantum state
• Universal Quantum Estimator
• Entanglement spectrum of topological insulators and superconductors
• Quantum-assisted quantum compiling
• Quantum speedup of Monte Carlo methods
• Rényi Entropies from Random Quenches in Atomic Hubbard and Spin Models
• Direct detection of quantum entanglement
• Entanglement entropy and entanglement spectrum of the Kitaev model
• Noise Resilience of Variational Quantum Compiling
• The power of random measurements: measuring Tr(ρ^n) on single copies of ρ
• Entanglement Spectrum, Critical Exponents and Order Parameters in Quantum Spin Chains
• Contractivity of positive and trace preserving maps under $L_p$ norms
• Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem?
• Maximum Likelihood Estimation of Functionals of Discrete Distributions
• Unitary $n$-designs via random quenches in atomic Hubbard and Spin models: Application to the measurement of Rényi entropies
• Emergent irreversibility and entanglement spectrum statistics
• Quantum Fisher information from randomized measurements
• Hamiltonian Simulation with Optimal Sample Complexity
• Entanglement spectroscopy on a quantum computer
• Low depth algorithms for quantum amplitude estimation
• Quantum algorithm for Petz recovery channels and pretty good measurements
• Measuring Polynomial Invariants of Multi-Party Quantum States
• Systematic Crosstalk Mitigation for Superconducting Qubits via Frequency-Aware Compilation
• Entanglement spectroscopy with a depth-two quantum circuit
• Variational quantum amplitude estimation
• Cyclic Quantum Error-Correcting Codes and Quantum Shift Registers
• Quantum algorithm for estimating Renyi entropies of quantum states
• Quantum Algorithm for Fidelity Estimation
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Qubit-efficient entanglement spectroscopy using qubit resets
• Measuring Quantum Entropy
• Quantum algorithms for estimating quantum entropies
• Learning unknown pure quantum states
• Depth-efficient proofs of quantumness
• Unified multivariate trace estimation and quantum error mitigation

Cited by in corpus (22)

• 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
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Logarithmic-Depth Quantum Circuits for Hamming Weight Projections
• Geometry of sets of Bargmann invariants
• Certifying nonstabilizerness in quantum processors
• Sample Complexity of Black Box Work Extraction
• Readout Error Mitigation for Mid-Circuit Measurements and Feedforward
• Parallel Quantum Signal Processing Via Polynomial Factorization
• Space-time tradeoff in networked virtual distillation
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• 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