A Lower Bound for the SturmLiouville Eigenvalue Problem on a Quantum Computer
 Title:
 A Lower Bound for the SturmLiouville Eigenvalue Problem on a Quantum Computer
 Author(s):
 Bessen, Arvid J.
 Date:
 2005
 Type:
 Technical reports
 Department(s):
 Computer Science
 Persistent URL:
 http://hdl.handle.net/10022/AC:P:29434
 Series:
 Columbia University Computer Science Technical Reports
 Part Number:
 CUCS05205
 Publisher:
 Department of Computer Science, Columbia University
 Publisher Location:
 New York
 Abstract:
 We study the complexity of approximating the smallest eigenvalue of a univariate SturmLiouville problem on a quantum computer. This general problem includes the special case of solving a onedimensional Schroedinger equation with a given potential for the ground state energy. The SturmLiouville problem depends on a function q, which, in the case of the Schroedinger equation, can be identified with the potential function V. Recently Papageorgiou and Wozniakowski proved that quantum computers achieve an exponential reduction in the number of queries over the number needed in the classical worstcase 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 SturmLiouville equation can be solved with O(log(1/e)) power queries, while the number of queries in the worstcase and randomized settings on a classical computer is polynomial in 1/e. 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 Wozniakowski's algorithm is asymptotically optimal. In particular we prove a matching lower bound of log(1/e) power queries, therefore showing that log(1/e) 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.
 Subject(s):
 Computer science
 Item views
 225
 Metadata:

text  xml
 Suggested Citation:
 Arvid J. Bessen, 2005, A Lower Bound for the SturmLiouville Eigenvalue Problem on a Quantum Computer, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:29434.