Quantum and classical query complexities of functions of matrices

Abstract

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 $⟨i|f(A)|j⟩$. We show that for any continuous function $f(x):[-1,1]\to [-1,1]$, the quantum query complexity of computing $⟨i|f(A)|j⟩\pm \epsilon /4$ is lower bounded by $\Omega ({\widetilde{°}}_{\epsilon }(f))$. The upper bound is at most quadratic in ${\widetilde{°}}_{\epsilon }(f)$ and is linear in ${\widetilde{°}}_{\epsilon }(f)$ under certain mild assumptions on $A$. Here the approximate degree ${\widetilde{°}}_{\epsilon }(f)$ is the minimum degree such that there is a polynomial of that degree approximating $f$ up to additive error $\epsilon$ in the interval $[-1,1]$. We also show that the classical query complexity is lower bounded by $\tilde{\Omega }((s/2{)}^{({\widetilde{°}}_{2\epsilon }(f)-1)/6})$ for any $s\ge 4$. Our results show that the quantum and classical separation is exponential for any continuous function of sparse Hermitian matrices, and also imply the optimality of implementing smooth functions of sparse Hermitian matrices by quantum singular value transformation. As another hardness result, we show that entry estimation problem (i.e., deciding $⟨i|f(A)|j⟩\ge \epsilon$ or $⟨i|f(A)|j⟩\le -\epsilon$) is BQP-complete for any continuous function $f(x)$ as long as its approximate degree is large enough. The main techniques we used are the dual polynomial method for functions over the reals, linear semi-infinite programming, and tridiagonal matrices.

37 pages, key results are enhanced, we added BQP-completeness result

References in corpus (10)

• Quantum algorithm for solving linear systems of equations
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Exponential improvement in precision for simulating sparse Hamiltonians
• A Limit on the Speed of Quantum Computation in Determining Parity
• Separations in query complexity using cheat sheets
• Complexity of quantum state verification in the quantum linear systems problem
• Tight Bound for Estimating Expectation Values from a System of Linear Equations
• A (simple) classical algorithm for estimating Betti numbers
• Quantum algorithms for powering stable Hermitian matrices

Cited by in corpus (3)

• Quantum eigenvalue processing
• Parallel Quantum Signal Processing Via Polynomial Factorization
• An adversary bound for quantum signal processing