Quantum Speedups for Multiproposal MCMC

Area of Science:

• Quantum Computing
• Computational Statistics
• Statistical Physics

Background:

• Multiproposal Markov chain Monte Carlo (MCMC) algorithms enhance sampling efficiency for complex target distributions.
• Classical MCMC requires O(P) target evaluations per step with P proposals, limiting scalability.
• Prior quantum MCMC (QPMCMC) achieved O(sqrt(P)) evaluations but retained O(P) overall complexity due to proposal generation.

Purpose of the Study:

• Introduce a novel, faster quantum multiproposal MCMC strategy: QPMCMC2.
• Achieve significant computational speedups by reducing target evaluations and qubit requirements.
• Demonstrate the applicability and efficiency of QPMCMC2 on complex graphical models.

Main Methods:

• Developed QPMCMC2 utilizing a Tjelmeland distribution for proposal generation close to the input state.
• Analyzed QPMCMC2 complexity, showing O(1) target evaluations and O(log P) qubits for P proposals.
• Ensured the QPMCMC2 Markov kernel maintains detailed balance exactly and is fully explicit for graphical models.

Main Results:

• QPMCMC2 achieves a substantial reduction in computational cost compared to classical and previous quantum MCMC methods.
• The algorithm was successfully applied to Ising-type models on bacterial evolutionary networks.
• Significant speedups were observed in Bayesian ancestral trait reconstruction for a dataset of 248 Salmonella bacteria.

Conclusions:

• QPMCMC2 represents a significant advancement in quantum MCMC, offering unprecedented efficiency for sampling.
• The method's exact detailed balance and explicit nature broaden its applicability to various graphical models.
• QPMCMC2 shows great promise for accelerating complex statistical inference tasks in fields like evolutionary biology.