Quantum simulations of one dimensional quantum systems

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.