Quantum Algorithms for Differential Equations

This thesis describes quantum algorithms for Hamiltonian simulation,
ordinary differential equations (ODEs), and partial differential
equations (PDEs).
 
Product formulas are used to simulate Hamiltonians which can be
expressed as a sum of terms which can each be simulated individually.
By simulating each of these terms in sequence, the net effect
approximately simulates the total Hamiltonian. We find that the error
of product formulas can be improved by randomizing over the order in
which the Hamiltonian terms are simulated. We prove that this approach
is asymptotically better than ordinary product formulas and present
numerical comparisons for small numbers of qubits.
 
The ODE algorithm applies to the initial value problem for
time-independent first order linear ODEs. We approximate the
propagator of the ODE by a truncated Taylor series, and we encode the
initial value problem in a large linear system. We solve this linear
system with a quantum linear system algorithm (QLSA) whose output we
perform a post-selective measurement on. The resulting state encodes
the solution to the initial value problem. We prove that our algorithm
is asymptotically optimal with respect to several system parameters.
 
The PDE algorithms apply the finite difference method (FDM) to
Poisson's equation, the wave equation, and the Klein-Gordon equation.
We use high order FDM approximations of the Laplacian operator to
develop linear systems for Poisson's equation in cubic volumes under
periodic, Neumann, and Dirichlet boundary conditions. Using QLSAs, we
output states encoding solutions to Poisson's equation. We prove that
our algorithm is exponentially faster with respect to the spatial
dimension than analogous classical algorithms. We also consider how
high order Laplacian approximations can be used for simulating the
wave and Klein-Gordon equations. We consider under what conditions it
suffices to use Hamiltonian simulation for time evolution, and we
propose an algorithm for these cases that uses QLSAs for state
preparation and post-processing.