dorsal/arxiv
View SchemaClassical and Quantum Complexity of the Sturm-Liouville Eigenvalue Problem
| Authors | A. Papageorgiou, H. Wozniakowski |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0502054 |
| URL | https://arxiv.org/abs/quant-ph/0502054 |
Abstract
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 $C^2([0,1])$ and study the minimal number $n(\e)$ of function evaluations or queries that are necessary to compute an $\e$-approximation of the smallest eigenvalue. We prove that $n(\e)=\Theta(\e^{-1/2})$ in the (deterministic) worst case setting, and $n(\e)=\Theta(\e^{-2/5})$ in the randomized setting. The quantum setting offers a polynomial speedup with {\it bit} queries and an exponential speedup with {\it power} queries. Bit queries are similar to the oracle calls used in Grover's algorithm appropriately extended to real valued functions. Power queries are used for a number of problems including phase estimation. They are obtained by considering the propagator of the discretized system at a number of different time moments. They allow us to use powers of the unitary matrix $\exp(\tfrac12 {\rm i}M)$, where $M$ is an $n\times n$ matrix obtained from the standard discretization of the Sturm-Liouville differential operator. The quantum implementation of power queries by a number of elementary quantum gates that is polylog in $n$ is an open issue.
{
"annotation_id": "9acaf7d4-e21d-4e72-ac69-07c865eac067",
"date_created": "2026-03-02T18:02:13.738000Z",
"date_modified": "2026-03-02T18:02:13.738000Z",
"file_hash": "f597498ebdc4fddce7b91d5e8a376b86557eed1754db3cba3f860de76efedf73",
"private": false,
"record": {
"abstract": "We study the approximation of the smallest eigenvalue of a Sturm-Liouville\nproblem in the classical and quantum settings. We consider a univariate\nSturm-Liouville eigenvalue problem with a nonnegative function $q$ from the\nclass $C^2([0,1])$ and study the minimal number $n(\\e)$ of function evaluations\nor queries that are necessary to compute an $\\e$-approximation of the smallest\neigenvalue. We prove that $n(\\e)=\\Theta(\\e^{-1/2})$ in the (deterministic)\nworst case setting, and $n(\\e)=\\Theta(\\e^{-2/5})$ in the randomized setting.\nThe quantum setting offers a polynomial speedup with {\\it bit} queries and an\nexponential speedup with {\\it power} queries. Bit queries are similar to the\noracle calls used in Grover\u0027s algorithm appropriately extended to real valued\nfunctions. Power queries are used for a number of problems including phase\nestimation. They are obtained by considering the propagator of the discretized\nsystem at a number of different time moments. They allow us to use powers of\nthe unitary matrix $\\exp(\\tfrac12 {\\rm i}M)$, where $M$ is an $n\\times n$\nmatrix obtained from the standard discretization of the Sturm-Liouville\ndifferential operator. The quantum implementation of power queries by a number\nof elementary quantum gates that is polylog in $n$ is an open issue.",
"arxiv_id": "quant-ph/0502054",
"authors": [
"A. Papageorgiou",
"H. Wozniakowski"
],
"categories": [
"quant-ph"
],
"title": "Classical and Quantum Complexity of the Sturm-Liouville Eigenvalue Problem",
"url": "https://arxiv.org/abs/quant-ph/0502054"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6e797058-c3c0-434d-b470-dbeec29b4d25",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}