Quantum and classical query complexities of functions of matrices

Ashley Montanaro, Changpeng Shao

Let $A$ be an $s$-sparse Hermitian matrix, $f(x)$ be a univariate function, and $i,j$ be two indices. In this work, we investigate the query complexity of approximating $\bra{i} f…