Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values

Abstract

Many quantum algorithms involve the evaluation of expectation values. Optimal strategies for estimating a single expectation value are known, requiring a number of state preparations that scales with the target error $\epsilon$ as $\mathcal{O}(1/\epsilon )$. In this paper, we address the task of estimating the expectation values of $M$ different observables, each to within additive error $\epsilon$, with the same $1/\epsilon$ dependence. We describe an approach that leverages Gilyén et al.'s quantum gradient estimation algorithm to achieve $\mathcal{O}(\sqrt{M}/\epsilon )$ scaling up to logarithmic factors, regardless of the commutation properties of the $M$ observables. We prove that this scaling is worst-case optimal in the high-precision regime if the state preparation is treated as a black box, even when the operators are mutually commuting. We highlight the flexibility of our approach by presenting several generalizations, including a strategy for accelerating the estimation of a collection of dynamic correlation functions.

References in corpus (5)

• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Information-theoretic bounds on quantum advantage in machine learning
• Optimal Quantum Measurements of Expectation Values of Observables
• Fermionic partial tomography via classical shadows
• Robust shadow estimation

Cited by in corpus (11)

• Efficient quantum computation of molecular forces and other energy gradients
• Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
• Optimizing the information extracted by a single qubit measurement
• Estimating Quantum Hamiltonians via Joint Measurements of Noisy Non-Commuting Observables
• On quantum algorithms for the Schrödinger equation in the semi-classical regime
• Inferring physical properties of symmetric states from the fewest copies
• Tight Bound for Estimating Expectation Values from a System of Linear Equations
• Quantum-enhanced mean value estimation via adaptive measurement
• Almost optimal measurement scheduling of molecular Hamiltonian via finite projective plane
• Quantum memory assisted observable estimation
• Expanding the reach of quantum optimization with fermionic embeddings