Quantum Circuits for the Metropolis-Hastings Algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916054245048320 |
|---|---|
| author | Claudon, Baptiste Rodenas-Ruiz, Pablo Piquemal, Jean-Philip Monmarché, Pierre |
| author_facet | Claudon, Baptiste Rodenas-Ruiz, Pablo Piquemal, Jean-Philip Monmarché, Pierre |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_11576 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum Circuits for the Metropolis-Hastings Algorithm Claudon, Baptiste Rodenas-Ruiz, Pablo Piquemal, Jean-Philip Monmarché, Pierre Quantum Physics Statistical Mechanics Chemical Physics 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. |
| title | Quantum Circuits for the Metropolis-Hastings Algorithm |
| topic | Quantum Physics Statistical Mechanics Chemical Physics |
| url | https://arxiv.org/abs/2506.11576 |