  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.
