  We present quantum algorithms for the simulation of quantum systems in one
spatial dimension, which result in quantum speedups that range from
superpolynomial to polynomial. We first describe a method to simulate the
evolution of the quantum harmonic oscillator (QHO) based on a refined analysis
of the Trotter-Suzuki formula that exploits the Lie algebra structure. For
total evolution time $t$ and precision $\epsilon>0$, the complexity of our
method is $ O(\exp(\gamma \sqrt{\log(N/\epsilon)}))$, where $\gamma>0$ is a
constant and $N$ is the quantum number associated with an "energy cutoff" of
the initial state. Remarkably, this complexity is subpolynomial in
$N/\epsilon$. We also provide a method to prepare discrete versions of the
eigenstates of the QHO of complexity polynomial in $\log(N)/\epsilon$, where
$N$ is the dimension or number of points in the discretization. This method may
be of independent interest as it provides a way to prepare, e.g., quantum
states with Gaussian-like amplitudes. Next, we consider a system with a quartic
potential. Our numerical simulations suggest a method for simulating the
evolution of sublinear complexity $\tilde O(N^{1/3+o(1)})$, for constant $t$
and $\epsilon$. We also analyze complex one-dimensional systems and prove a
complexity bound $\tilde O(N)$, under fairly general assumptions. Our quantum
algorithms may find applications in other problems. As an example, we discuss
the fractional Fourier transform, a generalization of the Fourier transform
that is useful for signal analysis and can be formulated in terms of the
evolution of the QHO.
