Solving the time-dependent Schr\"odinger equation is an important application area for quantum algorithms. We consider Schr\"odinger's equation in the semi-classical regime. Here the solutions exhibit strong multiple-scale behavior due to a small parameter $\hbar$, in the sense that the dynamics of the quantum states and the induced observables can occur on different spatial and temporal scales. Such a Schr\"odinger equation finds many applications, including in Born-Oppenheimer molecular dynamics and Ehrenfest dynamics. This paper considers quantum analogues of pseudo-spectral (PS) methods on classical computers. Estimates on the gate counts in terms of $\hbar$ and the precision $\varepsilon$ are obtained. It is found that the number of required qubits, $m$, scales only logarithmically with respect to $\hbar$. When the solution has bounded derivatives up to order $\ell$, the symmetric Trotting method has gate complexity $\mathcal{ O}\Big({ (\varepsilon \hbar)^{ -\frac12} \mathrm{ polylog}(\varepsilon^{ -\frac{ 3}{ 2\ell}} \hbar^{ -1-\frac{ 1}{ 2\ell}})}\Big),$ provided that the diagonal unitary operators in the pseudo-spectral methods can be implemented with $\mathrm{ poly}(m)$ operations. When physical observables are the desired outcomes, however, the step size in the time integration can be chosen independently of $\hbar$. The gate complexity in this case is reduced to $\mathcal{ O}\Big({ \varepsilon^{ -\frac12} \mathrm{ polylog}( \varepsilon^{ -\frac3{ 2\ell}} \hbar^{ -1} )}\Big),$ with $\ell$ again indicating the smoothness of the solution.
Categories: quant-ph cs.NA math.NA physics.comp-ph