Given a quantum Hamiltonian and its evolution time, the corresponding unitary evolution operator can be constructed in many different ways, corresponding to different trajectories between the desired end-points and different series expansions. A choice among these possibilities can then be made to obtain the best computational complexity and control over errors. It is shown how a construction based on Grover's algorithm scales linearly in time and logarithmically in the error bound, and is exponentially superior in error complexity to the scheme based on the straightforward application of the Lie–Trotter formula. The strategy is then extended first to simulation of any Hamiltonian that is a linear combination of two projection operators, and then to any local efficiently computable Hamiltonian. The key feature is to construct an evolution in terms of the largest possible steps instead of taking small time steps. Reflection operations and Chebyshev expansions are used to efficiently control the total error on the overall evolution, without worrying about discretization errors for individual steps. We also use a digital implementation of quantum states that makes linear algebra operations rather simple to perform.
Given a quantum Hamiltonian and its evolution time, the corresponding unitary evolution operator can be constructed in many different ways, corresponding to different trajectories between the desired end-points and different series expansions. A choice among these possibilities can then be made to obtain the best computational complexity and control over errors. It is shown how a construction based on Grover's algorithm scales linearly in time and logarithmically in the error bound, and is exponentially superior in error complexity to the scheme based on the straightforward application of the Lie–Trotter formula. The strategy is then extended first to simulation of any Hamiltonian that is a linear combination of two projection operators, and then to any local efficiently computable Hamiltonian. The key feature is to construct an evolution in terms of the largest possible steps instead of taking small time steps. Reflection operations and Chebyshev expansions are used to efficiently control the total error on the overall evolution, without worrying about discretization errors for individual steps. We also use a digital implementation of quantum states that makes linear algebra operations rather simple to perform.
Given a quantum Hamiltonian and its evolution time, the corresponding unitary evolution operator can be constructed in many different ways, corresponding to different trajectories between the desired end-points. A choice among these trajectories can then be made to obtain the best computational complexity and control over errors. It is shown how a construction based on Grover's algorithm scales linearly in time and logarithmically in error bound, and is exponentially superior in error complexity to the scheme based on straightforward application of the Lie-Trotter formula. The strategy is then extended to simulation of any Hamiltonian that is a linear combination of two projection operators. The key feature is to construct an evolution in terms of reflection operators instead of taking small time steps. The reflection operation amounts to taking the largest possible step consistent with unitarity in the specified direction. Though that makes discretisation error for individual steps large, the total error on the overall evolution can be efficiently controlled.
We provide a quantum method for simulating Hamiltonian evolution with complexity polynomial in the logarithm of the inverse error. This is an exponential improvement over existing methods for Hamiltonian simulation. In addition, its scaling with respect to time is close to linear, and its scaling with respect to the time derivative of the Hamiltonian is logarithmic. These scalings improve upon most existing methods. Our method is to use a compressed Lie-Trotter formula, based on recent ideas for efficient discrete-time simulations of continuous-time quantum query algorithms.
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.
(Suzuki-)Trotter decompositions, splitting methods, (Lie) product formulae... The most common numerical methods for the time evolution of quantum systems come with many names. And they are used practically everywhere with applications ranging from the solution of classical equations of motion and various Monte Carlo simulations to the real and imaginary time evolution on classical as well as quantum computers. Here we review the state of the art of said methods, focussing especially on the progress made over the last few years. We highlight recently discovered efficient time evolution algorithms and explain how best to use them in practice. A central part of this work is the estimation of error bounds that has improved greatly within the past decade. The relevance of time evolution methods for quantum computing is discussed with a focus on noisy hardware. Finally, a comprehensive overview of generalisations, related methods and alternatives to Trotterization is provided. This includes time-dependent Hamiltonian dynamics, processed methods, multi-product formulae, symplectic integrators, TDVP for tensor networks, quantum signal processing, Crouch-Grossman methods and more. The overall perspective in this work is that of a theoretical physicist. All mathematical proofs as well as some technical details are omitted for easier readability. Instead, this review serves as a hands-on guide and, of course, as a starting point for references that provide further details.
In this work we propose an approach for implementing time-evolution of a quantum system using product formulas. The quantum algorithms we develop have provably better scaling (in terms of gate complexity and circuit depth) than a naive application of well-known Trotter formulas, for systems where the evolution is determined by a Hamiltonian with different energy scales (i.e., one part is "large" and another part is "small"). Our algorithms generate a decomposition of the evolution operator into a product of simple unitaries that are directly implementable on a quantum computer. Although the theoretical scaling is suboptimal compared with state-of-the-art algorithms (e.g., quantum signal processing), the performance of the algorithms we propose is highly competitive in practice. We illustrate this via extensive numerical simulations for several models. For instance, in the strong-field regime of the 1D transverse-field Ising model, our algorithms achieve an improvement of one order of magnitude in both the system size and evolution time that can be simulated with a fixed budget of 1000 arbitrary 2-qubit gates, compared with standard Trotter formulas.
Digital quantum simulation of many-body dynamics relies on Trotterization to decompose the target time evolution into elementary quantum gates operating at a fixed equidistant time discretization. Recent advances have outlined protocols enabling more efficient adaptive Trotter protocols, which have been shown to exhibit a controlled error in the dynamics of local observables and correlation functions. However, it has remained open to which extent the errors on the actual generator of the dynamics, i.e., the target many-body Hamiltonian, remain controlled. Here, we propose to use quantum Hamiltonian learning to numerically obtain the effective Hamiltonian and apply it on the recently introduced ADA-Trotter algorithm as a concrete demonstration. Our key observation is that deviations from the target generator remain bounded on all simulation times. This result suggests that the ADA-Trotter not only generates reliable digital quantum simulation of local dynamics, but also controllably approximates the global quantum state of the target system. Our proposal is sufficiently general and readily applicable to other adaptive time-evolution algorithms.