  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 $\frac{m}{2}\dot{x}^2 - V(x)$. This
Lagrangian path integral algorithm is based on a new rigorous derivation of a
discrete version of the Lagrangian path integral. Our first Hamiltonian path
integral method breaks up the paths into short timesteps. 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)}/\epsilon^{o(1)}$ for simulation time
$t$ and error $\epsilon$. The second approach uses long-time path integrals for
near-adiabatic systems and has query complexity that scales as
$O(1/\sqrt{\epsilon})$ if the energy eigenvalue gaps and simulation time is
sufficiently long. Finally, we show that our Lagrangian simulation algorithm
requires a number of queries to an oracle that computes the discrete Lagrangian
that scales, in the continuum limit, as $\widetilde{O}(t^2/\epsilon)$ 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.
