  Multiproposal Markov chain Monte Carlo (MCMC) algorithms choose from multiple
proposals at each iteration in order to sample from challenging target
distributions more efficiently. Recent work demonstrates the possibility of
quadratic quantum speedups for one such multiproposal MCMC algorithm. Using $P$
proposals, this quantum parallel MCMC QPMCMC algorithm requires only
$\mathcal{O}(\sqrt{P})$ target evaluations at each step. Here, we present a
fast new quantum multiproposal MCMC strategy, QPMCMC2, that only requires
$\mathcal{O}(1)$ target evaluations and $\mathcal{O}(\log P)$ qubits. Unlike
its slower predecessor, the QPMCMC2 Markov kernel (1) maintains detailed
balance exactly and (2) is fully explicit for a large class of graphical
models. We demonstrate this flexibility by applying QPMCMC2 to novel Ising-type
models built on bacterial evolutionary networks and obtain significant speedups
for Bayesian ancestral trait reconstruction for 248 observed salmonella
bacteria.
