← Publications · Pablo Rodenas Ruiz

Quantum Circuits for the Metropolis–Hastings Algorithm

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

arXiv preprint (quant-ph, cond-mat.stat-mech, physics.chem-ph), 2025

arXiv:2506.11576 · PDF · BibTeX

Abstract

Quantum computers are expected to provide a speedup for Metropolis-Hastings (MH) simulations: Szegedy's quantization of a reversible Markov chain yields a quantum walk whose spectral gap is quadratically larger than that of the classical walk. However, existing generic methods require a number of qubits that scales with the computational complexity of the proposal-acceptance logic, which is undesirable for near-term fault-tolerant devices. We present a Szegedy quantum walk construction that directly follows the classical proposal-acceptance logic without further reversible-computing overhead, delivering an end-to-end quadratic speedup for Monte Carlo simulations while reducing qubit requirements.

Cite (BibTeX)

@misc{claudon2025quantum,
  title = {{Quantum Circuits for the Metropolis–Hastings Algorithm}},
  author = {Claudon, B. and Rodenas-Ruiz, P. and Piquemal, J.-P. and Monmarché, P.},
  year = {2025},
  month = jun,
  howpublished = {arXiv preprint (quant-ph, cond-mat.stat-mech, physics.chem-ph)},
  eprint = {2506.11576},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.11576},
  abstract = {Quantum computers are expected to provide a speedup for Metropolis-Hastings (MH) simulations: Szegedy's quantization of a reversible Markov chain yields a quantum walk whose spectral gap is quadratically larger than that of the classical walk. However, existing generic methods require a number of qubits that scales with the computational complexity of the proposal-acceptance logic, which is undesirable for near-term fault-tolerant devices. We present a Szegedy quantum walk construction that directly follows the classical proposal-acceptance logic without further reversible-computing overhead, delivering an end-to-end quadratic speedup for Monte Carlo simulations while reducing qubit requirements.}
}

View this paper on pablorodenas.me.