Quantum simulation of real-space dynamics

Quantum 6, 860 (2022).

https://doi.org/10.22331/q-2022-11-17-860

Quantum simulation is a prominent application of quantum computers. While there is extensive previous work on simulating finite-dimensional systems, less is known about quantum algorithms for real-space dynamics. We conduct a systematic study of such algorithms. In particular, we show that the dynamics of a $d$-dimensional Schrödinger equation with $eta$ particles can be simulated with gate complexity $tilde{O}bigl(eta d F text{poly}(log(g’/epsilon))bigr)$, where $epsilon$ is the discretization error, $g’$ controls the higher-order derivatives of the wave function, and $F$ measures the time-integrated strength of the potential. Compared to the best previous results, this exponentially improves the dependence on $epsilon$ and $g’$ from $text{poly}(g’/epsilon)$ to $text{poly}(log(g’/epsilon))$ and polynomially improves the dependence on $T$ and $d$, while maintaining best known performance with respect to $eta$. For the case of Coulomb interactions, we give an algorithm using $eta^{3}(d+eta)Ttext{poly}(log(eta dTg’/(Deltaepsilon)))/Delta$ one- and two-qubit gates, and another using $eta^{3}(4d)^{d/2}Ttext{poly}(log(eta dTg’/(Deltaepsilon)))/Delta$ one- and two-qubit gates and QRAM operations, where $T$ is the evolution time and the parameter $Delta$ regulates the unbounded Coulomb interaction. We give applications to several computational problems, including faster real-space simulation of quantum chemistry, rigorous analysis of discretization error for simulation of a uniform electron gas, and a quadratic improvement to a quantum algorithm for escaping saddle points in nonconvex optimization.