  Quantum computation is expected to accelerate certain computational task over
classical counterpart. Its most primitive advantage is its ability to sample
from classically intractable probability distributions. A promising approach to
make use of this fact is the so-called quantum-enhanced Markov chain Monte
Carlo (MCMC) [D. Layden, et al., arXiv:2203.12497 (2022)] which uses outputs
from quantum circuits as the proposal distributions. In this work, we propose
the use of Quantum Alternating Operator Ansatz (QAOA) for quantum-enhanced MCMC
and provide a strategy to optimize its parameter to improve convergence speed
while keeping its depth shallow. The proposed QAOA-type circuit is designed to
satisfy the specific constraint which quantum-enhanced MCMC requires with
arbitrary parameters. Through our extensive numerical analysis, we find a
correlation in certain parameter range between an experimentally measurable
value, acceptance rate of MCMC, and the spectral gap of the MCMC transition
matrix, which determines the convergence speed. This allows us to optimize the
parameter in the QAOA circuit and achieve quadratic speedup in convergence.
Since MCMC is used in various areas such as statistical physics and machine
learning makes, this work represents an important step toward realizing
practical quantum advantage with currently available quantum computers through
quantum-enhanced MCMC.
