Simulating the Hamiltonian dynamics of quantum systems is one of the most promising applications of digital quantum computers. In this dissertation, we develop an understanding of quantum simulation algorithms concerning their design, analysis, implementation, and application. We implement three leading simulation algorithms, employing diverse techniques to tighten their error analyses and optimize circuit implementations. We produce concrete resource estimates for simulating a Heisenberg spin system, a problem arising in condensed matter physics that is otherwise difficult to solve on a classical computer. The resulting circuits are orders of magnitude smaller than those for the simplest classically-infeasible instances of factoring and quantum chemistry, suggesting the simulation of spin systems as a promising candidate for an early demonstration of practical quantum computation. We design new simulation algorithms by using classical randomness. We show that by simply randomizing how the terms in the Hamiltonian are ordered, one can prove stronger bounds for product formulas and thereby give more efficient quantum simulations. We also develop a classical sampler for time-dependent Hamiltonians, using which we give a simulation algorithm that substantially improves over previous approaches when the Hamiltonian varies significantly with time. We propose a general theory to analyzing product formulas, an approach to quantum simulation widely used in experimental demonstrations but whose error scaling was poorly understood. Our approach directly exploits the commutativity of Hamiltonian, overcoming the limitations of prior error analyses. We prove new speedups of product formulas for simulating many quantum systems, including simulations of nearest-neighbor lattice systems, second-quantized plane-wave electronic structure, $k$-local Hamiltonians, rapidly decaying power-law interactions, and clustered Hamiltonians, nearly matching or even outperforming the best previous results in quantum simulation. We accompany our analysis with numerical calculation, which suggests that the bounds also have nearly tight constant prefactors. We identify applications of quantum simulation to designing other quantum algorithms and improving quantum Monte Carlo methods. We develop an algorithmic framework ``quantum singular value transformation'' using techniques from quantum simulation and apply it to implement principal component regression. We also apply our new analysis of product formulas and obtain improved quantum Monte Carlo simulations of the transverse field Ising model and quantum ferromagnets.
Simulating the Hamiltonian dynamics of quantum systems is one of the most promising applications of digital quantum computers. In this dissertation, we develop an understanding of quantum simulation algorithms concerning their design, analysis, implementation, and application. We implement three leading simulation algorithms, employing diverse techniques to tighten their error analyses and optimize circuit implementations. We produce concrete resource estimates for simulating a Heisenberg spin system, a problem arising in condensed matter physics that is otherwise difficult to solve on a classical computer. The resulting circuits are orders of magnitude smaller than those for the simplest classically-infeasible instances of factoring and quantum chemistry, suggesting the simulation of spin systems as a promising candidate for an early demonstration of practical quantum computation. We design new simulation algorithms by using classical randomness. We show that by simply randomizing how the terms in the Hamiltonian are ordered, one can prove stronger bounds for product formulas and thereby give more efficient quantum simulations. We also develop a classical sampler for time-dependent Hamiltonians, using which we give a simulation algorithm that substantially improves over previous approaches when the Hamiltonian varies significantly with time. We propose a general theory to analyzing product formulas, an approach to quantum simulation widely used in experimental demonstrations but whose error scaling was poorly understood. Our approach directly exploits the commutativity of Hamiltonian, overcoming the limitations of prior error analyses. We prove new speedups of product formulas for simulating many quantum systems, including simulations of nearest-neighbor lattice systems, second-quantized plane-wave electronic structure, k-local Hamiltonians, rapidly decaying power-law interactions, and clustered Hamiltonians, nearly matching or even outperforming the best previous results in quantum simulation. We accompany our analysis with numerical calculation, which suggests that the bounds also have nearly tight constant prefactors. We identify applications of quantum simulation to designing other quantum algorithms and improving quantum Monte Carlo methods. We develop an algorithmic framework ``quantum singular value transformation'' using techniques from quantum simulation and apply it to implement principal component regression. We also apply our new analysis of product formulas and obtain improved quantum Monte Carlo simulations of the transverse field Ising model and quantum ferromagnets.
With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, using diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically infeasible instances of factoring and quantum chemistry, bringing practical quantum computation closer to reality.
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.
Quantum computation appears to offer significant advantages over classical computation and this has generated a tremendous interest in the field. In this thesis we study the application of quantum computers to computational problems in science and engineering, and to combinatorial optimization problems. We outline the results below. Algorithms for scientific computing require modules, i.e., building blocks, implementing elementary numerical functions that have well-controlled numerical error, are uniformly scalable and reversible, and that can be implemented efficiently. We derive quantum algorithms and circuits for computing square roots, logarithms, and arbitrary fractional powers, and derive worst-case error and cost bounds. We describe a modular approach to quantum algorithm design as a first step towards numerical standards and mathematical libraries for quantum scientific computing. A fundamental but computationally hard problem in physics is to solve the time-independent Schrödinger equation. This is accomplished by computing the eigenvalues of the corresponding Hamiltonian operator. The eigenvalues describe the different energy levels of a system. The cost of classical deterministic algorithms computing these eigenvalues grows exponentially with the number of system degrees of freedom. The number of degrees of freedom is typically proportional to the number of particles in a physical system. We show an efficient quantum algorithm for approximating a constant number of low-order eigenvalues of a Hamiltonian using a perturbation approach. We apply this algorithm to a special case of the Schrödinger equation and show that our algorithm succeeds with high probability, and has cost that scales polynomially with the number of degrees of freedom and the reciprocal of the desired accuracy. This improves and extends earlier results on quantum algorithms for estimating the ground state energy. We consider the simulation of quantum mechanical systems on a quantum computer. We show a novel divide and conquer approach for Hamiltonian simulation. Using the Hamiltonian structure, we can obtain faster simulation algorithms. Considering a sum of Hamiltonians we split them into groups, simulate each group separately, and combine the partial results. Simulation is customized to take advantage of the properties of each group, and hence yield refined bounds to the overall simulation cost. We illustrate our results using the electronic structure problem of quantum chemistry, where we obtain significantly improved cost estimates under mild assumptions. We turn to combinatorial optimization problems. An important open question is whether quantum computers provide advantages for the approximation of classically hard combinatorial problems. A promising recently proposed approach of Farhi et al. is the Quantum Approximate Optimization Algorithm (QAOA). We study the application of QAOA to the Maximum Cut problem, and derive analytic performance bounds for the lowest circuit-depth realization, for both general and special classes of graphs. Along the way, we develop a general procedure for analyzing the performance of QAOA for other problems, and show an example demonstrating the difficulty of obtaining similar results for greater depth. We show a generalization of QAOA and its application to wider classes of combinatorial optimization problems, in particular, problems with feasibility constraints. We introduce the Quantum Alternating Operator Ansatz, which utilizes more general unitary operators than the original QAOA proposal. Our framework facilitates low-resource implementations for many applications which may be particularly suitable for early quantum computers. We specify design criteria, and develop a set of results and tools for mapping diverse problems to explicit quantum circuits. We derive constructions for several important prototypical problems including Maximum Independent Set, Graph Coloring, and the Traveling Salesman problem, and show appealing resource cost estimates for their implementations.
Computer simulation is central to understanding the behaviour of matter. Yet, more than a century after the development of quantum theory, first-principles simulation of chemistry remains a daunting challenge, owing to the exponential growth in memory required to represent interacting quantum particles such as electrons in molecules. Quantum computing offers, in principle, a fundamentally more efficient paradigm for simulating quantum systems, with quantum chemistry often cited as a flagship application. However, many quantum algorithms face intrinsic limitations, and any genuine quantum advantage must surpass the strong baseline set by decades of progress in classical algorithms and hardware. While classical methods often suffice for simulating weakly correlated systems, systems with many strongly correlated electrons remain a challenge for both classical and quantum approaches. In this thesis, we develop quantum algorithms for solving the time-independent Schrödinger equation, with a focus on molecular systems with strongly correlated electrons. We introduce a framework for identifying a compact set of states that parametrise the many-body wavefunction by capturing the correlation due to spin coupling between localised electrons. This representation requires very few variational parameters but incurs a very high memory cost on classical computers. To overcome this, we design quantum circuits that efficiently prepare such states by exploiting their symmetry, encoding the dominant entanglement structure of electronic wavefunctions into the initial qubit states. Through theoretical analysis and classical simulations of quantum computers, we show that this substantially reduces the quantum resources required to accurately compute ground- and excitedstate properties. Finally, we develop an approach for approximating the optimal ansatz within the variational quantum eigensolver, an algorithm designed for near-term quantum devices. Our method constructs wavefunctions from products of symmetrypreserving unitary operators and couples discrete and continuous optimisation to yield highly compact representations of strongly correlated electrons using shallow quantum circuits. Together, these results establish complementary directions for embedding problemspecific structure into quantum simulation algorithms, advancing the practical simulation of strongly correlated electrons.
Trotter product formulas are a fundamental class of methods for Hamiltonian simulation, particularly attractive due to their low qubit requirements. However, they are often overlooked for use with fault-tolerant quantum algorithms, because of their perceived higher gate counts and the difficulty of estimating Trotter error. Here, we introduce Symmetry-Protected Randomized near-Integrable Trotter (SPRINT) formulas, a framework for building optimized product formulas for electronic structure Hamiltonians widely used in quantum chemistry. SPRINT integrates a generalization of classical near-integrability, randomization, symmetry protection, use of QROM, and other techniques into a thoroughly optimized methodology for Hamiltonian simulation. When applied to concrete simulation tasks, we find SPRINT leads to substantial reduction in gate count compared to previous approaches. Alongside SPRINT, we introduce and analyze a Generalized Rank Decomposition (GRADE) of electronic Hamiltonians that generalizes previous factorization methods. We apply these techniques to the task of simulating the X-ray absorption spectrum of Li4Mn2O, a candidate battery cathode material, leveraging recent advances in tight Trotter error estimation to carefully identify the best version of SPRINT for this problem. Using a Trotter error estimation tool developed in the PennyLane software platform, we show that SPRINT reduces the Toffoli gate cost by a factor of 4.5 relative to the previous state of the art for this problem, with a gate cost only ×2.5 higher than qubitization, while requiring a dramatic ×5.5 fewer logical qubits. These results establish well-designed Trotter product formulas as an attractive Hamiltonian simulation method for industrially relevant problems in chemistry and materials science.
We establish tight connections between entanglement entropy and the approximation error in Trotter-Suzuki product formulas for Hamiltonian simulation. Product formulas remain the workhorse of quantum simulation on near-term devices, yet standard error analyses yield worst-case bounds that can vastly overestimate the resources required for structured problems. For systems governed by geometrically local Hamiltonians with maximum entanglement entropy Smax across all bipartitions, we prove that the first-order Trotter error scales as O(t2Smaxpolylog(n)/r) rather than the worst-case O(t2n/r), where n is the system size and r is the number of Trotter steps. This yields improvements of Ω~(n2) for one-dimensional area-law systems and Ω~(n3/2) for two-dimensional systems. We extend these bounds to higher-order Suzuki formulas, where the improvement factor involves 2pS∗/2 for the p-th order formula. We further establish a separation result demonstrating that volume-law entangled systems fundamentally require Ω~(n) more Trotter steps than area-law systems to achieve the same precision. This separation is tight up to logarithmic factors. Our analysis combines Lieb-Robinson bounds for locality, tensor network representations for entanglement structure, and novel commutator-entropy inequalities that bound the expectation value of nested commutators by the Schmidt rank of the state. These results have immediate applications to quantum chemistry, condensed matter simulation, and resource estimation for fault-tolerant quantum computing.