Quantum Algorithms for Scientific Computation

Abstract

This thesis presents a mathematical analysis of several quantum algorithms and their applications in scientific computation. It is organized into two parts. The first part investigates quantum algorithms for the quantum simulation problem, with particular emphasis on methods based on Lie–Trotter–Suzuki formulas, commonly known as product formulas. It develops a rigorous analysis of a digital quantum simulation algorithm: the multiproduct formula, a high-order method constructed from low-order product formulas. First, it provides a detailed characterization of the error scaling of the time-independent multiproduct formula for simulating quantum dynamics in finite-dimensional quantum systems. This analysis establishes both commutator scaling and a near-optimal dependence on the simulation time and target precision. The results show that the multiproduct formula achieves a polynomial speedup with respect to system size and evolution time, together with an exponential improvement in the dependence on precision. The thesis then extends the multiproduct formula to the simulation of non-unitary dynamics by combining it with a recently proposed quantum algorithm for dissipative linear differential equations. The resulting algorithm is shown to exhibit commutator scaling, a property that is particularly important for the quantum simulation of differential equations. The performance of both algorithms is also examined in various application cases. The second part proposes Chebyshev polynomial expansions as a unifying principle for a range of quantum algorithms and applications. The approach exploits the direct correspondence between Chebyshev polynomials and the parameters of quantum signal processing, thereby enabling the straightforward implementation of Chebyshev polynomials on a quantum computer. This observation is used to design fixed-parameter quantum circuits for function approximation. The method is applied to the approximation of functions in two classes of function spaces: high-dimensional functions in the Korobov function space, a structured subspace of Sobolev spaces well suited to high-dimensional approximation and integration; and countably parametric holomorphic maps, which arise naturally in applications such as uncertainty quantification and parametric partial differential equations. Finally, the thesis introduces a quantum algorithm for the non-uniform quantum Fourier transform based on a low-rank factorization technique derived from Chebyshev expansions. This method overcomes limitations of algorithms that rely on uniform grids and enables efficient quantum spectral transforms on non-uniform grids. These results demonstrate the versatility of Chebyshev polynomials across a broad range of quantum computational tasks.