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)=Θ(\e^{-1/2})$ in the (deterministic) worst case setting, and $n(\e)=Θ(\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.
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 C2([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)=Θ(\e−1/2) in the (deterministic) worst case setting, and n(\e)=Θ(\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(21iM), where M is an n×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.
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.
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.
Our understanding of complex mechanical processes is by our inability to solve the equations that govern them except for simple cases. Numerical simulation of systems appears to be our best option to understand, design and improve systems. It turns out, however, that computational problems in mechanics are notoriously difficult to treat numerically. The computational time that is required often scales exponentially with the size of the problem.
One of the most radical approaches for treating problems was proposed by Feytiman in 1982 [46]: he suggested that mechanics itself showed a promising way to simulate physics. This idea, the so called computer, showed its potential convincingly in one important regime with the development of Shor's integer factorization algorithm which improves exponentially on the best known classical algorithm.
In this thesis we explore six different computational problems from mechanics, study their computational complexity and try to find ways to remedy them. In the first problem we investigate the reasons behind the improved performance of Shor's and similar algorithms. We show that the key part in Shor's algorithm, the phase estimation algorithm, achieves its good performance through the use of power queries and we give lower bounds for all phase estimation algorithms that use power queries that match the known upper bounds. Our research indicates that problems that allow the use of power queries will achieve similar exponential improvements over classical algorithms. We then apply our lower bound technique for power queries to the Sturm-Liouville eigenvalue problem and show matching lower bounds to the upper bounds of Papageorgiou and Wozniakowski [85]. It seems to be very difficult, though, to find nontrivial instances of the Sturm-Lionville problem for which power queries can be simulated efficiently.
A computer differs from a classical computer that uses randomness, because it allows negative probabilities that can cancel each other (destructive interference). Ideally we would like to transfer classical randomized algorithms to the computer and get speed improvements. One of the simplest classical randomized algorithm is the random walk and we study the behavior of the continuous-time random walk. We analyze this random walk in one dimension and give analytical formulas for its behavior that demonstrate its interference properties. Is interference or cancellation really the most important advantage that a computer has over a classical computer? To answer that question we study the class StociMA of stochastic quantum algorithms that only use classical gates, but are given a witness, i.e. an arbitrary state that can guide the algorithm in computing the correct answer, but should not be able to fool it. We show that there exists a complete problem for this class, which we call the stoquastic local Hamiltonian problem. In this problem we try to compute the lowest eigenvalue of a Hamiltonian with interactions that span only a fixed number of particles and all contribute negatively. With the help of this problem we prove that MA ⊆ StocIMA ⊆ SBP ∪ QMA. This shows that interference is one of the most important parts of computation.
The simulation of the evolution of a general system in time requires a computational time that is exponential in the dimension of the system. But maybe the problem that we ask for is too general and we can simulate special systems in polynomial time. In particular it would be interesting to study systems of limited energy, i.e. for which the state at starting time consists mainly out of components with small energy. We model this in the theory of weighted reproducing kernel Hilbert spaces with two different sets of weights: product weights and finite-order weights. We will show that the information cost of computing the evolution for starting states from these spaces is tractable, i.e. the cost does not grow exponentially with the dimension of the problem.
Finally we study a computational problem from lattice chromodynamics (QCD). In most popular algorithms that treat problems in QCD the (gauged) Dirac matrix has to be inverted numerous times. Since this matrix is large, sparse, and ill-conditioned, iterative approaches have to be used. Unfortunately a direct application of methods like conjugate gradient (CC) or minimal residual algorithms seem to give poor performance in practice. We study a newly proposed multigrid method, adaptive smoothed aggregation [29], that has promise to overcome these difficulties We show that while classical CG's convergence becomes worse as the matrix becomes almost singular, adaptive smoothed aggregation will still perform well.
Quantum computing has attracted a lot of attention in different research fields, such as mathematics, physics and computer science. Quantum algorithms can solve certain problems significantly faster than classical algorithms. There are many numerical problems, especially those arising from quantum systems, which are notoriously difficult to solve using classical computers, since the computational time required often scales exponentially with the size of the problem. However, quantum computers have the potential to solve these problems efficiently, which is also one of the founding ideas of the field of quantum computing. In this thesis, we explore five computational problems, designing innovative quantum algorithms and studying their computational complexity. First, we design an adiabatic quantum algorithm based on the Berry phases for the counting problem. For the running time, it is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result should be robust to decoherence and resilient to certain kinds of noise. Since the counting problem is the foundation of many other numerical problems, such as high-dimensional integration and path integration, our adiabatic algorithms can be directly generalized to these kinds of problems. In addition, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. The lower bound is very close to the best lower bound on query complexity known for the classical PAC learning model. We also study the algorithms and the cost of simulating a system evolving under a given Hamiltonian. We consider high order splitting methods that are particularly applicable in quantum simulation and obtain bounds on the number of exponentials required. Moreover, we derive the optimal order of convergence given the required error bound. We compare our complexity estimates to previously known ones and show the resulting speedup. Furthermore, we consider randomized algorithms for Hamiltonian simulation. The evolution is simulated by a product of exponentials in a random sequence and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. We provide a scheme to bound the error of the final quantum state in a randomized algorithm, and obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement. We also apply Hamiltonian simulation in estimating the ground state energy of a multiparticle system, which is also known as the multivariate Sturm-Liouville eigenvalue problem. Since the cost of this problem grows exponentially with the number of particles using deterministic classical algorithms, it suffers from the curse of dimensionality. Quantum computers can vanquish the curse, and we exhibit a quantum algorithm whose total cost are linear in the number of particles.
We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint k on an n-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected (1/2−ε)-approximation using only Oε(logn) queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above 1/4 requires Ω(n/logn) queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a (1−1/e−ε)-approximation using Oε(min{n,n/k}) queries. When k=o(n), our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when k=cn for any fixed rational c<1−1/e−ε, the query complexity reduces to Oε,c(logn), yielding an exponential separation from the classical Ω(n/logn) lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of exp(Ω(ε2n)) queries for achieving a ratio beyond 1/2+ε without constraints, and exp(Ω(ε2k)) queries for exceeding 1−1/e+ε when k/n≤ε. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.
Abstract We describe a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix. This algorithm combines quantum phase estimation and quantum amplitude estimation to achieve a quadratic speedup with respect to the best classical algorithm in terms of matrix dimensionality, i.e. O ~ ( N / ε ) 9 9 In this work O ~ ignores terms that are polylogarithmic in N or 1 / ε . black-box queries to an oracle encoding the matrix, where N is the matrix dimension and ɛ is the desired precision. In contrast, the best classical algorithm for the same task requires Ω ( N ) polylog ( 1 / ε ) queries. In addition, this algorithm allows the user to select any constant success probability. We also provide a similar algorithm with the same runtime that allows us to prepare a quantum state lying mostly in the matrix’s low-energy subspace. We implement simulations of both algorithms and demonstrate their application to problems in quantum chemistry and materials science.