  In this paper, we develop a Monte Carlo algorithm named the Frozen Gaussian
Sampling (FGS) to solve the semiclassical Schr\"odinger equation based on the
frozen Gaussian approximation. Due to the highly oscillatory structure of the
wave function, traditional mesh-based algorithms suffer from "the curse of
dimensionality", which gives rise to more severe computational burden when the
semiclassical parameter \(\ep\) is small. The Frozen Gaussian sampling
outperforms the existing algorithms in that it is mesh-free in computing the
physical observables and is suitable for high dimensional problems. In this
work, we provide detailed procedures to implement the FGS for both Gaussian and
WKB initial data cases, where the sampling strategies on the phase space
balance the need of variance reduction and sampling convenience. Moreover, we
rigorously prove that, to reach a certain accuracy, the number of samples
needed for the FGS is independent of the scaling parameter \(\ep\).
Furthermore, the complexity of the FGS algorithm is of a sublinear scaling with
respect to the microscopic degrees of freedom and, in particular, is
insensitive to the dimension number. The performance of the FGS is validated
through several typical numerical experiments, including simulating scattering
by the barrier potential, formation of the caustics and computing the
high-dimensional physical observables without mesh.
