# Practical advantage beyond the quadratic speedup limit with fully-quantum walks

arXiv: https://arxiv.org/abs/2607.22818 · HTML: https://mlsanity.com/paper/2607.22818/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 82 references that are in the map.
- First posted on arXiv 24 Jul 2026.

## Builds on (most cited first, 16 of 16)

- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Challenges and Opportunities in Quantum Optimization](https://mlsanity.com/paper/2312.02279/) (2023)
- [A Survey and Taxonomy of Graph Sampling](https://mlsanity.com/paper/1308.5865/) (2013)
- [Assessing requirements to scale to practical quantum advantage](https://mlsanity.com/paper/2211.07629/) (2022)
- [Disentangling Hype from Practicality: On Realistically Achieving Quantum Advantage](https://mlsanity.com/paper/2307.00523/) (2023)
- [The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model](https://mlsanity.com/paper/2110.14206/) (2021)
- [Quantum-enhanced Markov chain Monte Carlo](https://mlsanity.com/paper/2203.12497/) (2022)
- [Classical and Quantum Algorithms for Tensor Principal Component Analysis](https://mlsanity.com/paper/1907.12724/) (2019)
- [Janus II: a new generation application-driven computer for spin-system simulations](https://mlsanity.com/paper/1310.1032/) (2013)
- [Quartic quantum speedups for community detection](https://mlsanity.com/paper/2510.08494/) (2025)
- [A Divide-and-Conquer Approach to Dicke State Preparation](https://mlsanity.com/paper/2112.12435/) (2021)
- [Quantum Metropolis Sampling via Weak Measurement](https://mlsanity.com/paper/2406.16023/) (2024)
- [Quartic quantum speedups for planted inference](https://mlsanity.com/paper/2406.19378/) (2024)
- [Microcanonical simulated annealing: Massively parallel Monte Carlo simulations with sporadic random-number generation](https://mlsanity.com/paper/2506.16240/) (2025)

## Abstract (arXiv)

We introduce a new class of fully-quantum Metropolis walks in which both the proposal and acceptance steps are intrinsically quantum. Unlike standard quantum walks obtained by quantizing classically efficient Markov chains, our algorithm employs Hamiltonian simulation as a quantum-native proposal mechanism, enlarging the class of quantum walks beyond classical counterparts. We target the problem of sampling from the low-temperature Gibbs distribution of classical dense Ising models, within a fixed error in total variation distance. This approach achieves about a cubic polynomial asymptotic advantage over previous quantum-walks, resulting in a total sixth-degree polynomial queries speedup compared to the best classical walk. This shows that speedups beyond the widely assumed quadratic limit are possible within the quantum walk formalism. We perform a complete fault-tolerant compilation of all algorithmic primitives and benchmark against CPU, GPU, and FPGA implementations of the best classical Markov chain. Under identical hardware assumptions, the resulting advantage runtime crossover is reduced from approximately 103 years for conventional quantum walks to less than one day. These results identify fully-quantum Markov chains as a promising route toward practical quantum advantage.