Tight bound for estimating expectation values from a system of linear equations
Abhijeet Alase, Robert R. Nerem, Mohsen Bagherimehrab, Peter Friedrich Hoyer, Barry Cyril Sanders · Physical Review Research · 2022
The system of linear equations problem (SLEP) is specified by a complex invertible matrix $A$, the condition number $\ensuremath{\kappa}$ of $A$, a vector $\mathbit{b}$, a Hermitian matrix $M$, and an accuracy $\ensuremath{\epsilon}$, and the task is to estimate ${\mathbit{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\mathbit{x}$, where $\mathbit{x}$ is the solution vector to the equation $A\mathbit{x}=\mathbit{b}$. We aim to establish a lower bound on the complexity of the end-to-end quantum algorithms for SLEP with respect to $\ensuremath{\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/\ensuremath{\alpha}$ as a block for some $\ensuremath{\alpha}\ensuremath{\in}{\mathbb{R}}^{+}$. We show, by constructing a quantum algorithm and deriving a lower bound, that the quantum query complexity for SLEP in this setting is $\mathrm{\ensuremath{\Theta}}(\ensuremath{\alpha}/\ensuremath{\epsilon})$. Our lower bound is established by reducing the problem of estimating the mean of a black box function to SLEP. Our $\mathrm{\ensuremath{\Theta}}(\ensuremath{\alpha}/\ensuremath{\epsilon})$ result tightens and proves the common assertion of polynomial accuracy dependence $[\mathrm{poly}(1/\ensuremath{\epsilon})]$ 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.