In this thesis, we present three innovations that can be used to simulate quantum dynamics on both quantum and classical computers. Our primary innovation is an efficient quantum algorithm for simulating time-dependent Hamiltonian evolution of general input states on a quantum computer. Given conditions on the smoothness of the Hamiltonian, the complexity of the algorithm is close to linear in the evolution time, and therefore is comparable to algorithms for time-independent Hamiltonians. In addition, we show how the complexity can be reduced by optimizing the time steps. The complexity of the algorithm is quantified by calls to an oracle, which yields information about the Hamiltonian. In contrast to previous work, which allowed an oracle query to yield an arbitrary number of bits or qubits, we assign a cost for each bit or qubit accessed, revealing hitherto unnoticed simulation costs. We also account for discretization errors in the time and the representation of the Hamiltonian. This work is enabled by our development of a decomposition scheme based on Lie-Trotter- Suzuki product formulae for ordered operator exponentials. We show, by counterexample, that Lie-Trotter-Suzuki approximations may be lower order than expected when applied to problems that have singularities or discontinuous derivatives of appropriate order. We address this problem by presenting a set of criteria that is sufficient for the validity of these approximations, prove convergence and provide upper bounds for the approximation error. We also provide a new analysis of the evolution of quantum adiabatic systems in this thesis. Our work contains the tightest upper bounds that are currently known, and the first tight lower bounds, for the error in the adiabatic approximation applied to fixed Hamiltonians in the limit of slow evolution. We use our results to address the Marzlin- Sanders counterexample Hamiltonian. Specifically, we provide sufficiency conditions for the validity of the adiabatic approximation and demonstrate that the Marzlin-Sanders counterexample fails to satisfy them. We also find a new class of time-dependent Hamiltonians that are related to the Marzlin0Sanders counterexample Hamiltonian, but nonetheless obey the adiabatic approximation for sufficiently slow evolutions.
In this thesis, we present three innovations that can be used to simulate quantum dynamics on both quantum and classical computers. Our primary innovation is an efficient quantum algorithm for simulating time-dependent Hamiltonian evolution of general input states on a quantum computer. Given conditions on the smoothness of the Hamiltonian, the complexity of the algorithm is close to linear in the evolution time, and therefore is comparable to algorithms for time-independent Hamiltonians. In addition, we show how the complexity can be reduced by optimizing the time steps. The complexity of the algorithm is quantified by calls to an oracle, which yields information about the Hamiltonian. In contrast to previous work, which allowed an oracle query to yield an arbitrary number of bits or qubits, we assign a cost for each bit or qubit accessed, revealing hitherto unnoticed simulation costs. We also account for discretization errors in the time and the representation of the Hamiltonian. This work is enabled by our development of a decomposition scheme based on Lie-Trotter- Suzuki product formulae for ordered operator exponentials. We show, by counterexample, that Lie-Trotter-Suzuki approximations may be lower order than expected when applied to problems that have singularities or discontinuous derivatives of appropriate order. We address this problem by presenting a set of criteria that is sufficient for the validity of these approximations, prove convergence and provide upper bounds for the approximation error. We also provide a new analysis of the evolution of quantum adiabatic systems in this thesis. Our work contains the tightest upper bounds that are currently known, and the first tight lower bounds, for the error in the adiabatic approximation applied to fixed Hamiltonians in the limit of slow evolution. We use our results to address the Marzlin- Sanders counterexample Hamiltonian. Specifically, we provide sufficiency conditions for the validity of the adiabatic approximation and demonstrate that the Marzlin-Sanders counterexample fails to satisfy them. We also find a new class of time-dependent Hamiltonians that are related to the Marzlin0Sanders counterexample Hamiltonian, but nonetheless obey the adiabatic approximation for sufficiently slow evolutions.
We explicitly show how to simulate time-dependent sparse Hamiltonian evolution on a quantum computer, with complexity that is close to linear in the evolution time. The complexity also depends on the magnitude of the derivatives of the Hamiltonian. We propose a range of techniques to simulate Hamiltonians with badly behaved derivatives. These include using adaptive time steps, adapting the order of the integrators, and omitting regions about discontinuities. The complexity of the algorithm is quantified by calls to an oracle, which yields information about the Hamiltonian, and accounts for all computational resources. We explicitly determine the number of bits of output that this oracle needs to provide, and show how to efficiently perform the required 1-sparse unitary operations using these bits. We also account for discretization error in the time, as well as accounting for Hamiltonians that are a sum of terms that are sparse in different bases.
In adiabatic quantum computing the aim is to track an eigenstate as the Hamiltonian changes. In the usual setup this is achieved using the natural time-dependent Hamiltonian evolution of the system and the main technical tool is the adiabatic theorem. We propose several alternative processes that achieve the same goal, but can easily be implemented on a gate-based quantum computer without the overhead of simulating time-dependent Hamiltonian evolution. We give a general framework for deriving `adiabatic' theorems for these processes.
As an application, we give various algorithms for solving the Quantum Linear Systems Problem (QLSP) with optimal scaling in the condition number. One of these algorithms was previously developed in [Cunningham, Roland 2024] and another can be seen as a randomised version of the discrete adiabatic algorithm of [Costa et al. 2022].
We also describe versions of Trotterisation in our framework, which allows several results from [An et al. 2025] to be reproduced in a randomised setting. In particular, bounds on the Trotter error in terms of the fidelity are obtained that are asymptotically better than the standard bounds.
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.
With quantum computers on the horizon, it is essential to understand what problems they can be used to solve. One potential application is simulating quantum systems, in particular, systems with many interacting electrons. However, there is a disparity between the computational resources required to study these problems and the capabilities of modern experimental quantum devices. In this thesis, we make progress toward closing this gap by reducing the cost of quantum simulation of quantum chemistry on a number of fronts. In the first half, we develop three improved quantum simulation algorithms by approximating time evolution under the Hamiltonian using a truncated Taylor series rather than the Trotter-Suzuki decomposition. We do this first for the molecular electronic structure Hamiltonian in two representations, obtaining asymptotic improvements in terms of both the number of orbitals and the required precision. We also apply the truncated Taylor series paradigm to quantum simulation in real space, where we consider simulation of general wave functions discretized on a uniform grid. In the second half, by working with Hamiltonians tailored specifically to quantum algorithms, we demonstrate that Trotter steps of the electronic structure Hamiltonian can be simulated in exactly N depth and with only linear connectivity, where N is the number of spin-orbitals. This resolves the problem of non-locality in fermion-to-qubit mappings, and has wide-ranging applications for variational and phase estimation-based quantum simulation of quantum chemistry. We further study this algorithm on an error-corrected quantum computer using the surface code. Benchmarking it alongside other product formula approaches, we show that quantum simulation of scientifically important instances of the electronic structure problem that are classically intractable can be performed with only a few hundred thousand physical qubits and fewer than one billion costly fault-tolerant gates. Finally, we study the effect of using randomized Hamiltonians in iterative phase estimation, and how this allows us to reduce the costs of simulation as well as to exploit knowledge of the ground state in how we design our simulation algorithm.
The discovery of adiabatic quantum computing has revealed a need for rigorously proven bounds for the error in the adiabatic approximation. We present in this paper, a rigorous and elementary derivation of upper and lower bounds on the error incurred from using the adiabatic approximation for quantum systems that can be used to assess the runtime of adiabatic algorithms. Our bounds are often asymptotically tight in the limit of slow evolution for fixed Hamiltonians, and are used to provide sufficient conditions for the application of the adiabatic approximation. We show that our sufficiency criteria exclude the Marzlin–Sanders counterexample from the class of Hamiltonians that obey the adiabatic approximation. Finally, we demonstrate the existence of classes of Hamiltonians that resemble the Marzlin–Sanders counterexample Hamiltonian, but also obey the adiabatic approximation.
Compared with time-independent Hamiltonians, the dynamics of generic quantum Hamiltonians H ( t ) are complicated by the presence of time ordering in the evolution operator. In the context of digital quantum simulation, this difficulty prevents a direct adaptation of many time-independent simulation algorithms for time-dependent simulation. However, there exists a framework within the theory of dynamical systems that eliminates time ordering by adding a “clock” degree of freedom. In this work, we provide a computational framework, based on this reduction, for encoding time-dependent dynamics as time-independent systems. As a result, we make two advances in digital Hamiltonian simulation. First, we create a time-dependent simulation algorithm based on performing qubitization on the augmented clock system and, in doing so, provide the first qubitization-based approach to time-dependent Hamiltonians that goes beyond Trotterization of the ordered exponential. Second, we define a natural generalization of multiproduct formulas for time-ordered exponentials and then propose and analyze an algorithm based on these formulas. Unlike other algorithms of similar accuracy, the multiproduct approach achieves commutator scaling, meaning that this method outperforms existing methods for physically local time-dependent Hamiltonians with sufficient smoothness. Our work reduces the disparity between time-dependent and time-independent simulation and indicates a step toward optimal quantum simulation of time-dependent Hamiltonians. Published by the American Physical Society 2024