Leveraging Periodicity as a Quantum PDE Solver
Pooya Ronagh
University of Waterloo
Quantum computing is anticipated to deliver substantial computational advantages for problems that possess exploitable structure. A central question, however, is what forms of structure enable such advantages, and whether they arise in meaningful real-world applications. While this question has been extensively studied for discrete computational problems (i.e. those involving Boolean functions), an analogous systematic investigation has been lacking for continuous-domain problems. In this talk, we relate different degrees of smoothness of real-valued periodic functions to the computational complexity of preparing high-precision amplitude encodings of these functions as quantum states. We focus on the setting in which such functions arise as solutions to partial differential equations (PDEs). We then introduce a novel pseudo-spectral Fourier–analytic framework for manipulating periodic functions, which gives rise to a rich family of quantum algorithms for solving both time-dependent and time-independent PDEs at varying target precisions. As an illustrative application, we present a hierarchy of many-body quantum simulation pipelines that exhibit increasing levels of quantum computational advantage as the scale of available quantum resources grows.
Back to Long Programs