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.
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.
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.
(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.
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 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.
Adiabatic quantum computing is a general framework for preparing eigenstates of Hamiltonians on quantum devices. However, its digital implementation requires an efficient Hamiltonian simulation subroutine, which may introduce extra computational overhead or complicated quantum control logic. In this work, we show that the time-step sizes in time discretization can be much larger than expected, and the overall complexity is greatly reduced. Remarkably, regardless of the general convergence order of the numerical method, we can choose a uniform time-step size independent of tolerated error and evolution time for sufficiently accurate simulation. Furthermore, with the boundary cancellation condition where the continuous diabatic errors are exponentially suppressed, we provide strong evidence for a superpolynomial convergence of first-order Trotter with uniform time-step size. We apply our analysis to the example of adiabatic unstructured search and show several preferable features of the Trotterized adiabatic approach: It can match the Grover lower bound, it does not require knowledge of the number of marked states, and its performance can be asymptotically comparable with that of the quantum approximate optimization algorithm.
In designing quantum control, it is generally required to simulate the controlled system evolution with a classical computer. However, computing the time evolution operator can be quite resource consuming since the total Hamiltonian is often hard to diagonalize. In this paper, we mitigate this issue by substituting the time evolution segments with their Trotter decompositions, which reduces the propagator into a combination of single-qubit operations and fixed-time system evolutions. The resulting procedure can provide substantial speed gain with acceptable costs in the propagator error. As a demonstration, we apply the proposed strategy to improve the efficiency of the gradient ascent pulse engineering algorithm for searching optimal control fields. Furthermore, we show that the higher-order Trotter decompositions can provide efficient Ans\"atze for the variational quantum algorithm, leading to improved performance in solving the ground-state problem. The strategy presented here is also applicable for many other quantum optimization and simulation tasks.