A lower bound for the Sturm–Liouville eigenvalue problem on a quantum computer

Abstract: We study the complexity of approximating the smallest eigenvalue of a univariate Sturm–Liouville problem on a quantum computer. This general problem includes the special case of solving a one-dimensional Schrödinger equation with a given potential for the ground state energy. The Sturm–Liouville problem depends on a function q, which, in the case of the Schrödinger equation, can be identified with the potential function . Recently Papageorgiou and Woźniakowski proved that quantum computers achieve an exponential reduction in the number of queries over the number needed in the classical worst-case and randomized settings for smooth functions q. Their method uses the (discretized) unitary propagator and arbitrary powers of it as a query (“power queries”). They showed that the Sturm–Liouville equation can be solved with power queries, while the number of queries in the worst-case and randomized settings on a classical computer is polynomial in . This proves that a quantum computer with power queries achieves an exponential reduction in the number of queries compared to a classical computer. In this paper we show that the number of queries in Papageorgiou''s and Woźniakowski''s algorithm is asymptotically optimal. In particular we prove a matching lower bound of power queries, therefore showing that power queries are sufficient and necessary. Our proof is based on a frequency analysis technique, which examines the probability distribution of the final state of a quantum algorithm and the dependence of its Fourier transform on the input. [Copyright &y& Elsevier]