UC Berkeley

This dissertation concerns the numerical simulation of many-body quantum dynamics, which is fundamental for predicting physical and chemical properties at the atomic and sub-atomic scale. The problem appears ubiquitously in many areas, such as quantum chemistry, quantum controls, and quantum information theory. Simulating many-body quantum dynamics poses a variety of computational challenges, including high dimensionality and fast oscillations. While model reduction techniques can partially resolve the high dimensionality issue on classical computers, quantum computers give rise to new hopes to directly simulate the full many-body quantum dynamics. Nevertheless, both classical and quantum simulations still suffer from highly oscillatory solutions, limiting the time step sizes in time discretization and hindering the practical applications of quantum dynamics simulation. The broad goal of this dissertation is to investigate how classical and quantum computers can efficiently treat fast oscillatory solutions. As a notable application, such progress leads to new methods for solving linear system problems on quantum computers. This dissertation consists of three parts: adiabatic dynamics (Part II), classical simulation (Part III) and quantum simulation (Part IV).

Although the quantum dynamics are generally complicated, when the Hamiltonian varies slowly with time and satisfies certain spectrum gap conditions, the solution can approximately remain within some specific eigenspace of the Hamiltonian. This phenomenon is called the near adiabatic evolution, which has attracted much attention since the early days of quantum mechanics. It weaves together eigenvalue problems and differential equations. Adiabatic dynamics is also one of the underlying physical principles for building universal quantum computational devices. The near adiabatic evolution serves as a glue, explicitly and implicitly, throughout this dissertation. In Part II, we quantitatively study the adiabatic error between the quantum dynamics and the exact eigenspace by proving a new version of the quantum linear adiabatic theorem. Under the gap condition and the vanishing boundary condition, we show that the adiabatic error can converge exponentially in terms of the inverse evolution time. Meanwhile, to control the adiabatic error at the desired level, the evolution time is sufficient to scale almost quadratically in terms of the magnitude of the inverse spectrum gap. This result is almost sharp in both the convergence order and the gap dependence, and appears for the first time beyond the two-level system.

Part III is devoted to designing a new approach to efficiently deal with highly oscillatory solutions of quantum dynamics on classical computers. The critical observation is that such fast oscillations in the wave functions are not physical and are solely due to the generally non-optimal gauge choice (i.e. degrees of freedom irrelevant to physical observables) of the Schr\"odinger equation. The optimal gauge choice is given by a parallel transport formulation, which can significantly flatten the wave functions and thus allow much larger time step sizes in time discretization. We establish the framework of the parallel transport dynamics for evolutions of pure states and mixed states, as well as the time-dependent density functional theory.

We start with the simplest single pure state evolution and derive the dynamics under the parallel transport gauge via two approaches: solving the optimization problem and evolving the dynamics under the parallel transport operator. We analyze the resulting parallel transport dynamics in the context of the singularly perturbed linear Schr\"odinger equation and demonstrate its superior performance in the near adiabatic regime. Then we derive the dynamics under parallel transport gauge for real-time time-dependent density functional theory and numerically test its performance using absorption spectrum, ultrashort laser pulse, and Ehrenfest dynamics calculations as examples. Our tests show that propagating parallel transport dynamics is more than 10 times faster in terms of the wall clock time when compared to the standard explicit fourth-order Runge-Kutta time integrator for the original Schr\"odinger equation. Finally, we generalize the parallel transport dynamics to the scenario of mixed state evolution. Going beyond the linear and near adiabatic regime, we find that the error of the parallel transport dynamics can be bounded by certain commutators between Hamiltonians, density matrices, and their derived quantities. Such a commutator structure is not present in the Schr\"odinger dynamics. The commutator structure of the error bound and numerical results in the nonlinear regimes further confirm the advantage of the parallel transport dynamics.

Part IV is about simulating linear quantum dynamics on quantum computers, as well as application to solving quantum linear system problems. For quantum simulation, we focus on the standard and generalized Trotter methods and study their performance on simulating unbounded time-dependent control Hamiltonian, where the cost of the simulation cannot be well bounded by existing theoretical analysis for most quantum algorithms. We observe that nearly all existing analyses on quantum simulation focus on the difference between the exact evolution operator and the numerical evolution operator. This measures the worst-case error of the quantum simulation, which might not be of practical interest. By proving a new vector norm error bounds for the Trotter type methods, we demonstrate that if the quantum dynamics are smooth enough, the cost of quantum simulation using the Trotter type methods does not increase as the Hamiltonian norm increases. Our result extends that of [Jahnke, Lubich, BIT Numer. Math. 2000] to the time-dependent setting and outperforms all previous analyses in the quantum simulation literature for simulating unbounded time-dependent Hamiltonian. We also clarify the existence and the importance of commutator scalings of Trotter and generalized Trotter methods for time-dependent Hamiltonian simulations.

Linear system solvers are used ubiquitously in scientific computing. Quantum algorithms for solving large systems of linear equations have received much attention recently, but most existing algorithms either do not have optimal asymptotic complexity scalings or involve rather complicated subroutines. We study how simulating quantum dynamics and adiabatic theorem can be combined to construct a new near-optimal quantum linear system solver. Our approach first transforms the linear system problem to an eigenvalue problem, then constructs a near adiabatic dynamics with the final solution solving this eigenvalue problem, finally simulating this near adiabatic dynamics by existing quantum simulation algorithms. We demonstrate that with an optimally tuned scheduling function, the new adiabatic-based solver can readily solve a quantum linear system problem with $\Or(\kappa~\text{poly}(\log(\kappa/\epsilon)))$ runtime, where $\kappa$ is the condition number, and $\epsilon$ is the target accuracy. This is near-optimal in both $\kappa$ and $\epsilon$. The complexity estimate of the adiabatic-based solver is derived from an improved adiabatic theorem in which the constant and gap dependence are carefully and explicitly tracked. We also investigate the possibility of solving quantum linear system problems using the related quantum approximate optimization algorithm with an optimal control protocol.