Classical and Quantum Complexity of the Sturm-Liouville Eigenvalue Problem

摘要

The study of the potential power of quantum computers has been a major theoretical challenge. There will be an additional incentive to build a quantum computer if we can identify computationally important problems for which quantum computation offers significant speedups over computation on a classical computer. The Sturm-Liouville eigenvalue problem is defined in full generality. We study the approximation of the smallest eigenvalue of a Sturm- Liouville problem in the classical and quantum settings. We consider a univariate Sturm-Liouville eigenvalue problem with a nonnegative function q from the class C2(0; 1) and study the minimal number n(epsilon) of function evaluations or queries that are necessary to compute an epsilon-approximation of the smallest eigenvalue.