We present quantum algorithms for sampling from non-logconcave probability
distributions in the form of $\pi(x) \propto \exp(-\beta f(x))$. Here, $f$ can
be written as a finite sum $f(x):= \frac{1}{N}\sum_{k=1}^N f_k(x)$. Our
approach is based on quantum simulated annealing on slowly varying Markov
chains derived from unadjusted Langevin algorithms, removing the necessity for
function evaluations which can be computationally expensive for large data sets
in mixture modeling and multi-stable systems. We also incorporate a stochastic
gradient oracle that implements the quantum walk operators inexactly by only
using mini-batch gradients. As a result, our stochastic gradient based
algorithm only accesses small subsets of data points in implementing the
quantum walk. One challenge of quantizing the resulting Markov chains is that
they do not satisfy the detailed balance condition in general. Consequently,
the mixing time of the algorithm cannot be expressed in terms of the spectral
gap of the transition density, making the quantum algorithms nontrivial to
analyze. To overcome these challenges, we first build a hypothetical Markov
chain that is reversible, and also converges to the target distribution. Then,
we quantified the distance between our algorithm's output and the target
distribution by using this hypothetical chain as a bridge to establish the
total complexity. Our quantum algorithms exhibit polynomial speedups in terms
of both dimension and precision dependencies when compared to the best-known
classical algorithms.

我们提出了量子算法用于从非对数凹概率分布中采样，同时解决了求解大数据集中混合模型和多稳定系统时计算代价昂贵的函数评估问题。我们的量子算法在维度和精度依赖方面相对于已知的最佳经典算法展示了多项式加速。