Southwest Quantum Information and Technology

Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values

Presenting Author: William Huggins, Google
Contributing Author(s): Kianna Wan, Jarrod McClean, Thomas E. O'Brien, Nathan Wiebe, Ryan Babbush

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 ε as ε^−1. In this paper we address the task of estimating the expectation values of M different observables, each to within additive error ε, with the same ε^−1 dependence. We describe an approach that leverages Gilyén et al.'s quantum gradient estimation algorithm to achieve M^(1/2) ε^−1 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.

Read this article online: https://arxiv.org/abs/2111.09283

(Session 5 : Thursday from 5:00 pm - 7:00 pm)