Quantum Speedup for Nonreversible Markov Chains
Baptiste Claudon, Jean-Philip Piquemal, Pierre Monmarché · 2025
Read Quantum Speedup for Nonreversible Markov Chains by Baptiste Claudon, Jean-Philip Piquemal, Pierre Monmarché (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05868.txt.
Description
Baptiste Claudon, Jean-Philip Piquemal, and Pierre Monmarche study a speed prize for quantum computing in a 2025 paper. Their topic is Markov chains, step-by-step random walks used in stats, physics, and finance. Past work showed quantum tools can speed up walks that can run backwards.
Many real walks cannot run backwards, though, and those forms can in fact beat the backwards kind on plain machines. The team builds ways to turn such walks into a form quantum tools can use. They claim gains that can beat the square-type speed-up known for the backwards case, in some settings by far more. If the methods hold up, sampling work in science and data fields could get much faster.
Catalog record
| CREATOR | Baptiste Claudon, Jean-Philip Piquemal, Pierre Monmarché |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-05868