← Publications · Pablo Rodenas Ruiz

Quantum Circuits for the Metropolis–Hastings Algorithm

B. Claudon, P. Rodenas-Ruiz, J.-P. Piquemal, P. Monmarché

Journal of Physics A: Mathematical and Theoretical, 2026

arXiv:2506.11576 · doi:10.1088/1751-8121/ae8983 · PDF · BibTeX

Abstract

Szegedy's quantization of a reversible Markov chain provides a quantum walk whose spectral gap is quadratically larger than that of the classical walk. Quantum computers are therefore expected to provide a speedup of Metropolis-Hastings (MH) simulations. Existing generic methods to implement the quantum walk require coherently computing the transition probabilities of the underlying Markov kernel. However, reversible computing methods require a number of qubits that scales with the complexity of the computation. This overhead is undesirable in near-term fault-tolerant quantum computing, where few logical qubits are available. In this work, we present a Szegedy quantum walk construction which follows the classical proposal-acceptance logic, and does not require further reversible computing methods. We also compare this construction with an alternative to Szegedy's approach which also provides a quadratic gap amplification. Since each step of the quantum walks uses a constant number of proposal and acceptance steps, we expect the end-to-end quadratic speedup to hold for MH Markov Chain Monte-Carlo simulations.

Cite (BibTeX)

@article{claudon2026quantum,
  title = {{Quantum Circuits for the Metropolis–Hastings Algorithm}},
  author = {Claudon, B. and Rodenas-Ruiz, P. and Piquemal, J.-P. and Monmarché, P.},
  year = {2026},
  month = jul,
  journal = {Journal of Physics A: Mathematical and Theoretical},
  publisher = {IOP Publishing},
  eprint = {2506.11576},
  archivePrefix = {arXiv},
  doi = {10.1088/1751-8121/ae8983},
  url = {https://arxiv.org/abs/2506.11576},
  abstract = {Szegedy's quantization of a reversible Markov chain provides a quantum walk whose spectral gap is quadratically larger than that of the classical walk. Quantum computers are therefore expected to provide a speedup of Metropolis-Hastings (MH) simulations. Existing generic methods to implement the quantum walk require coherently computing the transition probabilities of the underlying Markov kernel. However, reversible computing methods require a number of qubits that scales with the complexity of the computation. This overhead is undesirable in near-term fault-tolerant quantum computing, where few logical qubits are available. In this work, we present a Szegedy quantum walk construction which follows the classical proposal-acceptance logic, and does not require further reversible computing methods. We also compare this construction with an alternative to Szegedy's approach which also provides a quadratic gap amplification. Since each step of the quantum walks uses a constant number of proposal and acceptance steps, we expect the end-to-end quadratic speedup to hold for MH Markov Chain Monte-Carlo simulations.}
}

View this paper on pablorodenas.me.