Stochastic Quantum Sampling for Non-Logconcave Distributions and
  Estimating Partition Functions
Guneykan Ozgul Xiantao Li Mehrdad Mahdavi Chunhao Wang
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.