Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0512109 · Journal of Complexity

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

Arvid J. Bessen

Published Jun 11, 2006• 3 citations
arXivHTMLPDF
DOI
10.1016/j.jco.2006.03.006

Related papers

Classical and Quantum Complexity of the Sturm–Liouville Eigenvalue Problem

Anargyros Papageorgiou, H. Woźniakowski

arXiv:quant-ph/0502054•Quantum Information Processing•May 17, 2005•26 citations

The Sturm-Liouville Eigenvalue Problem and NP-Complete Problems in the Quantum Setting with Queries

Anargyros Papageorgiou, H. Woźniakowski

arXiv:quant-ph/0504194•Quantum Information Processing•Nov 27, 2006•8 citations

On the complexity of the multivariate Sturm–Liouville eigenvalue problem

Anargyros Papageorgiou

Journal of Complexity•Mar 29, 2007•12 citations

Fredholm determinant and the Sturm-Liouville problems in quantum mechanics

Mikio Nakahara

Physics Letters A•Mar 1, 1994•0 citations

A Lower Bound for the Sturm-Liouville Eigenvalue Problem on a Quantum Computer

Arvid J. Bessen

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.

•Dec 14, 2005•3 citations

WKB analysis of $\mathcal P$$\mathcal T$-symmetric Sturm–Liouville problems

Carl M. Bender, Hugh F Jones

Most studies of -symmetric quantum-mechanical Hamiltonians have considered the Schrödinger eigenvalue problem on an infinite domain. This paper examines the consequences of imposing the boundary conditions on a finite domain. As is the case with regular Hermitian Sturm–Liouville problems, the eigenvalues of the -symmetric Sturm–Liouville problem grow like n 2 for large n . However, the novelty is that a eigenvalue problem on a finite domain typically exhibits a sequence of critical points at which pairs of eigenvalues cease to be real and become complex conjugates of one another. For the potentials considered here this sequence of critical points is associated with a turning point on the imaginary axis in the complex plane. WKB analysis is used to calculate the asymptotic behaviours of the real eigenvalues and the locations of the critical points. The method turns out to be surprisingly accurate even at low energies. This article is part of a special issue of Journal of Physics A: Mathematical and Theoretical devoted to ‘Quantum physics with non-Hermitian operators’.

arXiv:1201.1234•Journal of Physics A Mathematical and Theoretical•Oct 23, 2012•15 citations
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.
WKB analysis of P\mathcal PPT\mathcal TT-symmetric Sturm–Liouville problems
Most studies of -symmetric quantum-mechanical Hamiltonians have considered the Schrödinger eigenvalue problem on an infinite domain. This paper examines the consequences of imposing the boundary conditions on a finite domain. As is the case with regular Hermitian Sturm–Liouville problems, the eigenvalues of the -symmetric Sturm–Liouville problem grow like n 2 for large n . However, the novelty is that a eigenvalue problem on a finite domain typically exhibits a sequence of critical points at which pairs of eigenvalues cease to be real and become complex conjugates of one another. For the potentials considered here this sequence of critical points is associated with a turning point on the imaginary axis in the complex plane. WKB analysis is used to calculate the asymptotic behaviours of the real eigenvalues and the locations of the critical points. The method turns out to be surprisingly accurate even at low energies. This article is part of a special issue of Journal of Physics A: Mathematical and Theoretical devoted to ‘Quantum physics with non-Hermitian operators’.