We describe an improved version of the quantum simulation method based on the implementation of a truncated Taylor series of the evolution operator. The idea is to add an extra step to the previously known algorithm which implements an operator that corrects the weightings of the Taylor series. This way, the desired accuracy is achieved with an improvement in the overall complexity of the algorithm. This quantum simulation method is applicable to a wide range of Hamiltonians of interest, including to quantum chemistry problems.
We describe a simple, efficient method for simulating Hamiltonian dynamics on a quantum computer by approximating the truncated Taylor series of the evolution operator. Our method can simulate the time evolution of a wide variety of physical systems. As in another recent algorithm, the cost of our method depends only logarithmically on the inverse of the desired precision, which is optimal. However, we simplify the algorithm and its analysis by using a method for implementing linear combinations of unitary operations together with a robust form of oblivious amplitude amplification.
We describe a method to simulate Hamiltonian evolution on a quantum computer by repeatedly using a superposition of steps of a quantum walk, then applying a correction to the weightings for the numbers of steps of the quantum walk. This correction enables us to obtain complexity which is the same as the lower bound up to doublelogarithmic factors for all parameter regimes. The scaling of the query complexity is given. This technique should also be useful for improving the scaling of the Taylor series approach to simulation, which is relevant to applications such as quantum chemistry.
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.
A highly anticipated use of quantum computers is the simulation of complex quantum systems including molecules and other many-body systems. One promising method involves directly applying a linear combination of unitaries (LCU) to approximate a Taylor series by truncating after some order. Here we present an adaptation of that method, optimized for Hamiltonians with terms of widely varying magnitude, as is commonly the case in electronic structure calculations. We show that it is more efficient to apply LCU using a truncation that retains larger magnitude terms as determined by an iterative procedure. We obtain bounds on the simulation error for this generalized truncated Taylor method, and for a range of molecular simulations, we report these bounds as well as exact numerical results. We find that our adaptive method can typically improve the simulation accuracy by an order of magnitude, for a given circuit depth.
In quantum chemistry, the "electronic structure problem" refers to the process of numerically solving Schrodinger's equation for a given molecular system. These calculations rank among the most CPU-intensive computations that are performed nowadays, yet they are also crucial to the design of new drugs and materials. The idea behind quantum simulation of quantum chemistry is that a quantum computer could perform such calculations in a manner that is exponentially more efficient than what a classical computer could accomplish. In fact, quantum simulation is quite possibly the application most naturally suited to a quantum computer. In this work we introduce novel algorithms for the simulation of quantum chemistry, algorithms that are exponentially more precise than previous algorithms in the literature. Previous algorithms are based on the Trotter-Suzuki decomposition and scale like the inverse of the desired precision, while our algorithms represent the first practical application of the recently developed truncated Taylor series approach, and they achieve scaling that is logarithmic in the inverse of the precision. We explore algorithms for both second-quantized and first-quantized encodings of the chemistry Hamiltonian, where the second-quantized encoding requires
mathcalO(N) qubits for an
N spin-orbital system, and the highly compressed first-quantized encoding requires
mathcalO(eta) qubits, where
eta<<N is the number of electrons in the system. We first introduce a second-quantized algorithm that uses pre-computed molecular integrals, resulting in a gate count that scales like
widetildecalO(N8t). Next we introduce algorithms that compute molecular integrals on the fly by carefully discretizing these integrals. Indeed, figuring out how to evaluate the integrals in an efficient manner is one of the main challenges of applying the truncated Taylor series approach to the chemistry problem: the complexity of a general quantum algorithm is traditionally formulated in terms of the number of queries made to an oracle whose assumption we just assume, but in this case, we actually construct the oracle for our specific problem. The evaluation of the oracle itself requires evaluating molecular integrals, which adds additional complexity to an algorithm. We find that the gate count of the second-quantized on-the-fly algorithm scales like
widetildecalO(N5t). We also find that the first-quantized on-the-fly algorithm, which uses the configuration interaction (CI) matrix representation of the Hamiltonian, requires at most
widetildecalO(eta2N3t) gates. In general, the discovery of exponentially more precise algorithms will allow for the simulation of larger molecular systems than was previously possible under Trotter-based methods. In addition, the results here can be generalized to the simulation of other fermionic systems beyond the electronic structure problem.