dorsal/arxiv
View SchemaA Lower Bound for the Sturm-Liouville Eigenvalue Problem on a Quantum Computer
| Authors | Arvid J. Bessen |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0512109 |
| URL | https://arxiv.org/abs/quant-ph/0512109 |
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.
{
"annotation_id": "c43b8f5a-20b3-4b38-ae5e-20290a5b0a80",
"date_created": "2026-03-02T18:02:23.065000Z",
"date_modified": "2026-03-02T18:02:23.065000Z",
"file_hash": "422afe35dedcdbfb51eb575fa2cef6ac1ab446d33ab2a423417949d3001a9739",
"private": false,
"record": {
"abstract": "We study the complexity of approximating the smallest eigenvalue of a\nunivariate Sturm-Liouville problem on a quantum computer. This general problem\nincludes the special case of solving a one-dimensional Schroedinger equation\nwith a given potential for the ground state energy.\n The Sturm-Liouville problem depends on a function q, which, in the case of\nthe Schroedinger equation, can be identified with the potential function V.\nRecently Papageorgiou and Wozniakowski proved that quantum computers achieve an\nexponential reduction in the number of queries over the number needed in the\nclassical worst-case and randomized settings for smooth functions q. Their\nmethod uses the (discretized) unitary propagator and arbitrary powers of it as\na query (\"power queries\"). They showed that the Sturm-Liouville equation can be\nsolved with O(log(1/e)) power queries, while the number of queries in the\nworst-case and randomized settings on a classical computer is polynomial in\n1/e. This proves that a quantum computer with power queries achieves an\nexponential reduction in the number of queries compared to a classical\ncomputer.\n In this paper we show that the number of queries in Papageorgiou\u0027s and\nWozniakowski\u0027s algorithm is asymptotically optimal. In particular we prove a\nmatching lower bound of log(1/e) power queries, therefore showing that log(1/e)\npower queries are sufficient and necessary. Our proof is based on a frequency\nanalysis technique, which examines the probability distribution of the final\nstate of a quantum algorithm and the dependence of its Fourier transform on the\ninput.",
"arxiv_id": "quant-ph/0512109",
"authors": [
"Arvid J. Bessen"
],
"categories": [
"quant-ph"
],
"title": "A Lower Bound for the Sturm-Liouville Eigenvalue Problem on a Quantum Computer",
"url": "https://arxiv.org/abs/quant-ph/0512109"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d7977409-b49d-44d3-a5fe-5fe4b787df60",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}