Tight Bound for Estimating Expectation Values from a System of Linear Equations

Understand

The System of Linear Equations Problem (SLEP) is specified by a complex invertible matrix $A$, the condition number $\kappa$ of $A$, a vector $b$, a Hermitian matrix $M$ and an accuracy $\epsilon$, and the task is to estimate $x^\dagger Mx$, where $x$ is the solution vector to the equation $Ax = b$.

• We aim to establish a lower bound on the complexity of the end-to-end quantum algorithms for SLEP with respect to $\epsilon$, 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/\alpha$ as a block for some $\alpha \in \mathbb R^+$.
• We show that the quantum query complexity for SLEP in this setting is $\Theta(\alpha/\epsilon)$.