Abstract Quantum simulation is a rapidly advancing field poised to revolutionize our understanding of complex quantum systems by harnessing the unique capabilities of quantum computers. In this review, we present a concise overview of key developments in quantum simulation algorithms, with a focus on time-independent digital Hamiltonian simulation of quantum dynamics. We review seminal methods—from traditional Trotter formulas to techniques such as truncated Taylor series combined with the linear combination of unitaries, and quantum signal processing. Additionally, we examine error analyses and recent innovations that enhance the efficiency and accuracy of quantum simulations.
Abstract Quantum simulation is a rapidly advancing field poised to revolutionize our understanding of complex quantum systems by harnessing the unique capabilities of quantum computers. In this review, we present a concise overview of key developments in quantum simulation algorithms, with a focus on time-independent digital Hamiltonian simulation of quantum dynamics. We review seminal methods—from traditional Trotter formulas to techniques such as truncated Taylor series combined with the linear combination of unitaries, and quantum signal processing. Additionally, we examine error analyses and recent innovations that enhance the efficiency and accuracy of quantum simulations.
This chapter covers the quantum algorithmic primitive of Hamiltonian simulation, which aims to digitally simulate the evolution of a quantum state forward in time according to a Hamiltonian. There are several approaches to Hamiltonian simulation, which are best suited to different situations. We cover approaches for time-independent Hamiltonian simulation based on product formulas, the randomized compiling approach called qDRIFT, and quantum signal processing. We also discuss a method that leverages linear combination of unitaries and truncation of Taylor and Dyson series, which is well suited for time-dependent Hamiltonian simulation
Quantum simulation involves using a quantum system to study another quantum system. The proposal to simulate quantum physics using quantum mechanical devices, as outlined by Richard Feynman in 1982, stems from classical computers' challenges in simulating quantum systems. The pursuit of simulating complex quantum systems has led to the intersection of quantum mechanics and quantum computing. This offers new opportunities to understand and manipulate the quantum world. Central to describing quantum dynamics is the Hamiltonian operator H^, which governs the time evolution of physical systems and serves as the mathematical foundation for quantum simulations. This thesis explores the methodologies and advancements in simulating Hamiltonian operators on quantum computers, focusing on decomposing these operators into quantum gates and the efficiency gains over classical computational approaches. Initially, the thesis explains the fundamental theory and basics of quantum computing. Further it dives into the foundations of the Hamiltonian operator within quantum mechanics, highlighting its role in describing the dynamics of quantum systems. The complexity and high-dimensional nature of Hamiltonian matrices necessitate using quantum computers to simulate quantum phenomena accurately and efficiently. The process of simulating the Hamiltonian operator on a quantum computer involves a detailed examination of the strategies for decomposing the operator into a sequence of quantum gates. This decomposition is crucial for translating the abstract mathematical description of quantum systems into the physical operations of a quantum computer. By utilizing the principles of quantum mechanics, such as superposition and entanglement, quantum gates manipulate qubits to mimic the evolution of quantum states as the Hamiltonian operator dictates. Latter portions of the thesis are dedicated to comparing the efficiency of quantum simulations against traditional classical simulations and inspecting efficient quantum simulations. Quantum computers offer a polynomial or an exponential speedup for certain classes of problems, such as those involving highly entangled quantum states or requiring the simulation of complex quantum dynamics. This advantage is due to the quantum computer's ability to naturally represent and process quantum information - a task for which classical computers require exponential resources as the system size increases. The efficiency of simulating the Hamiltonian operator on a quantum computer is further enhanced through optimization techniques and algorithmic improvements. These include error mitigation strategies and the development of quantum algorithms tailored to specific types of Hamiltonian operators. The thesis presents a comprehensive analysis of these methods, demonstrating how they make quantum simulations more practical and accessible for scientific research and technological development. In conclusion this thesis is a literature review that examines the transformative potential of quantum simulations. By efficiently simulating the Hamiltonian operator on quantum computers researchers can explore quantum phenomena with precision, paving the way for breakthroughs in quantum physics, materials science, and beyond. The advancements in quantum computing technology and algorithmic approaches discussed here highlight the current capabilities and future explorations in the quantum realm.
(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.
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.
Abstract This chapter presents some quantum algorithms to simulate the dynamics of a quantum system, one of the most important applications of a quantum computer. We introduce the conditions for efficient simulation of Hamiltonian dynamics. We then present some Trotterization methods, in which the time evolution operator is approximated as a product of terms, each of which can be implemented by a quantum circuit at polynomial cost. We show high-order decompositions and illustrate the use of a Trotterization method to simulate sparse Hamiltonians. We discuss the Taylor series method and the qubitization method. The latter achieves optimal cost in simulation time and target accuracy. We conclude the chapter with a proof that simulating Hamiltonian dynamics is BQP-complete
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.