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

DOI10.1016/J.JCO.2006.03.006zbMATH Open1142.34392arXivquant-ph/0512109OpenAlexW2953068357MaRDI QIDQ855896FDOQ855896

Arvid J. Bessen

Publication date: 7 December 2006

Published in: Journal of Complexity (Search for Journal in Brave)

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 Schroedinger 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 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 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 O(log(1/e)) power queries, while the number of queries in the worst-case 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.

Full work available at URL: https://arxiv.org/abs/quant-ph/0512109

zbMATH Keywords

lower boundsquantum algorithmSturm-Liouville problempower queries

Mathematics Subject Classification ID

Quantum computation (81P68) Eigenvalues, estimation of eigenvalues, upper and lower bounds of ordinary differential operators (34L15) Numerical solution of eigenvalue problems involving ordinary differential equations (65L15)

Cites Work

• Title not available (Why is that?)
• The quantum query complexity of approximating the median and related statistics
• Title not available (Why is that?)
• Lower bound for quantum phase estimation
• Quantum summation with an application to integration.
• Quantum approximation. I: Embeddings of finite-dimensional \(L_{p}\) spaces
• Quantum approximation. II: Sobolev embeddings
• Quantum complexity of integration
• Quantum lower bounds by polynomials
• Title not available (Why is that?)
• The power of various real-valued quantum queries
• Classical and quantum complexity of the Sturm-Liouville eigenvalue problem

Cited In (3)

• Quantum Walks
• On the complexity of the multivariate Sturm-Liouville eigenvalue problem
• Quantum lower bounds by entropy numbers

   Recommendations

• Classical and quantum complexity of the Sturm-Liouville eigenvalue problem 👍 👎
• On the complexity of the multivariate Sturm-Liouville eigenvalue problem 👍 👎
• The Sturm-Liouville eigenvalue problem and NP-complete problems in the quantum setting with queries 👍 👎
• Approximating ground and excited state energies on a quantum computer 👍 👎
• Lower bound for quantum phase estimation 👍 👎

This page was built for publication: A lower bound for the Sturm-Liouville eigenvalue problem on a quantum computer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q855896)