Tight bound for estimating expectation values from a system of linear equations 

Abstract

The System of Linear Equations Problem (SLEP) is specified by a complex invertible matrix A , the condition number κ of A , a vector b , a Hermitian matrix M and an accuracy ǫ , and the task is to estimate x † M x , where x is the solution vector to the equation A x = b . We aim to establish a lower bound on the complexity of the end-to-end quantum algorithms for SLEP with respect to ǫ , and devise a quantum algorithm that saturates this bound. To make lower bounds attainable, we consider query complexity in the setting in which a block encoding of M is given, i.e., a unitary black box U M that contains M/α as a block for some α ∈ R + . We show, by constructing a quantum algorithm and deriving a lower bound, that the quantum query complexity for SLEP in this setting is Θ( α/ǫ ). Our lower bound is established by reducing the problem of estimating the mean of a black box function to SLEP. Our Θ( α/ǫ ) result tightens and proves the common assertion of polynomial accuracy dependence (poly(1 /ǫ )) for SLEP without making any complexity-theoretic assumptions, and shows that improvement beyond linear dependence on accuracy is not possible if M is provided via block encoding.