  We propose a novel hybrid quantum computing strategy for parallel MCMC
algorithms that generate multiple proposals at each step. This strategy makes
the rate-limiting step within parallel MCMC amenable to quantum parallelization
by using the Gumbel-max trick to turn the generalized accept-reject step into a
discrete optimization problem. When combined with new insights from the
parallel MCMC literature, such an approach allows us to embed target density
evaluations within a well-known extension of Grover's quantum search algorithm.
Letting $P$ denote the number of proposals in a single MCMC iteration, the
combined strategy reduces the number of target evaluations required from
$\mathcal{O}(P)$ to $\mathcal{O}(P^{1/2})$. In the following, we review the
rudiments of quantum computing, quantum search and the Gumbel-max trick in
order to elucidate their combination for as wide a readership as possible.
