Seminar: Quantum Speedup in Machine Learning, the Monte Carlo Way
By Massimiliano Incudini

Massimiliano Incudini will give a seminar on Tuesday 10/11 at 2pm online.

Title: Quantum Speedup in Machine Learning, the Monte Carlo Way

Can quantum computers make machine learning faster? Despite theoretical speedups, demonstrating a practical advantage remains challenging, particularly when accounting for the costs of fault-tolerant quantum computation.

In this talk, I will explore this question through Markov chain Monte Carlo, a fundamental tool for sampling from complex probability distributions. Unlike conventional Monte Carlo methods, which explore probability distributions through classically generated moves, quantum computers can exploit quantum dynamics to propose transitions between configurations. These proposals can help the algorithm escape regions where classical sampling becomes slow [1]. We incorporate the entire Metropolis procedure into a coherent quantum algorithm, achieving a speedup beyond the conventional quadratic limit. Numerical results on dense Ising models suggest a heuristic speedup with polynomial degree as high as six [2]. Finally, I will discuss how these gains translate into projected wall-clock execution times, comparing fault-tolerant quantum implementations with optimized CPU, GPU, and FPGA alternatives.

I will also discuss the potential implications for machine learning, particularly for training energy-based generative models, where efficient sampling is a central computational challenge.

[1] D. Layden, G. Mazzola et al. Quantum-enhanced Markov chain Monte Carlo. Nature 619, 282–287 (2023). [2] M.I. and G. Mazzola. Practical advantage beyond the quadratic speedup limit with fully-quantum walks. Preprint (2026).