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

CREATORBaptiste Claudon, Jean-Philip Piquemal, Pierre Monmarché
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-05868

Browse the full library · About the Tower of Babel