Search

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]

The computation of combinatorial and numerical problems on quantum computers is often much faster than on a classical computer in numbers of queries. A query is a procedure by which the quantum computer gains information about the specific problem. Different query definitions were given and our aim is to review them and to show that these definitions are not equivalent. To achieve this result we will study the simulation and approximation of one query type by another. While approximation is “easy” in one direction, we will show that it is “hard” in the other direction by a lower bound for the numbers of queries needed in the simulation. The main tool in this lower bound proof is a relationship between quantum algorithms and trigonometric polynomials that we will establish. [Copyright &y& Elsevier]