Efficient quantum simulation algorithms in the path integral formulation

Abstract We provide a new paradigm for quantum simulation that is based on path integration that allows quantum speedups to be observed for problems that are more naturally expressed using the path integral formalism rather than the conventional sparse Hamiltonian formalism. We provide two novel quantum algorithms based on Hamiltonian versions of the path integral formulation and another for Lagrangians of the form Σ γ m γ /2 ẋ γ 2 - V(x), while avoiding the sign problems that preclude efficient Monte-Carlo algorithms for such problems. The Lagrangian path integral algorithm is based on a new rigorous derivation of a discrete version of the Lagrangian path integral. We show that for the time evolution of a system with η particles in D + 1 dimensions for time T, our Lagrangian simulation algorithm requires a number of queries to an oracle that computes the discrete Lagrangian that scales in the continuum limit as O(ηDT 2 /ϵ), if V (x) is bounded and finite and the wave function obeys appropriate position and momentum cutoffs. This shows that Lagrangian dynamics can be efficiently simulated on quantum computers and opens up the possibility for quantum field theories for which the Hamiltonian is unknown to be efficiently simulated on quantum computers. Our first Hamiltonian path integral method breaks up the paths into short time steps. It is efficient under appropriate sparsity assumptions and requires a number of queries to oracles that give the eigenvalues and overlaps between the eigenvectors of the Hamiltonian terms that scales as t o(1) /ϵ o(1) for simulation time t and error ϵ. The second approach uses long-time path integrals for near-adiabatic systems and has query complexity that scales as O(1/ √ ϵ) if the energy eigenvalue gaps and simulation time is sufficiently long.